Асистент з підрахунку очок у боулінгу

1 секунда

64 мегабайти

Дуже складна

Боулінг — це дуже популярний вид спорту у США. Проте підрахунок балів у грі може бути складним для не-ACMерів, тому вам доручено створити програму, яка допоможе це зробити.

Для тих, хто ніколи не грав у боулінг або забув, як обчислюються бали, далі наведено опис підрахунку балів у боулінгу, а також приклади вхідних і вихідних даних. Основна ідея полягає в тому, що для перемоги потрібно набрати більше очок, ніж ваш суперник.

Знаючи остаточний рахунок вашого суперника і кількість кеглів, які ви збили кожним кидком до восьмого фрейму, ви повинні визначити, що вам потрібно для перемоги (якщо це можливо). Якщо виграти неможливо, виведіть impossible. Інакше, виведіть послідовність кидків, яка дозволить вам виграти, причому ця послідовність має бути першою у лексикографічному порядку. Тобто, вона повинна мати найменший перший кидок, найменший другий кидок з урахуванням першого, найменший третій з урахуванням перших двох тощо.

Вхідні дані

Вхідні дані складаються з серії тестових випадків. Кожен випадок містить остаточний рахунок вашого суперника, після чого йде кількість кеглів, збитих кожним вашим кидком у перших восьми фреймах. Кінець введення позначено від'ємним числом. Усі інші значення у файлі є дійсними підрахунками кеглів у грі. Рахунок вашого суперника — це ціле число від $0$ до $300$ , а кількість збитих кеглів у ваших кидках — невід'ємні цілі числа, не більші за $10$ (де $10$ — це кількість кеглів на початку кожного фрейму). Приклад вхідних даних, наведений нижче, відформатовано для ясності. Вам потрібно буде ретельно обробити вхідні дані, щоб визначити, де закінчується один тестовий випадок, а починається наступний, оскільки не можна припускати жодного формату відносно пробілів і розривів рядків у фактичному вхідному файлі!

Вихідні дані

Для кожного вхідного випадку виведіть кидки, необхідні для перемоги у грі. Дотримуйтеся такого формату: Case, один пробіл, номер випадку, двокрапка і один пробіл, і відповідь для цього випадку, подана як impossible або необхідна послідовність кількостей кеглів, з рівно одним пробілом між кожною парою чисел і без пробілів у кінці.

Як вести рахунок у боулінгу:

Є десять кеглів, які ви намагаєтесь збити, кидаючи у них кулю.

Для кожного набору з десяти кеглів, якщо ви не збили їх усі першим кидком, ви маєте другу спробу.

Один або два кидки, зроблені по одному набору з десяти кеглів, називають фреймом; у грі є десять фреймів.

Якщо всі кеглі збиті першим кидком, це називають страйком. Якщо всі кеглі збиті за два кидки, це називають спером.

Рахунок розраховується як сума збитих кеглів, але є бонуси за спер та страйки — вони обчислюються, як описано нижче. Якщо у вас немає сперів чи страйків, ваш рахунок — це просто сума всіх двадцяти кидків.

Якщо є страйк, ви додаєте до результату за цей фрейм бали з двох наступних кидків. Якщо є спер, ви додаєте до результату за цей фрейм бали з одного наступного кидка.

Десятий фрейм особливий тим, що наступний кидок або кидки зазвичай відсутні для страйку чи спера у десятому фреймі. Якщо у десятому фреймі ви отримуєте спер, ви маєте ще один кидок по новому набору з десяти кеглів, який просто додається до $10$ за спер. Якщо у десятому фреймі страйк, ви маєте ще два кидки. Якщо перший з них також є страйком, ви маєте ще одну спробу по новому набору. Зверніть увагу, що навіть якщо у десятому фреймі всі страйки, це не триває вічно: додаткових кидків лише два, і вони додаються до $10$ за перший страйк; максимальний результат десятого фрейму (і будь-якого іншого) — $30$ .

Таким чином, у десятому фреймі може бути три кидки, тож максимальна кількість кидків у грі становить $2 \times 9 + 3 = 21$ 2 \times 9 + 3 = 21. Мінімальна кількість — якщо у перших дев'яти фреймах всі страйки, а потім у десятому ні страйку, ні спера: $9 + 2 = 11$ 9 + 2 = 11 кидків.

Приклади

Приклад 1

Примітка

Ми записуємо кількість збитих кеглів для кожного кидка усіх десяти фреймів і тоді рахуємо підсумковий результат.

Приклад 1

$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$43$	$62$	$42$	$81$	$45$	$62$	$72$	$90$	$05$	$63$

Оскільки немає сперів чи страйків, рахунок — це просто сума всіх цих чисел, тобто $79$ .

Приклад 2

$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$46$	$62$	$42$	$81$	$10$	$62$	$72$	$90$	$05$	$63$

Це схоже на приклад 1, але є спер у фреймі $1$ і страйк у фреймі $5$ . Зауважте, що у фреймі $1$ сумарно зібрали $10$ перед додаванням $6$ (перший кидок) з фрейму $3$ . Оскільки у фреймі $5$ був страйк, додаються два кидки з фрейму $6$ . Остаточний рахунок — $97$ .

Приклад 3

$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$46$	$62$	$42$	$81$	$10$	$10$	$72$	$90$	$05$	$63$

Це схоже на приклад 2, але є страйк у $6$ -му фреймі. Додано ще два збитих кеглі, тому базовий рахунок $85$ , а не $83$ , як у прикладі 2. Так само додається перший кидок $2$ -го фрейму (дає $91$ ). Далі додаються два кидки після страйку у $5$ -му фреймі ( $10$ і $7$ ), отримали $108$ . Нарешті додаються два кидки фрейму $7$ , підсумок — $117$ .

Приклад 4

$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$46$	$62$	$42$	$81$	$10$	$107$	$29$	$00$	$56$	$47$

Це схоже на приклад 3, але є спер у десятому фреймі. Додаткова кегля на другому кидку у десятому фреймі підвищила б результат до $118$ , але додаємо $7$ на останньому кидку до спера, тому підсумок — $125$ .

Приклад 5 (максимальний рахунок, "ідеальна гра")

$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$10$	$10$	$10$	$10$	$10$	$10$	$10$	$10$	$10$	$101010$

Для кожного фрейму підсумок — $30$ , адже отримуємо $10$ за страйк і наступні два кидки, обидва по $10$ . Це дає нам максимальний підсумок $300$ .