Notice that every sixth lamp will always be in the same state. If you know the state of any 6 adjacent lamps you know the state of all lamps. In addition, you just need to know if a certain button has been pushed an even number of times or an odd number. Which even or odd number does not matter, and the order of the button presses does not matter. Don
On Sep 15, 10:26 pm, Mohammad Reza Rahmani <[email protected]> wrote: > just 2^4??? why??? > we have 4^10000 states and it's about 10^6000...This value is very big > to perform complete search...Is it True? > > thank's > > On 9/16/11, Marcelo Amorim Menegali <[email protected]> wrote: > > > > > > > > > Notice that changing the order of button presses doesn't change anything. > > Notice also that pressing a button twice is the same as not pressing it. > > So, in the end, given N, there are at most 2^4 = 16 final configurations > > (each button is either pressed once or not). > > > I hope this will help you. > > > -- > > Marcelo > > > On Thu, Sep 15, 2011 at 6:45 PM, Gaurav Menghani > > <[email protected]>wrote: > > >> On Thu, Sep 15, 2011 at 4:44 PM, Blackwizard > >> <[email protected]> wrote: > >> > Hi > >> > I want to solve this problem but I'm not sure about the algorithm... > >> > I think It can be complete search... > >> > Is the anybody to help me? > >> > what's the algorithm for this question... > > >> > Problem Link: > >> >http://olympiads.win.tue.nl/ioi/ioi98/contest/day1/party/party.html > > >> I think BFS should work, but then some pruning would be required since > >> the number of lamps is large. I'm not sure how the pruning would be > >> done though. > > >> > Thank's > > >> > -- > >> > You received this message because you are subscribed to the Google > >> > Groups > >> "Algorithm Geeks" 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/algogeeks?hl=en. > > >> -- > >> Gaurav Menghani > > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "Algorithm Geeks" 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/algogeeks?hl=en. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" 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/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" 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/algogeeks?hl=en.
