레이팅 미적용소 베시는 카드 게임의 열렬한 팬이다. 마주 볼 수 있는 엄지손가락이 없다는 점을 생각하면 꽤 놀라운 일이다. 안타깝게도 무리의 다른 소들 중에는 좋은 상대가 없다. 사실 그들은 너무 못해서 항상 완전히 예측 가능한 방식으로 플레이한다! 그럼에도 베시가 이기는 방법을 알아내는 것은 여전히 도전이 될 수 있다.
베시와 친구 엘시는 지금 간단한 카드 게임을 하고 있다. \(1 \ldots 2N\)으로 번호가 붙은 \(2N\)장의 카드 덱을 베시에게 \(N\)장, 엘시에게 \(N\)장으로 나눈다. 그런 다음 두 소는 \(N\)번의 라운드를 진행하는데, 각 라운드마다 베시와 엘시가 카드를 한 장씩 낸다. 처음 \(N/2\)번의 라운드에서는 더 높은 카드를 낸 쪽이 1점을 얻고, 마지막 \(N/2\)번의 라운드에서는 규칙이 바뀌어 더 낮은 카드를 낸 쪽이 1점을 얻는다.
베시가 엘시가 카드를 낼 순서를 예측할 수 있다고 할 때, 베시가 얻을 수 있는 최대 점수를 구하시오.
Problem credits: Brian Dean
Problem credits: Brian Dean
입력의 첫째 줄에 N의 값(\(2 \leq N \leq 50,000\); \(N\)은 짝수)이 주어진다.
다음 N개의 줄에는 엘시가 게임의 각 라운드에서 차례로 낼 카드가 주어진다. 이 정보로부터 베시의 카드를 쉽게 알아낼 수 있음에 유의하라.
베시가 얻을 수 있는 최대 점수를 한 줄에 출력한다.
cardgame.in · 출력을 쓸 파일 cardgame.out4
1
8
4
32Here, Bessie must have cards 2, 5, and 6, and 7 in her hand, and
she can use these to win at most 2 points, by saving her '2' card until one
of the hands in the second half of the game.
riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > December > Gold