레이팅 미적용August 8 – 15, Plovdiv, Bulgaria
Contest Day 1 - POI
English 1.1
POI
Full Feedback Problem
지역 대회인 플로브디프 정보 올림피아드(POI)는 다음과 같은 특이한 규칙에 따라 열렸다. N명의 참가자와 T개의 문제가 있었다. 각 문제는 테스트 케이스 하나로만 채점되었으므로, 모든 문제와 모든 참가자에 대해 두 가지 가능성만 있었다: 참가자가 그 문제를 풀었거나, 풀지 못했거나. 어떤 문제에도 부분 점수는 없었다.
각 문제의 배점은 대회가 끝난 뒤에 결정되었으며, 그 문제를 풀지 못한 참가자의 수와 같았다. 각 참가자의 점수는 그 참가자가 푼 문제들의 배점의 합과 같았다.
Philip은 대회에 참가했지만 복잡한 채점 규칙에 혼란스러워하며, 지금 결과를 바라보면서도 최종 순위에서 자신의 등수를 알아내지 못하고 있다. Philip의 점수와 순위를 계산하는 프로그램을 작성하여 그를 도와주시오.
대회 전에 참가자들에게는 1부터 N까지의 고유한 ID가 부여되었다. Philip의 ID는 P였다. 대회의 최종 순위표는 참가자들을 점수의 내림차순으로 나열한다. 동점인 경우, 동점인 참가자들 중 더 많은 문제를 푼 사람이 더 적게 푼 사람보다 앞에 나열된다. 이 기준으로도 동점이면, 결과가 같은 참가자들은 ID의 오름차순으로 나열된다.
TASK
어느 참가자가 어느 문제를 풀었는지가 주어졌을 때, Philip의 점수와 최종 순위표에서의 등수를 구하는 프로그램을 작성하시오.
EXAMPLE
Sample Input
Sample Output
5 3 2
0 0 1
1 1 0
1 0 0
1 1 0
1 1 0
3 2
첫 번째 문제는 단 한 명만 풀지 못했으므로 1점이다. 두 번째 문제는 두 명이 풀지 못했으므로 2점이다. 세 번째 문제는 네 명이 풀지 못했으므로 4점이다. 따라서 첫 번째 참가자는 4점이고, 두 번째 참가자(Philip), 네 번째, 다섯 번째 참가자는 모두 3점이며, 세 번째 참가자는 1점이다. 참가자 2, 4, 5는 첫 번째 동점 처리 기준(푼 문제 수)에서도 모두 동점이며, 두 번째 동점 처리 기준(더 작은 ID)에 따라 Philip이 나머지보다 앞선다. 따라서 최종 순위표에서 Philip의 등수는 2이다. 그는 ID 1인 참가자에게만 뒤진다.
\(1 \le N \le 2,000\)
참가자의 수
\(1 \le T \le 2,000\)
문제의 수
\(1 \le P \le N\)
Philip의 ID
프로그램은 표준 입력에서 다음 데이터를 읽어야 한다:
• 첫 줄에는 정수 N, T, P가 공백으로 구분되어 주어진다.
• 다음 N개의 줄에는 어느 참가자가 어느 문제를 풀었는지가 주어진다. 이 중 k번째 줄은 ID가 k인 참가자가 푼 문제들을 나타낸다. 각 줄에는 공백으로 구분된 T개의 정수가 있다. 첫 번째 수는 참가자 k가 첫 번째 문제를 풀었는지를 나타낸다. 두 번째 수는 두 번째 문제에 대해 같은 것을 나타내며, 이하 같다. 이 T개의 수는 모두 0 또는 1이며, 1은 참가자 k가 해당 문제를 풀었다는 뜻이고 0은 풀지 못했다는 뜻이다.
프로그램은 표준 출력에 공백 하나로 구분된 두 정수가 있는 한 줄을 출력해야 한다. 첫 번째는 Philip이 POI 대회에서 얻은 점수이다. 두 번째는 최종 순위표에서 Philip의 등수이다. 등수는 1 이상 N 이하의 정수이며, 1은 가장 위에 나열된 참가자(즉, 점수가 가장 높은 참가자)를,
August 8 – 15, Plovdiv, Bulgaria
Contest Day 1 - POI
English 1.1
N은 가장 아래에 나열된 참가자(즉, 점수가 가장 낮은 참가자)를 나타낸다.
GRADING
총 35점에 해당하는 여러 테스트에서는 Philip과 같은 점수를 가진 다른 참가자가 없다.