Задача 109
Сколькими отличными друг от друга способами игрок в "Дартс" может списаться с менее чем 100 очков?

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


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

В центре мишени расположены два концентрических круга, которые называют "яблочком". За попадание во внешний круг "яблочка" начисляют 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