시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 61 | 14 | 12 | 24.490% |
이 대회의 스코어는 어떻게 매겨질까?
생각보다 간단하다.
우선, 푼 문제 수가 많으면 순위가 높다.
푼 문제 수가 같을 경우, 페널티가 낮은 사람이 순위가 높다.
페널티는 아래와 같이 계산된다.
페널티 = 푼 문제에 대해서만, (그 문제를 처음 맞기까지 제출한 횟수 - 1) * 20을 문제별로 모두 합산
즉, 이미 맞은 문제에 대한 제출은 페널티에 영향을 끼치지 않으며, 대회가 끝날 때까지 맞히지 못한 문제는 몇 회를 틀렸든 관계없이 페널티에는 합산되지 않는다.
원래는 맞은 시점의 시간도 페널티에 포함되지만, 이 문제에서는 맞은 시간에 대해서는 무시한다. 즉, 제출 횟수만이 페널티에 영향을 끼친다.
대회가 시작한 지 4시간이 지나자, 스코어보드는 더 이상 업데이트되지 않기 시작했다.
B학생은 이 대회에서 꼭 우승하고 싶지만, 강력한 우승 후보 A학생을 이길 수 있을지 자신이 없었다.
B학생은 잠시 고민한 뒤, 스코어보드가 업데이트되지 않고 있음을 이용해 스코어보드를 조작하여 우승 상금을 타려고 한다.
B학생은 앞으로 있을 모든 학생들의 제출 로그를 로그마다 아래와 같은 네 가지 경우 중 하나로 만들려고 한다.
B학생은 통찰력과 예지력으로, 대회가 끝나기 전까지 있을 모든 제출 로그에 대해 분석을 완료하였다.
또한, A학생과 B학생 둘 중 한 명이 아닌 다른 학생의 우승 가능성이 없음도 알아냈다.
B학생은 이제 남은 제출 로그들에 위에 설명한 조작을 적용하여 A학생을 이기고 우승하려 한다.
그 전에, B학생은 자신의 우승 가능성이 있는지부터 알아보고 싶다.
당신은 불의를 싫어하지만, 이 문제가 제법 재미있는 문제라고 생각했다.
따라서, B학생이 우승할 수 있는지 없는지를 알아보려고 한다.
첫째 줄에 대회 문제의 수 Q, 남은 제출 로그의 수 N이 주어진다. (1 ≤ Q ≤ 20, 1 ≤ N ≤ 105)
둘째 줄에, 현재 A학생이 해결한 문제의 수 NA와 B학생이 해결한 문제의 수 NB가 주어진다. (0 ≤ NA, NB ≤ Q)
다음 줄에 NA개의 정수로, 현재 A학생이 해결한 문제들이 오름차순으로 주어진다.
다음 줄에 NB개의 정수로, 현재 B학생이 해결한 문제들이 오름차순으로 주어진다.
만일 해결한 문제가 없는 학생이 있다면, 해당 줄은 빈 줄로 주어진다.
문제 번호는 1 이상 Q 이하의 정수이며, 중복된 문제 번호는 주어지지 않는다.
이어 PA, PB가 주어진다. 이는 A학생의 현재 페널티, B학생의 현재 페널티이다. (0 ≤ PA, PB ≤ 2000000)
맞은 문제가 없는 학생의 페널티는 항상 0이다.
그리고 N줄에 걸쳐, 남은 제출 로그가 제출한 순서대로 주어진다.
제출 로그는 정수 세 개 X Y Z로 이루어져 있다.
X는 1, 2, 3 중 하나로, 1일 경우 A학생의 로그, 2일 경우 B학생의 로그, 3일 경우 다른 학생의 로그를 의미한다.
Y는 문제 번호로, 1 이상 Q 이하이다.
Z는 0 또는 1로, 0일 경우 틀렸음을, 1일 경우 맞았음을 의미한다.
A학생과 B학생은 현재 맞은 문제를 제외하고, 다른 모든 문제에 대해 단 한 번의 제출도 없는 상태이다.
이미 맞은 문제에 대해서는 다시 맞거나 틀려도 페널티에 전혀 영향이 없음에 주의한다.
하지만 이미 맞은 문제에 대한 제출을 다시 하는 것은 몇 번이든 가능하다. 이 경우, 제출한 사람은 아무런 영향을 받지 않지만, 조작을 통해서 다른 사람에게 영향을 끼치게 될 수도 있다.
로그를 문제에 나온 방식대로 조작하여 B학생이 우승할 수 있다면 YES를, 불가능하다면 NO를 출력한다.
만일 A학생과 B학생의 푼 문제 수와 페널티가 동일할 경우, B학생은 패배한 것으로 간주한다.
만약 YES를 출력했다면, N줄에 걸쳐 각 로그를 어떤 방식으로 조작했는지 1, 2, 3, 4의 정수로 출력한다.
만약 답이 여러 가지라면 답이 될 수열이 사전 순으로 가장 앞선 것을 출력한다.
6 3 1 2 2 2 4 10 20 3 4 1 3 4 0 1 4 1
YES 2 1 2
University > 연세대학교 > 2017 연세대학교 컴퓨터과학과 프로그래밍 경진대회 I번