We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

# Project Euler #109: Darts

# Project Euler #109: Darts

Contest ends in

#### Sort by

recency

#### |

#### 8 Discussions

#### |

Please Login in order to post a comment

Ah, Project Euler #109: Darts! This intriguing problem delves into the surprisingly vast possibilities of checkout throws in the classic game. With the unique "doubles out" rule adding a strategic twist, the number of potential three-dart combinations quickly skyrockets. Cracking this challenge requires clever deduction and efficient search algorithms, rewarding the solver with a deep appreciation for the dartboard's arithmetic elegance. How to play darts Prepare for a satisfying brain-teaser that blends logic and probability into a fun, mathematical adventure!

"There are exactly 14 distinct ways to checkout on a score of 6"... There seems to be more. For example:

These are not included in the list. Which rules crossed them out?

The infinite number of darts are not very friendly. I suppose dynamic programming is not applicable for larger input. My DP approach got TLE #7, #8 and

`MemoryError`

from #9 onwards. If you're interested, here is part of my code snippet:EDIT: Learn about linear recurrence relation matrix (of size ), and then think about constructing the matrix (of size ) that can be feeded to a cumulative vector. Start with the vector`[1] + [0] * 60`

. Perform matrix exponentiation (divide and conquer, very straightforward) that is . And finally, pick the double ending elements from the final vector of . Problem 114 has a relevant approach.Can please someone suggest an idea for less than O(N) solution to deal with test cases 9 and above.

I assume that there should be analytic formula for coefficients of series expansion of generating function just can't find one.

what is modulo 10^9+9 how to represent answer in that format