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

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


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

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

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

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

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


D3

 

 
D1D2 
S2D2 
D2D1 
S4D1 
S1S1D2
S1T1D1
S1S3D1
D1D1D1
D1S2D1
S2S2D1

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

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

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

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

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