프로그램 명: ioi_tournament
제한시간: 1 초

1491년 베아트리체의 결혼식을 위해서 밀란의 스포르자 공작은 다빈치에게 3일간의 마상 시합(말을 타고 창 실력을 겨루는 게임)을 포함한 결혼 축제를 기획하도록 부탁하였다. 하 지만 가장 인기있는 기사가 도착이 늦기에...

토너먼트

마상시합 토너먼트에 참가하는 N 명의 기사는 처음에 한 줄로 서 있고, 줄에 선 순서대로 기사들은 0 부터 N - 1 까지 번호가 붙어 있다. 마상시합의 한 라운드는 두 위치 S와 E를 (0 ≤ S < E ≤ N - 1) 부름으로써 시작된다. 그러면 번호가 S 이상 E 이하인 모든 기사들이 이번 라운드에서 경쟁하여 1명의 승자가 정해지게 된다. 승자는 다시 원래의 줄로 돌아가고, 패 자들은 경기에서 빠지게 된다. 기사들이 0번 쪽으로 순서를 유지하면서 이동하여 원래 줄 의 빈 자리들을 채운다. 결과적으로 남은 기사들의 번호는 0 부터 N - (E - S) - 1 까지가 된 다. 다음 라운드도 같은 방식으로 계속되어 마지막 한명의 기사가 남을 때 까지 계속된다. 다빈치는 기사들의 실력이 모두 다르다는 것을 알고 있으며, 실력은 0 부터 N - 1 까지의 정 수로 표현된다 (값이 클 수록 더 좋은 실력을 의미한다). 또한, 다빈치는 모든 C개의 라운드 에서 불려질 번호 범위도 정확히 알고 있고, 각 라운드에서 가장 좋은 실력 값을 가진 기사 가 반드시 이긴다고 확신한다.

늦게 온 기사

N 명의 기사들 중 N - 1 명은 이미 도착하여 줄을 서 있지만, 가장 인기있는 기사만이 아직 도착하지 않았다. 아직 도착하지 않은 기사의 실력 값은 R이다. 다빈치는 그 기사의 인기를 이용해 축제의 즐거움을 더할 목적으로, 그 기사가 승리하는 라운드의 수가 가장 많아지도 록 그 기사의 위치를 정하고 싶어한다. 그 기사가 참여하지 않는 라운드는 무관하며 단지 그 기사가 참여해서 이기는 라운드의 수 만이 중요하다는 점에 주의하라.

예제

기사의 총 수 N = 5인 경우에, N - 1 명의 기사들은 이미 줄을 서 있고 각각의 실력 값은 줄 에 있는 순서 대로 [1, 0, 2, 4]라고 하자. 늦게 온 기사의 실력 값은 R = 3임을 알수 있다. 토 너먼트는 C = 3 라운드로 구성되며 각 라운드에서 불려지는 (S, E) 값들은 순서대로 다음과 같다고 하자: (1, 3), (0, 1), (0, 1).

다빈치가 늦게 온 기사를 첫번째 위치에 배치하게 되면 전체 기사들의 실력 값은 [3, 1, 0, 2, 4]가 된다. 첫번째 라운드는 위치 1, 2, 3에 있는 실력 값이 각각 1, 0 , 2인 기사들이 경쟁하 고 실력 값 2인 기사가 승자가 된다. 이 라운드 후에 남은 기사들이 있는 줄의 실력 값은 순 서대로 [3, 2, 4]와 같이 될 것이다. 다음 라운드는 실력 값 3인 기사와 실력 값 2인 기사가 (위치 번호로는 0과 1) 경쟁하고 실력 값 3인 기사가 승리하여, 남은 줄의 실력 값은 [3, 4]가 된다. 마지막 라운드의 승자는 실력 값 4인 기사일 것이다. 결과적으로, 늦게 온 기사는 단 하나의 라운드(두번째 라운드)에서만 승리하였다.

반면에, 다빈치가 늦게 온 기사를 실력 값 1인 기사와 0인 기사 사이에 배치하였다면, 최초 의 줄의 실력 값들은 다음과 같을 것이다: [1, 3, 0, 2, 4]. 이 경우, 첫 라운드에 참여하는 기사 들의 실력 값은 3, 0, 2와 같으며, 실력 값 3인 기사가 승리한다. 이제 남은 줄의 실력 값들은 [1, 3, 4]이며 그 다음 라운드에서 실력 값 1, 3인 기사들이 경쟁하여 역시 실력 값 3인 기사 가 승리한다. 직후의 남은 줄의 실력 값들은 [3, 4]이며, 마지막 라운드에서는 실력 값 4인 기사가 승리한다. 따라서, 이 경우 늦게 온 기사는 2개의 라운드에서 승리하며, 늦게온 기 사가 3회 이상 승리하는 것은 불가능하므로 이 방법이 가장 좋은 경우이다.

