Асистент з підрахунку очок у боулінгу
Боулінг — це дуже популярний вид спорту в США. Проте підрахунок балів у грі може бути складним для тих, хто не є членами ACM, тому вам доручено створити програму, яка допоможе це зробити.
Для тих, хто ніколи не грав у боулінг або забув, як обчислюються бали, на наступних сторінках наведено опис підрахунку балів у боулінгу, а також приклади вхідних і вихідних даних. Основна ідея полягає в тому, що для перемоги потрібно набрати більше очок, ніж ваш суперник.
Знаючи остаточний рахунок вашого суперника та кількість кеглів, які ви збили кожним кидком до восьмого фрейму, ви повинні визначити, що вам потрібно для перемоги (якщо це можливо). Якщо виграти неможливо, виведіть "неможливо". Інакше, виведіть послідовність кидків, яка дозволить вам виграти, причому ця послідовність має бути першою в лексикографічному порядку. Тобто, вона повинна мати найменший перший кидок, найменший другий кидок з урахуванням першого, найменший третій з урахуванням перших двох і так далі.
Вхідні дані
Вхідні дані складаються з серії тестових випадків. Кожен випадок містить остаточний рахунок вашого суперника, за яким слідує кількість кеглів, збитих кожним вашим кидком у перших восьми фреймах. Кінець введення позначається від’ємним числом. Усі інші значення у файлі є дійсними підрахунками кеглів у грі. Рахунок вашого суперника — це ціле число від 0 до 300, а кількість збитих кеглів у ваших кидках — невід’ємні цілі числа, менші або рівні 10 (де 10 — це кількість кеглів на початку кожного фрейму). Наведений нижче приклад вхідних даних відформатований лише для ясності. Вам потрібно буде ретельно обробити вхідні дані, щоб визначити, де закінчується один тестовий випадок і починається наступний, оскільки ви не можете припустити жодного формату щодо пробілів і розривів рядків у фактичному вхідному файлі!
Вихідні дані
Для кожного вхідного випадку виведіть кидки, необхідні для виграшу гри. Дотримуйтесь цього формату точно: "Випадок", один пробіл, номер випадку, двокрапка та один пробіл, і відповідь для цього випадку, подана як "неможливо" або необхідна кількість кеглів, з точно одним пробілом між кожною парою чисел і без пробілів у кінці.
Як вести рахунок у боулінгу:
Є десять кеглів, які ви намагаєтеся збити, кидаючи в них м'яч.
Для кожного набору з десяти кеглів, якщо ви не збиваєте їх усі першим кидком, ви отримуєте другу спробу.
Один або два кидки, які ви робите в набір з десяти кеглів, називаються "фреймом", і в грі є десять фреймів.
Якщо ви збиваєте всі кеглі першим кидком, це називається "страйк". Якщо ви збиваєте всі кеглі, але це займає обидва кидки, це називається "спеа".
Рахунок обчислюється як сума збитих кеглів, але є бонуси за спеа та страйки, які обчислюються, як описано нижче. Якщо ви ніколи не отримуєте спеа або страйк, ваш рахунок просто дорівнює сумі ваших двадцяти кидків.
Якщо ви отримуєте страйк, ви подвоюєте рахунок наступних двох кидків. Якщо ви отримуєте спеа, ви подвоюєте рахунок наступного одного кидка.
Десятий фрейм особливий тим, що "наступний" кидок(и) зазвичай не існують для страйку або спеа в десятому фреймі. Якщо ви отримуєте спеа в десятому фреймі, ви отримуєте ще один кидок у новий набір з десяти кеглів, який просто додається до 10 за ваш спеа. Якщо ви отримуєте страйк у десятому фреймі, ви отримуєте ще два кидки. Якщо перший з них також є страйком, ви отримуєте другий кидок у ще один новий набір з десяти кеглів. Зверніть увагу, однак, що ви не продовжуєте вічно, якщо продовжуєте отримувати страйки. Ви отримуєте лише два кидки після першого страйку в десятому фреймі, і вони просто додаються до 10 за перший страйк, що дає максимальний рахунок 30 для десятого фрейму (і для будь-якого іншого фрейму).
Таким чином, у десятому фреймі може бути три кидки, тому максимальна кількість кидків у грі становить 2 * 9 + 3 = 21. Мінімальна кількість кидків відбувається, якщо ви отримуєте страйк у кожному з перших дев’яти фреймів, але потім не отримуєте страйк або спеа в десятому. Це призводить до 9 + 2 = 11 кидків.
Приклади:
Ми наводимо кількість збитих кеглів для кожного кидка для десяти фреймів, а потім обчислюємо рахунок.
Приклад 1:
Оскільки немає спеа або страйків, рахунок просто дорівнює сумі всіх цих чисел, що становить 79.
Приклад 2:
Це схоже на приклад 1, але є спеа в фреймі 1 і страйк у фреймі 5. Зверніть увагу, що ми маємо загалом 10 у фреймі 1 перед подвоєнням 6 (перший кидок) у фреймі 3. Також, через страйк у фреймі 5, ми подвоюємо два кидки у фреймі 6. Остаточний рахунок становить 97.
Приклад 3:
Це схоже на приклад 2, але є страйк у фреймі 6. Зверніть увагу, що ми додали ще два збитих кеглі, тому базовий рахунок становить 85, замість 83, як у прикладі 2. Як і раніше, ми подвоюємо перший кидок у фреймі 2, що дає нам 91. Далі ми подвоюємо два кидки після страйку у фреймі 5, які становлять 10 і 7. Це дає нам 108. Нарешті, ми подвоюємо два кидки у фреймі 7, що дає нам 117.
Приклад 4:
Це схоже на приклад 3, але є спеа у фреймі 10. Додаткова кегля на другому кидку в десятому фреймі підвищила б рахунок до 118 (ті ж обчислення, що і в прикладі 3), але ми додаємо 7 на останньому кидку до спеа, тому загальний рахунок становить 125.
Приклад 5 (максимальний рахунок, "ідеальна гра"):
Загальний рахунок для кожного фрейму становить 30, оскільки ми отримуємо 10 за страйк і наступні два кидки, які обидва є 10. Це дає нам максимальний рахунок 300.