| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 151 |
Problem: http://www.lightoj.com/volume_showproblem.php?problem=1393
The problem is categorized as Nim in LightOJ. I solved the remaining 4 problems in the same category with no major difficulties (here), however I am stuck on this one.
Could someone please hint to the solution ? Is it only "basic" Nim, or is there something else I need to learn ?
Thanks.
Yes, Spraug-someone's theorem.
Thanks. I haven't yet reached Sprague-Grundy theorem, nice to know it wasn't a variant of normal nim.
FYI, I havent read the problem u mentioned.
And also, every impartial game gets down to nim : ) sorry to frustrate you : ]. But yes, most of algorithmic problems are hard enough to see correspondence between them and the game of nim. Here comes the theorem...
Good luck.
About this problem — it’s a staircase nim on a grid, so we must xor value on the cell (x,y) with answer if (x + y) mod 2 != (r + c) mod 2. For explanation about staircase nim try to google.
P.S. — AC code is here
Thank you so much. Didnt know about staircase nim before. I found explanations for staircase nim, but not ones for it on a grid.
Cold you please give a bit more insight how we treat the grid in this case as a single staircase ?