글 읽기 - 왜 틀리는지 정말 모르겠습니다.

minjun623 3년 전 0

대회 예제 모두 통과 했고, 게시판 예제 모두 통과 했습니다. 뭐가 문젠지 모르겠습니다.

의미는 없지만 80프로까지 갔다가 틀렸답니다.

코드를 설명하면, x만큼의 시간이 지난 후 탑승한 승객 수를 세고, x+1만큼의 시간이 지난 후 탑승한 승객수를 세서 n이 이 사이면 탐색을 종료 합니다.

x만큼의 시간이 지난 후의 승객 수를 기준으로 탑승하는 승객 번호를 세서 n이 되는 순간 놀이기구의 번호를 출력합니다.

#include <stdio.h>
long long  N, M, inp[10000];
long long search(long long x){
	long long i, ans = 0;
	for(i=0; i<M; i++){
		ans += x/inp[i] + 1;
	}
	return ans;
}
int main(void){
	//mid < N && N <= mid+1 / mid = 0 ~ 
	scanf("%lld%lld", &N, &M);
	long long i, x, head = 0, mid, tail = N*50;
	for(i=0; i<M; i++){
		scanf("%lld", &inp[i]);
	}
	while(head <= tail){
		mid = (head + tail) / 2;
		if(search(mid) < N && N <= search(mid+1)){
			break;
		}else if(search(mid) < N){
			head = mid+1;
		}else{
			tail = mid-1;
		}
	}
	x = search(mid);
	for(i=0; i<M; i++){
		x += (mid+1)/inp[i] - mid/inp[i];
		if(x >= N){
			break;
		}
	}
	printf("%lld\n", i+1);
	return 0;
}

rhdqor213 3년 전 2

n < m 일 수 있습니다. 반례입니다.

3 5
1 2 3 4 5

minjun623 3년 전 1

생각도 못한 반례입니다.

감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 틀리는지 정말 모르겠습니다.

minjun623 3년 전 0

rhdqor213 3년 전 2

minjun623 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말