http://www.spoj.com/problems/NGM/
This problem is a very interesting one. For solving the tasks like this we need to determine what actually means " the best strategy". So here is what I am telling you, if there is one digit present on the board the winner is the first player for sure, because he will just subtract that digit fro itself and get 0. If the current number is 10 and it is now the turn of the second player the first player would still win right? So if we want to win we need to make a situation where the number 10 will be on the board and it will be the second player's turn, consider the number 11,12,13,14,15,16,17,18,19 in all of those cases the first player would take out the last digit leaving the number 10 to the second player which is a complete defeat. The same goes for every number, to conclude the best strategy is to subtract the last digit from the number so that we can leave a number which is divisible by 10 to the other player and when he makes a move (he can't turn the number divisible by 10 into another number divisible by 10 because the maximum number ho might be able to subtract is 9) and we will do it again and again until he will be down to the number 10 which is a lose. And of course it is clear that if we have a number divisible by 10 from the beginning that means that we will lose it.
This problem is a very interesting one. For solving the tasks like this we need to determine what actually means " the best strategy". So here is what I am telling you, if there is one digit present on the board the winner is the first player for sure, because he will just subtract that digit fro itself and get 0. If the current number is 10 and it is now the turn of the second player the first player would still win right? So if we want to win we need to make a situation where the number 10 will be on the board and it will be the second player's turn, consider the number 11,12,13,14,15,16,17,18,19 in all of those cases the first player would take out the last digit leaving the number 10 to the second player which is a complete defeat. The same goes for every number, to conclude the best strategy is to subtract the last digit from the number so that we can leave a number which is divisible by 10 to the other player and when he makes a move (he can't turn the number divisible by 10 into another number divisible by 10 because the maximum number ho might be able to subtract is 9) and we will do it again and again until he will be down to the number 10 which is a lose. And of course it is clear that if we have a number divisible by 10 from the beginning that means that we will lose it.
your blog is very helpful to newcomers in competitive programming. Thanks a lot.
ReplyDeletethanks a ton :)
ReplyDelete