Помощник по подсчету очков в боулинге
Боулинг — это популярный вид спорта в США. Однако предсказать количество фреймов, необходимых для победы в игре, может быть сложно для тех, кто не является членом 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.