해야 할 일

다빈치가 바라는 바에 따라, 늦게 온 기사가 승리하는 라운드의 수가 최대가 되는 위치를 찾아내는 프로그램을 작성하라. 구체적으로, GetBestPosition(N, C, R, K, S, E) 함수 를 작성하여야 한다. 이 함수를 호출할 때 인자들의 값의 정확함이 보장된다. 즉, E[i]의 값은 (i + 1) 번째 라운드 가 시작할 때 줄에 있는 기사들의 수 보다 작음이 보장되며, 모든 C개의 라운드가 끝난 다 음에는 단 한명의 기사만이 남아 있음이 보장된다.

GetBestPosition(N, C, R, K, S, E) 함수는 늦게 온 기사를 배치할 수 있는 최적의 위치 P를 리턴하여야 한다 (0 ≤ P ≤ N - 1). 만약 최적의 위치가 여러 개일 경우는 가장 작은 값을 리턴하여야 한다. (늦게 온 기사의 위치는 그 기사가 배치된 이후의 줄에서의 위치를 말하 며, 가장 앞의 위치를 0으로 시작하여 표현한 것이다. 다르게 표현하면, P는 늦게온 기사를 최적 위치에 배치한 후, 그 기사 앞에 있는 기사들의 수이다. 특정한 경우들을 보면, P = 0 이라는 것은 늦게 온 기사가 가장 앞에 위치한다는 뜻이며, P = N - 1 이라는 것은 늦게 온 기사가 줄의 가장 뒤에 위치한다는 뜻이다.)

Grader 예시

주어지는 grader의 입력은 다음 양식과 같다.
For his wedding with Beatrice d'Este in 1491, the Duke of Milan Lodovico Sforza asked Leonardo to orchestrate the wedding celebrations, including a great jousting tournament that lasted for three whole days. But the most popular knight is late… Tournament

. In a jousting tournament, the N knights are first arranged in a line and then their positions are numbered from 0 to N - 1 following the line order. The joust master sets up a round by calling out two positions S and E (where 0 ≤ S < E ≤ N - 1). All the knights whose positions are between S and E (inclusive) compete: the winner continues in the tournament and goes back to his place in the line, whereas the losers are out of the game and leave the field. After that, the remaining knights pack together towards the beginning of the line, preserving their relative order in the line, so that their resulting positions are from 0 to N - (E - S) - 1. The joust master calls out another round, repeating this process until just one knight remains. Leonardo knows that all the knights have different strengths, represented as distinct ranks from 0 (weakest) to N - 1 (strongest). He also knows the exact commands that the joust master will call out for the C rounds: he's Leonardo, after all… and he is certain that in each of these rounds the knight with the highest rank will win.

Late knight

N - 1 of the N knights are already arranged in the line, just the most popular knight is missing. This knight has rank R and is arriving a bit late. For the benefit of the entertainment, Leonardo wants to exploit his popularity and choose for him a position in the line that will maximize the number of rounds that the late knight will win. Note that we are not interested in the rounds that don't involve the late knight, just in the rounds he takes part in and wins.

Example

For N = 5 knights, the N - 1 knights that are already arranged in the line have ranks [1, 0, 2, 4], respectively. Consequently, the late knight has rank R = 3. For the C = 3 rounds, the joust master intends to call out the (S, E) positions per round, in this order: (1, 3), (0, 1), (0, 1). If Leonardo inserts the late knight at the first position, the ranks of the knights on the line will be [3, 1, 0, 2, 4]. The first round involves knights (at positions 1, 2, 3) with ranks 1, 0, 2, leaving the knight with rank 2 as the winner. The new line is [3, 2, 4]. The next round is 3 against 2 (at positions 0, 1), and knight with rank R = 3 wins, leaving the line [3, 4]. The final round (at positions 0, 1) has 4 as winner. Thus, the late knight only wins one round (the second one).

입력

출력

입출력 예

입력

출력


출처:ioi/2012/day2/3번 문제
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]