아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Orko

시간 제한1초메모리 제한128 MB

요약
플레이어 A가 받은 카드 열 장과 나머지 카드를 받은 B가 각 라운드에서 최선으로 플레이할 때, A가 첫 라운드의 선공을 잡고 몇 라운드를 이기는지 구한다.
난이도

어려움10점 중 8점

유형
게임 이론, 백트래킹, 동적 계획법, 비트 연산
정답자
아직 제출이 없습니다

문제

Orko는 두 명이 즐기는 카드 게임입니다. 각 카드에는 색 (빨강, 노랑, 초록, 검정)과 값 (1, 2, 3, 4, 5)이 하나씩 있습니다. 덱은 20장으로 이루어지며, 색과 값의 서로 다른 조합마다 정확히 한 장씩 존재합니다.

두 사람은 각각 20장 중 10장씩을 나누어 받습니다. 게임은 10라운드로 진행되며, 목표는 가능한 한 많은 라운드를 이기는 것입니다. 각 라운드에서 '선'(리드)을 가진 사람이 자신의 카드 한 장을 냅니다. 상대는 같은 색 카드를 가지고 있다면 반드시 같은 색 카드를 내야 하고, 없다면 아무 카드나 낼 수 있습니다.

선을 가진 사람은 다음 두 경우에 그 라운드를 이깁니다.

  • 상대에게 같은 색 카드가 없는 경우
  • 선이 낸 카드의 값이 상대가 낸 카드의 값보다 큰 경우

그 밖의 경우에는 상대가 그 라운드를 이깁니다.

첫 라운드의 선은 임의로 정해지고, 이후 각 라운드의 선은 직전 라운드를 이긴 사람이 가져갑니다.

두 사람 모두 자신이 이기는 라운드 수를 최대화하도록 플레이한다고 할 때, 각 사람이 몇 라운드를 이기는지 구하세요.

입력

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 한 줄로 주어지며, 플레이어 AA가 받은 카드들을 나타냅니다. 각 카드는 색을 나타내는 문자 (R, Y, G, B) 뒤에 값을 나타내는 숫자 (1, 2, 3, 4, 5)가 붙은 형태입니다. 나머지 카드는 모두 플레이어 BB가 받습니다.

마지막 테스트 케이스 다음에는 공백으로 구분한 별 10개로 이루어진 줄

* * * * * * * * * *

이 주어집니다.

출력

각 테스트 케이스마다, 플레이어 AA가 이기는 라운드 수를 나타내는 00 이상 1010 이하의 정수를 한 줄에 출력하세요. 첫 라운드의 선은 플레이어 AA가 가진다고 가정합니다.

예제1

  1. 예제 1

    입력
    G1 G3 B2 R2 Y1 R3 R5 Y2 Y3 G5
    * * * * * * * * * *
    
    예상 출력
    3