http://www.spoj.com/problems/MCOINS/
We need to solve this problem dynamically meaning building the solution for A[i] based on the previous findings. Let us have an array A where A[i] shows the answer for i coins. The array is a boolean array where "true" means that the first player won and "false" means that the second player won. Initially a[1]=true becasue if there is only 1 coin then the winner is the first one for sure and let us have a[0]=false meaning that second one wins when there are no coins at all because the first one can't make a move. Now for every next I if A[i-1] is false then for sure a[i] is going to be true. (because if there are B coins and the winner is the second that means that when there are B+1, B+L, or B+K coins the winner will be the first because we are kind of adding one more move to the total game which changes the outcome).
We need to solve this problem dynamically meaning building the solution for A[i] based on the previous findings. Let us have an array A where A[i] shows the answer for i coins. The array is a boolean array where "true" means that the first player won and "false" means that the second player won. Initially a[1]=true becasue if there is only 1 coin then the winner is the first one for sure and let us have a[0]=false meaning that second one wins when there are no coins at all because the first one can't make a move. Now for every next I if A[i-1] is false then for sure a[i] is going to be true. (because if there are B coins and the winner is the second that means that when there are B+1, B+L, or B+K coins the winner will be the first because we are kind of adding one more move to the total game which changes the outcome).
No comments:
Post a Comment