Saşa təsadüfən bərabər üzləri 1, 2, 3, 4 ədədləri ilə nömrələnmiş N eyni üçbucaqlı…
- User
Saşa təsadüfən bərabər üzləri 1, 2, 3, 4 ədədləri ilə nömrələnmiş N eyni üçbucaqlı piramidanı döşəməyə səpələdi. Bu zaman o, növbə ilə gediş etməklə iki nəfərin oynaya biləcəyi bir oyun fikirləşib tapdı. Bir gedişlə fiqurlardan birini ən böyük nömrəli üzü üzərinə çevirmək olar. Bu gedişi edə bilməyən oyunçu uduzur. İndi Saşa adətən dostlarını udur. Əgər ilk gedişi Siz etsəniz, ona qalib gələ bilərsinizmi?
Giriş verilənləri Birinci sətirdə aralarında boşluq işarəsi olmadan fiqurların dayandıqları üzlərinin nömrələri olan N sayda ədəd yazılmışdır. N<10000.
Çıxış verilənləri Əgər sizin uduş strategiyanız varsa, çıxışa 1, qismət Saşanın tərəfindədirsə 0 verin.
Nümunələr Giriş #1 4243 Çıxış #1 1 1-ci testi zəhmət olmasa izah elə
- Assistant
Bu oyun, hər bir üçbucaqlı piramidanın vəziyyətinə görə Grundy nömrəsi (Grundy Number) hesablanaraq Nim oyununa çevrilə bilər. Bu yanaşma oyunların optimal strategiyasını tapmaq üçün istifadə olunur.
Problem Anlayışı:
- Hər bir piramidanın yuxarı üzünün nömrəsi 1, 2, 3 və ya 4-dür.
- Hər gedişdə, piramidanı döndərərək yuxarı üzünü daha böyük nömrəli bir üzü ilə əvəz edə bilərsiniz.
- İki oyunçu növbə ilə hərəkət edir və hər hansı bir gediş edə bilməyən oyunçu uduzur.
Grundy Nömrələrinin Hesablanması:
Grundy nömrəsi, bir vəziyyətdəki mümkün gedişlərin Grundy nömrələrindən minimal müsbət tam ədəd (mex) kimi təyin olunur.
-
Grundy(4):
- 4-dən daha böyük nömrəli üz yoxdur.
- Grundy(4) = 0
-
Grundy(3):
- 3-dən daha böyük nömrə: 4
- Σ mümkün Grundy nömrəsi: {Grundy(4)} = {0}
- Grundy(3) = mex{0} = 1
-
Grundy(2):
- 2-dən daha böyük nömrələr: 3, 4
- Σ mümkün Grundy nömrəsi: {Grundy(3), Grundy(4)} = {1, 0}
- Grundy(2) = mex{0, 1} = 2
-
Grundy(1):
- 1-dən daha böyük nömrələr: 2, 3, 4
- Σ mümkün Grundy nömrəsi: {Grundy(2), Grundy(3), Grundy(4)} = {2, 1, 0}
- Grundy(1) = mex{0, 1, 2} = 3
Oyunun Ümumi Grundy Nömrəsinin Hesablanması:
Əgər toplam XOR (Exclusive OR) Grundy nömrələri sıfır deyilsə, ilk oyunçu qalib gəlmək üçün strategiyaya sahibdir.
Verilən nümunə:
Giriş: 4243Bu ardıcıllığı Grundy nömrələrinə çevirək:
- 4 → Grundy(4) = 0
- 2 → Grundy(2) = 2
- 4 → Grundy(4) = 0
- 3 → Grundy(3) = 1
XOR hesablanması:
0 ^ 2 ^ 0 ^ 1 = 3Sonuç XOR = 3 (sıfırdan fərqlidir).
Nəticə:
Toplam XOR sıfırdan fərqli olduğu üçün ilk gedişi edən oyunçu qalib gəlmək üçün strategiyaya sahibdir.
Çıxış:
1