레이팅 미적용August 8 – 15, Plovdiv, Bulgaria
Contest Day 1 - Archery
English 1.1
양궁 (ARCHERY)
양궁 대회가 다음 규칙에 따라 열린다. N개의 과녁이 한 줄로 배치되어 있으며, 줄에서의 위치에 따라 1부터 N까지 번호가 매겨져 있다(가장 왼쪽 과녁이 과녁 1, 가장 오른쪽 과녁이 과녁 N). 또한 2*N명의 궁수가 있다. 대회 중 어느 시점에서든 각 과녁에는 두 명의 궁수가 있다. 대회의 매 라운드는 다음 절차에 따라 진행된다:
각 과녁의 두 궁수가 서로 겨루어 승자와 패자를 정한다. 그 후 모든 궁수는 다음과 같이 재배치된다:
과녁 2부터 N까지의 승자들은 왼쪽 과녁(즉, 각각 과녁 1부터 N - 1)으로 이동한다.
과녁 2부터 N까지의 패자들과 과녁 1의 승자는 같은 과녁에 남는다.
과녁 1의 패자는 과녁 N으로 이동한다.
대회는 R 라운드 동안 계속되며, 라운드 수는 적어도 궁수의 수 이상이다(즉, R ≥ 2*N).
여러분은 대회에 정확히 정시에 도착한 유일한 궁수이다. 다른 2*N - 1명의 궁수는 모두 일찍 도착해 이미 한 줄로 서 있다. 이제 여러분이 할 일은 그들 사이 어딘가에 끼어드는 것이다. 여러분이 자리를 잡은 뒤에는, 줄의 가장 왼쪽 두 궁수가 과녁 1에서 대회를 시작하고, 다음 두 명은 과녁 2에서 시작하는 식으로, 가장 오른쪽 두 궁수가 과녁 N에서 시작하게 된다.
대회의 (여러분을 포함한) 2*N명의 궁수 모두는 실력에 따라 순위가 매겨져 있으며, 순위가 낮을수록(숫자가 작을수록) 실력이 좋다. 순위가 같은 두 궁수는 없다. 또한 두 궁수가 겨룰 때마다 순위 숫자가 더 작은 쪽이 항상 이긴다.
각 경쟁자의 실력을 알고 있는 여러분은, 대회가 끝났을 때 가능한 한 번호가 작은 과녁에 있도록 자신을 배치하고 싶다. 그러한 방법이 여러 가지라면, 그중 시작 과녁의 번호가 가능한 한 큰 방법을 선호한다.
TASK
여러분 자신을 포함한 모든 궁수의 순위와 경쟁자들의 줄에서의 배치가 주어졌을 때, 위에 정의된 목표를 달성하려면 어느 과녁에서 대회를 시작해야 하는지 결정하는 프로그램을 작성하시오.
EXAMPLES
Sample Input
Sample Output
4 8
7
4
2
6
5
8
1
3
3
여러분은 두 번째로 실력이 나쁜 궁수이다. 과녁 1에서 시작하면 과녁 4로 이동한 뒤 끝까지 그곳에 머문다. 과녁 2나 4에서 시작하면 대회 내내 그 자리에 머문다. 과녁 3에서 시작하면 가장 실력이 나쁜 궁수를 이기고 과녁 2로 이동해 그곳에 머문다.
Sample Input
Sample Output
4 9
2
1
5
8
3
4
7
6
2
여러분은 두 번째로 실력이 좋은 궁수이다. 가장 실력이 좋은 궁수는 이미 과녁 1에 있으며 대회 내내 그곳에 머문다. 따라서 어디서 시작하든 여러분은 항상 자신의 과녁에서 이동하게 되며, 과녁 4부터 1까지를 계속 반복해서 돌게 된다. 9번의 이동 후 과녁 1에서 끝나려면 과녁 2에서 시작해야 한다.
\(1 \le N \le 200,000\)
과녁의 수; 궁수 수의 절반과 같다
2N ≤ R ≤ 1,000,000,000 대회 라운드 수
1 ≤ Sk ≤ 2N
궁수 k의 순위
August 8 – 15, Plovdiv, Bulgaria
Contest Day 1 - Archery
English 1.1
프로그램은 표준 입력에서 다음 데이터를 읽어야 한다:
• 첫 줄에는 정수 N과 R가 공백으로 구분되어 주어진다.
• 다음 2N개의 줄에는 궁수들의 순위가 나열된다. 이 중 첫 줄에는 여러분의 순위가 주어진다. 나머지 줄에는 다른 궁수들의 순위가, 그들이 (왼쪽에서 오른쪽으로) 줄을 선 순서대로 한 줄에 한 명씩 주어진다. 이 2N개의 각 줄에는 1 이상 2N 이하의 정수가 하나씩 있다. 순위 1이 가장 좋고 순위 2N이 가장 나쁘다. 순위가 같은 두 궁수는 없다.
프로그램은 표준 출력에 1 이상 N 이하의 정수 하나가 있는 한 줄을 출력해야 한다: 여러분이 대회를 시작할 과녁의 번호.
GRADING
총 60점에 해당하는 여러 테스트에서 N은 5,000을 넘지 않는다.
또한 이 중 총 20점에 해당하는 일부 테스트에서 N은 200을 넘지 않는다.