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.

- All Contests
- ProjectEuler+
- Project Euler #151: Paper sheets of standard sizes: an expected-value problem.
- Discussions

# Project Euler #151: Paper sheets of standard sizes: an expected-value problem.

# Project Euler #151: Paper sheets of standard sizes: an expected-value problem.

#### Sort by

recency

#### |

#### 6 Discussions

#### |

Please Login in order to post a comment

The order of the output is determined by the value of the state which is the order of the recurence calls. The order of the output for N = 4 for the first few configuration states is:

0 0 0 0: 0, 0 0 0 1: 1, 0 0 0 2: 1, 0 0 0 3: 1, 0 0 0 4: 1, 0 0 1 0: 2, 0 0 1 1: 500000005, 0 0 1 2: 333333337, 0 0 1 3: 250000003, 0 0 2 0: 500000005, 0 0 2 1: 388888893

To beat all test cases memoization must be used. Moreover we can cache modulo inverse as the biggest one is mod inverse 64.

Test cases 0 through 3 work for me, but 4 and 5 don't. I assumed the inputs are 7 and 8, so I looked for myself what the outputs are. It turns out for inputs 3 through 6 it just gives the answer, but for 7 and 8 it gets 'truncated'. What should I do? How is it even possible that some people got it right?

And this is where I discovered that modular fraction are a thing and that they can be added and multiplied just like normal fractions. (they form a ring ?!)

Woaw mind blown ^^

Can't understand the output format, why is 500000005 equal to 3/2?

for N=4, is the following results correct? if my understanding of the problem statement is correct, I think the results should be correct, but it cannot pass the test case

0 0 0 0: 0

0 0 0 1: 1

0 0 0 2: 1

0 0 1 0: 2

0 0 0 3: 1

0 0 1 1: 500000005

0 0 0 4: 1

0 0 1 2: 333333337

0 0 2 0: 500000005

0 1 0 0: 500000006

0 0 1 3: 250000003

0 0 2 1: 388888893

0 1 0 1: 916666675

0 0 2 2: 319444448

0 1 0 2: 694444451

0 1 1 0: 652777784

0 1 1 1: 555555561

1 0 0 0: 555555562