Problem description
Bajtek i Bajtosia grają w grę ze stosem kamieni, który początkowo zawiera S kamieni. Gracze wykonują ruchy na zmianę, a zaczyna Bajtek.
W każdej turze gracz wybiera dodatnią liczbę całkowitą x, która jest palindromem1 i usuwa dokładnie x kamieni ze stosu.
Jeśli na początku tury czyjejś osoby stos jest pusty, ta osoba przegrywa. Bajtek zastanawia się, czy przy optymalnej grze obu graczy uda mu się wygrać. Pomóż mu odpowiedzieć na to pytanie.
Wejście
Pierwsza linia wejścia zawiera liczbę całkowitą S - liczbę kamieni.
Wyjście
Należy wypisać TAK, jeżeli przy optymalnej grze obu
graczy wygra Bajtek. W przeciwnym przypadku należy wypisać
NIE.
Ograniczenia
1 ≤ S < 10105
Podzadania
| Podzadanie | Warunki | Punkty |
|---|---|---|
| 1 | S < 100 | 8 |
| 2 | S < 106 | 12 |
| 3 | S < 109 | 24 |
| 5 | Brak dodatkowych ograniczeń. | 56 |
Przykład
| Wejście | Wyjście | Wyjaśnienie |
|
|
Bajtek może zabrać 8 kamieni, wygrywając grę. |
| Wejście | Wyjście | |
|
|
| Wejście | Wyjście | |
|
|
Dodatnia liczba całkowita jest palindromem, jeśli czyta się tak samo od lewej do prawej i od prawej do lewej. 1, 121, 9009 są palindromami, ale 1212, 112, 990 już nie.↩︎