Блог пользователя hanfei19910905

Автор hanfei19910905, 12 лет назад, По-английски

here is my submission , which got a WA on 17th test 3219752

My solution is regarding the segments as the stones in NIM game. The correctness can be proved by SG theorem .

In the 17th test . The number of rest sticks is 1 1 4 1 1 4 (for the same Y) and 2 1 1 3 1 2 . my answer is change 3 to 1 in order to make the xor value to 0.

The system answer is to cut 2,0 2,5 . but 2,3 — 2,4 has been cut before. Is it valid ?? And why my answer is wrong ? Thx :)

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Your idea is correct, but the sizes of NIM heaps here are 2 4 2 4 (the same Y), 3 4 1 2 (the same X). Their XOR is 4. After your cut, they become 2 4 2 4, 3 2 1 2, with XOR 2. After the correct answer, they become 2 4 2 4, 3 0 1 2, with XOR 0.

So what you need to do is consider the total number of uncut segments on every line as the size of the NIM heap, not just consecutive ones. That's because your cut can intersect the previous ones.

The transition from consecutive uncut segments to total number is quite easy, so as long as the rest of your algorithm is correct, you should get OK easily.