글 읽기 - 1011번 반례를 못찾겠습니다.

wjdwo951219 3년 전 0

문제에 적혀있는 테스트는 통과하였습니다.

외부 블로그에 있는 추가적인 데이터로도 테스트 하였습니다만, 오류는 없었습니다.

하지만 결과가 계속 틀렸습니다로 나와서 반례를 찾고싶은데 찾기가 너무 어렵습니다.

먼저 코드에 대한 설명을 작성하겠습니다.

데이터를 입력받고, 거리를 구합니다.

거리의 제곱근을 구하여 제곱근의 소숫점 버림 값과, 올림 값을 각각 구합니다.(minBound, maxBound)

minBound와 maxBound가 같으면, 거리의 제곱근의 값이 자연수라는 뜻이므로, maxBound * 2 -1 값을 출력합니다.

minBound와 maxBound가 다르고, 거리의 값이 범위의 중간값 이상이면 maxBound*2 - 1, 아니라면 minBound * 2를 출력합니다.

오랜시간 고민 끝에 질문 글 올립니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws Exception {

		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(reader.readLine());
		double distance[] = new double[n];
		
		for (int i = 0; i < n; i++) {
			String str = reader.readLine();
			distance[i] = Double.parseDouble(str.split(" ")[1]) - Double.parseDouble(str.split(" ")[0]);
		}
		
		for (int i = 0; i < distance.length; i++) {
			double sqrt = Math.sqrt(distance[i]);
			int minBound = (int)Math.floor(sqrt);
			int maxBound = (int)Math.ceil(sqrt);
			if (minBound == maxBound) {
				writer.write(String.valueOf(maxBound * 2 - 1));
				writer.newLine();
			} else if (((minBound * minBound + 1) + (maxBound * maxBound)) / 2 <= distance[i]) {
				writer.write(String.valueOf(maxBound * 2 - 1));
				writer.newLine();
			} else {
				writer.write(String.valueOf(minBound * 2));
				writer.newLine();
			}
		}

		writer.flush();
	}
	
}

jskimphys 3년 전 0

거리가 2^31-1 근처로 들어올 경우, maxbound*maxbound에서 오버플로우가 일어날 수 있습니다.

jskimphys 3년 전 0

거기다 maxbound^2 에서는 안 나는 경우에도 minbound^2+1+maxbound^2 에서는 더 쉽게 오버플로우가 나네요.

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

문제

문제

출처

ICPC

1011번 반례를 못찾겠습니다.

wjdwo951219 3년 전 0

jskimphys 3년 전 0

jskimphys 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말