0410. Сыграем в гоулинг?

Input file name:	bowling.in
Output file name:	bowling.out
Time limit:	2 s
Memory limit:	256 megabytes

Богдан очень любит играть в гоулинг. Правила этой игры достаточно просты:

• Игра состоит из десяти раундов.
• В каждом раунде перед игроком ставится десять кегель.
• Раунд состоит из двух бросков.
• Первым броском игрок сбивает некоторое количество кегель.
• Вторым броском игрок сбивает некоторое количество из оставшихся кегель.
• Сумма сбитых кегель прибавляется к итоговому результату.
• Если игрок в предыдущем раунде сбил все кегли, то результат первого броска текущего раунда еще раз прибавляется к итоговому результату.
• Если игрок первым броском сбил все десять кегель, то второй бросок не делается.
• Если в десятом раунде игрок сбил все кегли, то он переходит в бонусный раунд.
• В бонусном раунде перед игроком ставится десять кегель, но у него есть возможность сделать только один бросок. Результат броска прибавляется к итоговому результату.
• Если в первом бонусном раунде игрок сбил все кегди, то он переходит во второй бонусный раунд.
• Игрок набравший наибольшее число очков побеждает в игре.
• Игроки не могут пропускать броски.

После очередной игры возникла неприятность: все результаты игры были потеряны. Остались только данные о совершенных бросках. Для каждого броска известно сколько было сбито кегель. Но никто не помнит, кто именно совершал бросок. Всего было совершено N бросков. Богдану стало интересно, какой максимальный результат он мог набрать. Богдан может считать своими любые из N бросков. Он может менять последовательность бросков любым образом. Каждый бросок может быть задествован не более одного раза. Полученная последовательность должна быть корректной игрой. Эта задача показалась Богдану слишком сложной, поэтому он обратился к вам за помощью.

Формат входного файла

Первая строка входного файла содержит одно число N – количество совершённых бросков. 1 ≤ N ≤ 10⁵. Вторая срока содержит N чисел A_i – количество кегель, которые были сбиты во время броска i. 0 ≤ A_i ≤ 10.

Формат выходного файла

В первой строке выведите количество бросков, которые Богдан считает своими. Во второй строке выведите сами броски в том порядке, в каком Богдан совершал бы их в игре. Если из предложенных бросков нельзя составить корректную игру, то выведите -1.

Пример:

bowling.in	bowling.out
20 1 2 3 3 3 3 3 3 3 8 4 4 4 4 4 4 9 4 4 4	20 3 3 3 3 3 3 4 3 4 4 4 4 4 4 8 2 9 1 4 4
22 1 2 3 3 3 3 3 3 3 8 4 4 4 4 4 4 9 4 4 4 10 1	22 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 8 2 9 1 10 3
20 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5	-1

Discuss       Submit a solution



Printable version