카드 섞기 페이션스

많은 어린이가 카드놀이를 즐기지만, 카드를 제대로 섞기 어려워하는 경우가 많습니다. 다음의 '페이션스(patience)' 게임은 카드를 섞는 연습이 되는 동시에 카드 인식과 간단한 산수 능력을 길러 줍니다. 핵심은 서로 특정한 관계를 이루는, 앞면이 보이도록 놓인 카드의 쌍이나 3장 묶음을 '덮는(cover)' 것입니다.

한 벌의 카드는 4개의 무늬, 13개의 끗수로 이루어진 52장입니다. 무늬는 스페이드(S), 하트(H), 클럽(C), 다이아몬드(D)이고, 끗수는 에이스(A, 값 1), 2, 3, 4, 5, 6, 7, 8, 9, 10(T), 잭(J), 퀸(Q), 킹(K)입니다.

게임을 진행하는 동안 필요에 따라 4×4 격자에 최대 16개의 더미를 만들 수 있습니다(보통은 더 적게 필요합니다). 카드를 앞면이 보이도록 이 4×4 격자에 놓습니다. 각 카드를 놓기 전에, 이미 놓인 카드들 중 덮을 수 있는 쌍이나 3장 묶음이 있는지 확인합니다.

• 두 카드의 끗수가 모두 에이스부터 10까지이고 두 값의 합이 11이면, 그 쌍을 덮을 수 있습니다.
• 세 카드가 {잭, 퀸, 킹} 집합을 이루면, 그 3장 묶음을 덮을 수 있습니다.

덮을 수 있는 쌍이나 묶음이 없으면 새 더미를 시작합니다.

덮을 수 있는 쌍이나 묶음이 둘 이상 있을 때에는, 하나만 덮은 뒤 다시 판단합니다. 카드는 항상 나누어 준 순서(왼쪽에서 오른쪽, 위에서 아래)대로 덮습니다. 가장 먼저 덮는 카드는 진행 시작점에 가장 가까운(가장 먼저 놓인) 자격 있는 카드입니다. 두 번째로 덮는 카드(3장 묶음이면 세 번째 카드도)는 그 짝 중 시작점에 가장 가까운 카드입니다. 예를 들어 덱의 앞부분이 TS QC 8S 8D QH 2D 3H KH 9H... 라면, 처음 7장은 다음과 같이 놓입니다.

TS  QC  8S  8D
QH  2D  3H

이어지는 두 장(KH, 9H)은 각각 쌍을 이루는 8S와 3H를 덮습니다. 쌍이나 묶음을 덮는 것은 나눌 수 없는 하나의 동작으로 취급하므로, 그 동작이 끝나기 전에는 다른 덮기를 고려하지 않습니다.

이 게임의 진행을 시뮬레이션하는 프로그램을 작성하세요. 하나 이상의 카드 덱을 읽어 게임을 시뮬레이션하고, 마지막에 각 더미에 몇 장이 쌓였는지 구합니다. 정해진 16개의 더미 안에서 진행할 수 없으면, 아래에 설명된 메시지와 함께 그 덱의 처리를 종료합니다.

입력은 여러 개의 카드 덱으로 이루어지며, 각 덱은 13장씩 4줄로 주어집니다. 각 카드는 끗수 한 글자(A, 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K)와 무늬 한 글자(S, H, C, D)를 이어 붙인 두 글자로 표기됩니다. 카드는 나누어 줄 순서대로 나열됩니다. 입력의 끝은 # 한 글자만 있는 줄로 표시됩니다.

출력은 입력의 각 덱마다 한 줄씩 이루어집니다. 각 줄은 덱 번호와 콜론(:)으로 시작합니다.

• 지정된 4×4 격자 안에서 덱을 다 놓을 수 없으면, 콜론 뒤에 공백 하나를 두고 Overflowed on card no 메시지와 놓으려던 카드의 순번을 적습니다.
• 덱 전체를 놓을 수 있으면, 카드를 모두 나눈 뒤 각 더미에 쌓인 카드 수(0이 아닌 값들)를 왼쪽 더미부터 차례로 적습니다.

덱 번호와 각 더미의 카드 수는 모두 너비 3칸에 오른쪽 정렬합니다.