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회 이상 승리하는 것은 불가능하므로 이 방법이 가장 좋은 경우이다.

해야 할 일

다빈치가 바라는 바에 따라, 늦게 온 기사가 승리하는 라운드의 수가 최대가 되는 위치를 찾아내는 프로그램을 작성하라.

#2681 upload 5 done 3 how_to_reg 3

마상시합 토너먼트(Jousting tournament) timer 1s memory 256MB

#2681

마상시합 토너먼트(Jousting tournament) 1s 256MB