문제
팽수와 버미는 크리스마스 트리를 꾸미기 시작했다.
긴 일자형 원통에 들어있는 크리스마스 장식품을
상자는 투명하기 때문에 팽수와 버미는 각 장식품의 색상을 알 수 있다.
위 그림은 두 번째 예제의 초기 상태를 보여준다. 첫 번째 행동으로, 팽수는 왼쪽에서 1번 색상을 꺼내거나 오른쪽에서 3번 색상을 꺼낼 수 있다.
팽수는 트리 꾸미기가 지루해져서 게임을 하기로 했다.
게임의 규칙은 팽수와 버미가 번갈아가며 행동하며, 팽수가 먼저 시작한다.
차례가 올 때마다 플레이어는 상자에서 장식품을 하나 뽑아서 트리에 올린다. (상자의 왼쪽이나 오른쪽에서 가져올 수 있음).
장식품의 색상이 아직 뽑힌 적이 없는 경우, 플레이어는 한 점을 획득한다. 게임은 상자에서 마지막 장식품이 뽑힐 때 종료된다.
게임의 승자는 더 많은 점수를 획득한 플레이어이므로 팽수와 버미 모두 최대한 많은 점수를 얻고 싶어한다.
둘 다 명문 남극 유치원 졸업생이기에 항상 최적으로 게임을 진행한다. 게임이 끝날 때 결과를 출력하라.
입력
첫 번째 줄에 정수로 이루어진, 상자안에 들어있는 장식품의 수
두 번째 줄에
출력
게임의 결과인, 두 숫자가 ':' 기호로 연결된 두 숫자를 출력한다. (작은 따옴표 없이) 이는 각각 팽수와 버미의 점수이다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 15점 | 모든 |
| #2 | 9점 | |
| #3 | 24점 | 모든 |
| #4 | 14점 | |
| #5 | 38점 | 추가 제약 조건 없음. |
예제1
5
11211
1:1
첫 번째로, 팽수는 왼쪽에서 1번 색상을 꺼낸다. 새로운 색상이므로 1점을 획득한다.
버미는 오른쪽에서 1번 색상을 꺼낸다. 이미 뽑은 색상이므로 점수를 획득할 수 없다.
팽수는 왼쪽에서 1번 색상을 꺼낸다. 이미 뽑은 색상이므로 점수를 획들할 수 없다.
버미는 왼쪽에서 2번 색상을 꺼낸다. 새로운 색상이므로 1점을 획득한다.
마지막으로, 팽수는 왼쪽에서 1번 색상을 꺼낸다. 이미 뽑은 색상이므로 점수를 획득할 수 없다.
따라서 최종 결과는 1:1 이다.
예제2
6
123123
2:1