Hey .. here is a problem I saw somewhere on net. Can anyone give me some ideas on its algo ?
There is a tray that contains a row of "s" slots where biscuits may be placed. You can have atmost one biscuit per slot. You and your friend play a game with it. Each of you get to pick biscuits in turns. You can pick atmost "b" biscuits in a single turn provided they are in consecutive slots with no gaps (empty slots) in between (but you have to pick atleast one in your turn). Whoever picks the last biscuit wins the game. You are given a snapshot of the game and its your turn. Assuming that from this point onwards, both the players play optimally. Find out if you can win the game. And if yes, what is your next move? If there are multiple options for the next move, choose the one where you pick the highest number of biscuits in the next turn. If still there are multiple options, choose the one where you take the leftmost biscuit among them. As input, you will be given 't' which indicates the number of test cases. For each case, you will be given s ( 1<=s<=2000 ), b ( 1<=b<=20 ) seperated by space and the next line will contain s characters that are either '0' or '1' representing each of the s slots. '0' indicates that a biscuit is not present at that particular slot and '1' indicates that a biscuit is present. As output, print "yes" or "no" indicating if you can win and if the answer is yes, print a string of s characters of either '0' or '1' that indicates whether a biscuit is absent or present at the particular slot after you have played your turn. Sample input: 3 3 2 111 8 3 10110111 8 4 11111111 Sample output: yes 101 no yes 11000011 --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
