If one or more candidates tie for the least number of first-place votes then all of them are removed from the ballots.
이 부분이 실제 문제 출제 의도와 다릅니다. 실제로 의도된 문제 상황은 모두 탈락하는 것이 아닌 한 명만 탈락하는 것입니다. 따라서 다음과 같이 지문을 수정해 주시기 바랍니다.
If one or more candidates tie for the least number of first-place votes then one of them are removed from the ballots.
대회 당시에도 지문이 이렇게 잘못 나왔고, 문제를 제대로 읽은 사람들이 피해를 받았습니다. 실제로 이 지문은 이 부분만이 아니더라도 애매하게 쓰인 부분이나 엄밀하게 정의되지 않은 부분이 굉장히 많고, 문맥/대회 상황상 해당 부분을 추측에 맡겨야 풀 수 있습니다.
(추가: solved.ac 난이도 스레드에 게시한 내용을 그대로 옮겨 옵니다.)
설사 위의 지문 오류를 고치더라도 문제가 발생합니다. 최저 득표를 받은 사람이 여러 명일 때, 그 중 누가 탈락하는지를 알 수 없습니다. 이 문제의 주인공이 탈락할 수도 있고 다른 사람이 탈락할 수도 있는데, 이에 따라 답이 달라지게 됩니다.
위의 문제를 해결하기 위한 가장 그럴듯한 설명은, 만약 주인공을 포함해 여러 명의 꼴찌가 있다면 주인공이 아닌 사람이 탈락한다는 것입니다. 주인공이 이기기 위한 최소 라운드 수를 구하는 것이니 이쪽이 가장 합리적인 설명으로 보입니다만, 다음과 같은 케이스가 문제가 됩니다.
3
1 2 3
이 경우 첫 라운드에서 1번 후보가 떨어지고, 주인공(2번 후보)와 3번 후보가 세 표씩 받는 상태가 됩니다. 이때 과반수를 넘은 후보가 없으므로 지문에 의하면 둘 중 한 명이 떨어져야 하는데, 위의 방식대로 해석하면 3번 후보가 탈락합니다. 따라서 두 번의 라운드 이후 남은 후보가 한 명이 되는데, 이때 라운드를 한 번 더 진행하는지의 여부조차 애매하지만, 진행한다고 가정하면 2, 아니면 1이 답이 됩니다. 그러나 양쪽 모두 이런 식으로 코딩하면 WA를 받고, 의도된 답은 IMPOSSIBLE TO WIN입니다.
이러한 문제들로 인해 이 문제는 현재 세팅에서는 어떻게 해석하더라도 문제가 생겨납니다. 비록 "출제자의 의도에 맞게" 해석하여 문제를 푸는 것이 그리 어렵지는 않지만, 그렇게 해석하기 위해서는 다양한 모순들을 의도적으로 무시해야 합니다.
79brue 8달 전 11
(원문)
문제 지문에 다음과 같은 부분이 있습니다.
If one or more candidates tie for the least number of first-place votes then all of them are removed from the ballots.
이 부분이 실제 문제 출제 의도와 다릅니다. 실제로 의도된 문제 상황은 모두 탈락하는 것이 아닌 한 명만 탈락하는 것입니다. 따라서 다음과 같이 지문을 수정해 주시기 바랍니다.
If one or more candidates tie for the least number of first-place votes then one of them are removed from the ballots.
대회 당시에도 지문이 이렇게 잘못 나왔고, 문제를 제대로 읽은 사람들이 피해를 받았습니다. 실제로 이 지문은 이 부분만이 아니더라도 애매하게 쓰인 부분이나 엄밀하게 정의되지 않은 부분이 굉장히 많고, 문맥/대회 상황상 해당 부분을 추측에 맡겨야 풀 수 있습니다.
(추가: solved.ac 난이도 스레드에 게시한 내용을 그대로 옮겨 옵니다.)
설사 위의 지문 오류를 고치더라도 문제가 발생합니다. 최저 득표를 받은 사람이 여러 명일 때, 그 중 누가 탈락하는지를 알 수 없습니다. 이 문제의 주인공이 탈락할 수도 있고 다른 사람이 탈락할 수도 있는데, 이에 따라 답이 달라지게 됩니다.
위의 문제를 해결하기 위한 가장 그럴듯한 설명은, 만약 주인공을 포함해 여러 명의 꼴찌가 있다면 주인공이 아닌 사람이 탈락한다는 것입니다. 주인공이 이기기 위한 최소 라운드 수를 구하는 것이니 이쪽이 가장 합리적인 설명으로 보입니다만, 다음과 같은 케이스가 문제가 됩니다.
이 경우 첫 라운드에서 1번 후보가 떨어지고, 주인공(2번 후보)와 3번 후보가 세 표씩 받는 상태가 됩니다. 이때 과반수를 넘은 후보가 없으므로 지문에 의하면 둘 중 한 명이 떨어져야 하는데, 위의 방식대로 해석하면 3번 후보가 탈락합니다. 따라서 두 번의 라운드 이후 남은 후보가 한 명이 되는데, 이때 라운드를 한 번 더 진행하는지의 여부조차 애매하지만, 진행한다고 가정하면
2, 아니면1이 답이 됩니다. 그러나 양쪽 모두 이런 식으로 코딩하면 WA를 받고, 의도된 답은IMPOSSIBLE TO WIN입니다.이러한 문제들로 인해 이 문제는 현재 세팅에서는 어떻게 해석하더라도 문제가 생겨납니다. 비록 "출제자의 의도에 맞게" 해석하여 문제를 푸는 것이 그리 어렵지는 않지만, 그렇게 해석하기 위해서는 다양한 모순들을 의도적으로 무시해야 합니다.
따라서 이 문제에 "채점 준비 중"을 거는 것을 제안합니다.