Задача 109
Дартс

Играя в "Дартс", игрок бросает три дротика в мишень, разделенную на двадцать секций одинакового размера, которые пронумерованы от одного до двадцати.


Очки за попадание дротика определяются номером секции, в которую он попал. Дротик, попавший за пределы зеленого/красного внешнего кольца получает ноль очков. Области черного и бежевого цвета, заключенные внутри этого кольца начисляют очки этого сектора. В свою очередь, попадание в зеленое/красное внешнее или среднее кольцо начисляет двойные и тройные очки соответственно.

В центре мишени расположены два концентрических круга, которые называют "яблочком". За попадание во внешний круг "яблочка" начисляют 25 очков, а за попадание во внутренний - в два раза больше, т. е. 50 очков.

Существует много различных вариантов правил игры, но наиболее популярной является игра, при которой игроки начинают со счета 301 или 501, и, кто первый уменьшит свои общие очки до нуля, тот и победил. Однако, часто принято играть по системе "броском в удвоение ", согласно которой игрок должен бросить последний дротик в зону удвоенных очков (в том числе и "яблочко" в центре мишени). Любое другое попадание, уменьшившее очки игрока до единицы или нижк, приведет к тому, что очки за этот подход из трех дротиков "прогорают".

Когда текущие очки игрока позволяют закончить игру в один ход, это называется "выписыванием", и наибольшее возможное выписывание составляет 170: T20 T20 D25 (две тройные 20-ки и удвоенное "яблочко").

Существует ровно одиннадцать различных способов выписаться с 6 очков:


D3

 

 
D1 D2  
S2 D2  
D2 D1  
S4 D1  
S1 S1 D2
S1 T1 D1
S1 S3 D1
D1 D1 D1
D1 S2 D1
S2 S2 D1

Обратите внимание на то, что D1 D2 отличается от D2 D1, т. к. они оканчиваются разными удвоенными значениями. В свою очередь, S1 T1 D1 не отличается от T1 S1 D1.

Помимо этого, рассматривая возможные комбинации, мы не будем учитывать промахи. К примеру, D3 эквивалентно 0 D3 и 0 0 D3.

Невероятно, но всего существует 42336 различных способов выписаться.

Сколькими различными способами игрок может выписаться с менее, чем 100 очками?

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net