You should use Sprague-Grundy theory to solve this problem. On Oct 12, 6:11 pm, Brats <rbharat...@gmail.com> wrote: > 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
-- Vladislav Isenbaev (winger) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
