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 #227: The Chase
Project Euler #227: The Chase
Sort by
recency
|
13 Discussions
|
Please Login in order to post a comment
Looking back at this one, I believe it can be solved quickly for n < 10^18, m < 10^18, in O( log( n ) ).
Imagine a circle and person1 and person2 who have the dice and are sitting exactly opposite to each other on the left and write side of the circle. The probability of person1 rolling 1 and person2 rolling m, is equal to the probability of person1 rolling m and person2 rolling 1. That means the probability of each moving one step in the upper half of the circle (and therefore reducing the distance by two units) is equal to the probability of them doing the same thing in the lower half. And the same is true for other types of move (no passing and one to the right or left). Imho, the average is infinite.
When dice are at their furthest distance there are three options for the change in distance: stay the same, reduce by one or reduce by two.
In this problem there are a finite number of states and there is an exact solution.
I’ve written a few ideas down which should point you in the right direction for solving this one: https://www.jamespking.com/posts/hackerrank-projecteuler-227-writeup/
But when they are not at their furthest distance there is more options including increasing the distance by 1 and increasing by two
What's the expected value of a fair dice?
You can still model this situation and find an exact answer.
how to read input from stdin.....i m using c language
maybe cin?
scanf() i guess
From where the 675 and 44 are came from?
See https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/ Also note that 44 * 113636380 % (10**9 + 9) = 675 Since the modulo operation is not distributive over division we can't directly calculate 675/44 (mod 10^9 + 9). Instead, we find the multiplicative inverse of 44 (ie. 1/44) and use that (as discussed in the article). For more info on why we use the modulo operation read https://www.hackerearth.com/practice/notes/abhinav92003/why-output-the-answer-modulo-109-7/
tym pass