hi guys!↵
↵
i have met a problem in a test and i really dont understand the solution↵
the problem:↵
you are given n(n<=1e5) integers non negative and there are 2 player A , B play in turn (A move first).↵
in each turn , player of this turn must choose one in n intergers , call x , x must greater than 1 and decrease x by an amount not exceeding half of it.↵
who can not move will lose.↵
if A and B all play optimally , who will win↵
↵
i thought it's greedy , and have tried to construct an strategy , but i couldn't.↵
i heard that my friend have just change each a[i] to (a[i]-1)/2 if a[i] still odd , and finally , he calculate the xor sum of all a[i] , if the ans is 0 so B win , in contrast A win↵
he said that was game theory or nim or grundy .. or somethings ↵
i tried to find the information of these on google but didn't understand anything↵
↵
please can someone help me how to learn these , like what should i read to learn these ;-;
↵
i have met a problem in a test and i really dont understand the solution↵
the problem:↵
you are given n(n<=1e5) integers non negative and there are 2 player A , B play in turn (A move first).↵
in each turn , player of this turn must choose one in n intergers , call x , x must greater than 1 and decrease x by an amount not exceeding half of it.↵
who can not move will lose.↵
if A and B all play optimally , who will win↵
↵
i thought it's greedy , and have tried to construct an strategy , but i couldn't.↵
i heard that my friend have just change each a[i] to (a[i]-1)/2 if a[i] still odd , and finally , he calculate the xor sum of all a[i] , if the ans is 0 so B win , in contrast A win↵
he said that was game theory or nim or grundy .. or somethings ↵
i tried to find the information of these on google but didn't understand anything↵
↵
please can someone help me how to learn these , like what should i read to learn these ;-;
