vkdldjvkdnj   2년 전

3405 문제에 달린 글들을 보면 long long을 사용하면 틀리고 int를 사용하면 맞다고 나옵니다. 그래서 오버플로우가 일어나는 코드의 출력값이 정답으로 간주하는 것이 아닌가 싶어서 공식 데이터를 뜯어봤습니다.

공식 데이터의 2.in 파일의 여섯 번째 데이터는 올려둔 Text와 같습니다. 일단 데이터 자체가 문제의 조건과 맞지 않음을 볼 수 있습니다.
그리고 두 번째 왕국이 파산하고 나서 각 왕국의 재정?을 계산해보면 네 번째, 다섯 번째 왕국이 각각 2'791'895'802, -2'630'838'076 으로 두 값이 int 범위를 벗어남을 알 수 있습니다. 하지만 공식 정해에서 long long이 아닌 int를 사용해서 오버플로우가 일어나고 있으며, 공식 정해의 출력값인 '2 3 4'가 정답으로 간주되고 있습니다. 그리고 int 대신 long long을 사용하니 출력이 '2 4'로 나옵니다.

  • 공식 정해에서 int 대신 long long을 사용하면 모든 데이터에 대해 올바른 출력값을 얻을 수 있을 것으로 예상합니다. 일단 out 파일부터 수정해야 합니다.
  • 문제 지문에서 d_i,j 범위를 수정해야 합니다. int 범위 안으로 들어온다고 수정하면 될 것 같습니다.

measurezero   2년 전

64비트 정수 자료형을 이용하면 틀리는 문제점은 수정되어야하지만, 그 수정 방법에 이견이 있어 글을 남깁니다.

기존 문제 제한을 따르면 -2,147,483,648 이상 2,147,483,647 이하의 정수만을 문제 해결 과정에 사용해 올바른 답을 계산할 수 있습니다. 따라서 기존에 통과된 32비트 정수 자료형을 이용해 작성된 모든 코드들이 잘못되었다고 말할 수는 없습니다. 그러나 제안하신 변경사항은 위와 같은 올바른 기존 풀이 또한 모두 틀리게 만듭니다.

저는 문제 조건을 성실히 따라 코드를 작성한 사람들의 풀이를 틀리게 만드는 방향의 변화에는 동의하기 어렵습니다. 이런 경우에는 문제의 조건을 수정할 것이 아닌 문제가 있는 데이터를 삭제하는 것이 올바른 수정 방향이라고 생각합니다.

vkdldjvkdnj   2년 전

measurezero 님의 의견에 동의합니다. int를 사용하는 풀이 또한 올바른 풀이인데 틀리게 하는 것은 옳지 않은 것 같습니다.

하지만 걱정이 되는 부분이 있는 것이, 제가 언급한 '2.in'는 T = 10'000, n = 5입니다. n이 작고 d_ij가 큰 파일은 '2.in' 뿐이어서 그냥 삭제하면 문제가 될 수 있다고 생각합니다. '2.in' 파일을 범위에 맞게 복구하는 것이 가장 좋은 방법인 것 같은데, 시간이 소요되는 작업이라 해주실지 모르겠네요 ㅠ

아무쪼록 얼른 해결이 되었으면 좋겠습니다.

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