볼링 점수 도우미

볼링은 미국에서 인기가 아주 많은 스포츠다. 하지만 게임을 이기려면 남은 프레임에서 핀을 몇 개나 쓰러뜨려야 하는지 따지기가 번거로워서, 그 계산을 대신 해 주는 프로그램을 만들려고 한다.

볼링을 쳐 본 적이 없거나 점수 계산법이 기억나지 않으면 힌트에 정리해 둔 규칙을 읽으면 된다. 이기는 조건은 하나뿐이다. 상대보다 최종 점수가 높아야 한다.

상대의 최종 점수와 내가 8프레임까지 각 투구에서 쓰러뜨린 핀 개수가 주어진다. 남은 9프레임과 10프레임의 투구로 이길 수 있는지 판단하고, 이길 수 있다면 이기게 하는 투구 결과 중 사전순으로 가장 앞서는 것을 구하라. 사전순으로 가장 앞선다는 것은 첫 투구가 가장 작고, 그 값을 고정했을 때 두 번째 투구가 가장 작고, 앞의 두 값을 고정했을 때 세 번째 투구가 가장 작다는 뜻이다. 어떻게 굴려도 이길 수 없으면 impossible을 출력한다.

입력은 여러 테스트 케이스로 이루어진다. 각 케이스는 상대의 최종 점수로 시작하고, 이어서 내 1프레임부터 8프레임까지 각 투구에서 쓰러뜨린 핀 개수가 순서대로 주어진다. 음수가 나오면 입력이 끝난다.

상대의 점수는 0 이상 300 이하의 정수다. 각 투구에서 쓰러뜨린 핀 개수는 0 이상 10 이하의 정수이고, 10은 프레임을 시작할 때 서 있는 핀의 개수다. 입력 끝을 알리는 음수를 빼면 모든 값은 실제 경기에서 나올 수 있는 값이다.

예제 입력은 케이스가 어떻게 나뉘는지 보여 주려고 줄을 맞춰 두었을 뿐이다. 실제 입력에서는 공백과 줄바꿈의 위치를 전혀 가정할 수 없으므로, 한 케이스가 어디서 끝나고 다음 케이스가 어디서 시작하는지는 프레임 규칙으로 직접 판단해야 한다.

각 케이스마다 이기는 데 필요한 투구 결과를 한 줄에 출력한다. 형식은 다음과 같이 정확히 맞춘다. Case, 공백 한 칸, 케이스 번호, 콜론, 공백 한 칸, 그리고 답이다. 답은 impossible이거나 필요한 핀 개수를 순서대로 나열한 것이며, 숫자 사이에는 공백을 정확히 한 칸씩 두고 줄 끝에는 공백을 남기지 않는다.

핀 열 개를 세워 두고 공을 굴려 쓰러뜨린다.

첫 번째 공으로 열 개를 모두 쓰러뜨리지 못하면 두 번째 공을 굴릴 수 있다.

핀 한 세트를 향해 굴리는 공 한 개 또는 두 개를 프레임이라고 하고, 한 게임은 열 프레임으로 이루어진다.

첫 번째 공으로 열 개를 모두 쓰러뜨리면 스트라이크다. 두 번째 공까지 써서 열 개를 모두 쓰러뜨리면 스페어다.

점수는 쓰러뜨린 핀의 합이지만, 스페어와 스트라이크에는 아래와 같은 보너스가 붙는다. 스페어도 스트라이크도 한 번 나오지 않으면 점수는 스무 번 투구의 합이다.

스트라이크를 치면 다음 두 투구의 점수를 한 번 더 더한다. 스페어를 치면 다음 한 투구의 점수를 한 번 더 더한다.

10프레임은 특별하다. 보통이라면 10프레임의 스트라이크나 스페어 뒤에는 다음 투구가 없기 때문이다. 10프레임에서 스페어를 치면 새로 세운 핀 열 개를 향해 한 번 더 굴리고, 그 결과를 스페어의 10점에 더한다. 10프레임에서 스트라이크를 치면 두 번 더 굴린다. 그중 첫 번째가 또 스트라이크면 두 번째 투구는 새로 세운 핀 열 개를 향해 굴린다. 스트라이크가 계속 나와도 투구가 끝없이 이어지지는 않는다. 10프레임의 첫 스트라이크 뒤에 주어지는 투구는 두 번뿐이고 그 결과를 첫 스트라이크의 10점에 더하므로, 10프레임 점수는 최대 30점이다. 다른 프레임도 마찬가지로 최대 30점이다.

따라서 10프레임에서는 최대 세 번 굴릴 수 있고, 한 게임의 투구 수는 최대 $2 \times 9 + 3 = 21$회다. 투구 수가 가장 적은 경우는 1프레임부터 9프레임까지 모두 스트라이크를 치고 10프레임에서는 스트라이크도 스페어도 나오지 않을 때이며, 이때는 $9 + 2 = 11$회다.

아래 표는 열 프레임의 투구 결과다. 첫 행은 프레임 번호이고 둘째 행은 그 프레임에서 쓰러뜨린 핀 개수다.

게임 1

스페어도 스트라이크도 없으므로 점수는 쓰러뜨린 핀을 모두 더한 79점이다.

게임 2

게임 1과 비교하면 1프레임이 스페어이고 5프레임이 스트라이크다. 1프레임에서 10점을 얻은 다음 2프레임 첫 투구인 6을 한 번 더 더한다. 5프레임이 스트라이크이므로 6프레임의 투구 두 번도 한 번 더 더한다. 최종 점수는 97점이다.

게임 3

게임 2에서 6프레임이 스트라이크로 바뀌었다. 쓰러뜨린 핀이 두 개 늘었으므로 보너스를 빼면 게임 2의 83점이 아니라 85점이다. 앞서와 같이 2프레임 첫 투구를 한 번 더 더하면 91점이다. 다음으로 5프레임 스트라이크 뒤의 두 투구인 10과 7을 더하면 108점이다. 마지막으로 7프레임의 투구 두 번을 더하면 117점이다.

게임 4

게임 3에서 10프레임이 스페어로 바뀌었다. 10프레임 두 번째 투구에서 핀 하나를 더 쓰러뜨려 점수가 118점이 되고, 스페어 보너스로 마지막 투구의 7점을 더해 최종 125점이다.

게임 5는 퍼펙트 게임이다.

모든 프레임에서 스트라이크를 쳤으므로 점수는 최고점인 300점이다.