5460번 - 양궁 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 40 | 12 | 11 | 73.333% |
문제
재현이는 얼마 전 토너먼트 형태의 양궁 대회를 열었다. 1번부터 N번까지 번호가 매겨진 N개의 표적이 일직선상에 순서대로 (가장 좌측에 1번부터 시작하여 오른쪽에 N번으로 끝난다.) 나열되어 있으며, 2×N 명의 궁수들이 있다.
토너먼트는 다음과 같이 진행된다 - 한 표적에는 항상 2명의 궁수들이 할당되어 있으며, 두 궁수는 한 표적을 두고 경쟁하며 승자와 패자를 가른다. 승자와 패자가 결정된 후에는, 2 ~ N 표적에서 승리한 궁수들이 왼쪽 표적으로 이동하며 (1 ~ N-1 표적으로), 2 ~ N 표적에서 패배한 궁수들은 그 자리에 머무른다. 이때 1번 표적에서 승리한 궁수는 그 자리에 머무르며, 1번 표적에서 패배한 궁수는 N번째 표적으로 이동한다. 이 토너먼트는 R번 진행되며, R ≥ 2×N임이 보장된다.
경험있는 양궁 해설가 승원이는 자신을 포함에서 이번에 출전하는 양궁 선수의 실력 등급을 모두 알고 있다. 각 선수의 실력 등급은 1 ~ 2×N 까지의 수로 표시되며, 등급이 낮은 선수일수록 뛰어난 선수이다. 승원이의 이 데이터는 정말 정확해서, 항상 실력이 높은 선수가 실력이 낮은 선수를 이긴다는 사실을 보장할 수 있다. 승원이는 양궁 해설에 타고난 재능을 가지고 있지만 이상하게 양궁 자체에는 별 관심이 없어서, 이번 대회에서 이기는 것보다는 오늘 밤 있는 코드포스 라운드를 놓치지 않는 것에 더 관심이 있다. 출구는 맨 왼쪽에 있기 때문에, 승원이는 R번의 라운드가 끝나고 나서 가장 왼쪽 타겟에 서 있기를 원한다.
다행이도, 승원이를 제외한 2×N-1명의 궁수가 연습을 위해 일찍 대회장에 나와있었다. 승원이는 적절한 위치에 끼어들어가서 양궁 경기를 시작하려 한다. 과연 승원이는 어떠한 위치에 끼어들어가야지 가장 일찍 집에 들어갈 수 있을까?
입력
표준 입력으로부터 다음의 데이터를 읽어야 한다 :
- 첫 번째 줄에 N과 R이 주어진다.
- 두 번째 줄에는 승원이의 실력 등급이 주어진다.
- 세 번째 줄 이후 2×N-1개의 줄에 각 선수의 실력 등급이 주어진다. 현재 선수들은 주어지는 순서대로 왼쪽에서 오른쪽으로 서 있다. 즉 세 번째 줄에 적혀있는 선수가 가장 왼쪽에 있으며, 2×N+1번째 줄에 적혀있는 선수가 가장 오른쪽에 있다. 실력 등급은 2×N 보다 작거나 같은 서로 다른 자연수이다.
출력
승원이가 집에 일찍 들어가기 위해 끼어들어가야 할 위치를 출력한다. 이때 위치는, 승원이가 처음 경쟁할 때 삼을 표적의 번호를 뜻한다. 만약에 최적의 위치가 여러 곳이라면, 그 중 가장 번호가 높은 위치를 출력하면 된다.
제한
- 1 ≤ N ≤ 200000
- 2×N ≤ R ≤ 1,000,000,000
예제 입력 1
4 8 7 4 2 6 5 8 1 3
예제 출력 1
3
예제 입력 2
4 9 2 1 5 8 3 4 7 6
예제 출력 2
2
힌트
승원이의 실력 등급은 7이다. 1번 표적에서 시작할 경우 승원이는 4번 표적으로 간 후 끝까지 해당 표적에 머무른다. 2번 표적이나 4번 표적에서 시작할 경우 승원이는 끝까지 해당 표적에 머무른다. 3번 표적에서 시작할 경우 승원이는 실력 등급이 8인 궁수를 이기고 2번 표적에 끝까지 머무른다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호