2009/10/12 Paul Smith <paulsmithena...@gmail.com> > > Some observations: > > Every position is either a win for you or your opponent - the game > does not contain draws. > > Furthermore, the sub-game played from one consecutive set of biscuits > is entirely independent of the other sub-games. > > A single '1' is always winnable (b >= 1) > > A string of 1s is winnable if its length is less than b. > > A string of 0s is identical to a single 0 : 11100000000111 is the same > game as 1110111 > > A position is winnable if it contains an even number of unwinnable > sub-positions. > > are you sure of this ?
suppose there are just 2 symmetric subpositions .. its impossible to win this because whatever move i do, the opponent can do the same in the other sub-position and hence winning. this means irrespective of whether the subpositions are winnable or not, a problem having 2 symmetric subpositions is unwinnable. infact, just because a sub-position is unwinnable doesnt mean you will definitely lose the sub-position. the opponent may play it in such a way that you may still win the sub-position if that leads to his victory. this is where i don't know how to proceed. would i need to use 2 flags for winnable and losable ? > I think you can DP it from there. > > On Mon, Oct 12, 2009 at 12: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 > > > > > > > > > > > -- > Paul Smith > http://www.nomadicfun.co.uk > > p...@pollyandpaul.co.uk > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
