로프 timer 90s memory 1024MB

두 스카우트 팀이 정찰 대회에 참가하고 있다. 결승전이며 두 팀 모두 철저히 준비했다. 게임은 서쪽에서 동쪽으로 흐르는 강을 따라 진행된다. 강가에는 나무가 총 4\mathbf{N}그루 심어져 있으며, 그중 정확히 2\mathbf{N}그루는 북쪽 강둑에 일렬로, 나머지 2\mathbf{N}그루는 남쪽 강둑에 일렬로 늘어서 있다. 두 팀은 번갈아가며 턴을 진행하고, 당신의 팀이 먼저 시작한다.

각 턴에서 플레이하는 팀은, 아직 어떤 로프도 묶여 있지 않은 나무를 북쪽 강둑에서 하나, 남쪽 강둑에서 하나 골라 두 나무 사이에 로프를 묶어 강을 가로지르게 한다. 새로 추가되는 로프는 이전에 추가된 모든 로프보다 더 높은 위치에 놓인다. 플레이하는 팀은 새로 추가한 로프 아래를 지나가는 기존 로프 하나당 1점을 얻는다.

2\mathbf{N}턴이 지나면 모든 나무에 정확히 로프가 하나씩 묶이므로 더 이상 둘 수 있는 수가 없고 게임이 끝난다. 각 팀의 점수는 자신이 플레이한 모든 턴에서 얻은 점수의 합이다. 당신의 팀 점수가 상대 팀 점수보다 엄격히 크면 당신의 팀이 승리한다. 당신의 팀 점수가 상대 팀 점수보다 작거나 같으면 당신의 팀은 승리하지 못한다.

아래 애니메이션은 \mathbf{N}=2일 때 가능한 한 게임을 보여준다. 당신의 팀은 빨간색, 상대 팀은 파란색으로 표시된다.

상대 팀은 두 번째로 시작하는 것이 큰 이점이라고 자신했기 때문에, 자신들의 전략을 공개했다. 상대 팀은 자신의 턴에서, 그 턴에서 얻을 수 있는 점수가 최대가 되는 수를 선택한다. 그런 수가 여러 개라면 그중 하나를 무작위로 고른다. 이 선택은 가능한 선택지들 중에서 균등 무작위로 생성되며, 각 선택은 각 턴마다, 각 테스트 케이스마다, 각 제출마다 독립적으로 이루어진다. 따라서 당신이 완전히 같은 코드를 두 번 제출하더라도, 상대 팀은 서로 다른 무작위 선택을 할 수 있다.

당신은 총 \mathbf{T}번의 게임을 치르며, 그중 최소 \mathbf{W}번은 승리해야 한다.