글 읽기 - 2417번 Parametric Search 관련 질문

h0ngjun7 10년 전 0

주석처리 한 부분으로 하면 TLE가 나고, 그렇지 않으면 0ms에 AC가 나옵니다.
값이 unsigned long long을 벗어나는 경우는 없구요...
왜 그런지 잘 모르겠습니다.
극단적으로 while문을 돌다가 lo=hi=mid=3037000499가 되면, lo=mid+1이 되거나 hi=mid-1이 되어 while문을 종료해야지 정상인데..ㅠㅠ
혹시 아시는 분 답변 달아주시면 감사하겠습니다.

#include <stdio.h>
int main() {
	unsigned long long n, lo, hi, mid, sol = -1;
	scanf("%llu",&n);
	if (n == 9223372030926249001LL) printf("3037000499");
	else if (n > 9223372030926249001LL) printf("3037000500");
	else {
		lo = 0;
		hi = 3037000499LL;
		for (int i = 1; i <= 200; i++) {
		//while (lo <= hi) {
			mid = (lo+hi)/(2LL);
			if (mid*mid >= n) {
				hi = mid-1;
				if (sol < 0 || sol > mid) sol = mid;
			}
			else lo = mid+1;
		}
		printf("%llu",sol);
	}
	return 0;
}

baekjoon 10년 전 0

소스를 돌려보지는 않았지만, unsigned라서 overflow나 underflow가 발생하는게 아닐까 생각됩니다.

printf로 lo와 hi, mid값을 찍어보면 어떨까요

baekjoon 10년 전 0

unsigned long long 의 suffix는 ULL입니다. (http://gcc.gnu.org/onlinedocs/gcc/Long-Long.html)

baekjoon 10년 전 2

맞네요. 0을 입력하니

mid = 0인 경우에

hi = mid - 1 에서 hi에 18446744073709551615가 들어가네요.

h0ngjun7 10년 전 0

우와 답변 감사합니다!ㅎㅎ

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

문제

문제

출처

ICPC

2417번 Parametric Search 관련 질문

h0ngjun7 10년 전 0

baekjoon 10년 전 0

baekjoon 10년 전 0

baekjoon 10년 전 2

h0ngjun7 10년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말