| Fişierul intrare/ieşire: | cmmdcgame.in, cmmdcgame.out | Sursă | Winter Challenge 2020 |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Comisia •winterchallenge2020 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cmmdcgame
Daenerys si Jon joaca un joc. In acest joc, ei au N orase de cucerit, fiecare oras avand o populatie. Intr-o mutare, unul dintre ei poate ataca cate un oras (Daenerys cu dragoni, Jon cu lupi). Daca un oras are populatia X inainte de atac, dupa atac, aceasta populatie poate fi redusa la orice numar Y < X cu proprietatea ca X si Y sa fie coprime (nu ne intrebati de ce -- asa functioneaza dragonii, respectiv lupii). Cel care nu mai poate ataca niciun oras pierde. Dandu-se mai multe populatii initiale de orase, si presupunand ca Daenerys joaca prima, se cere sa aflati cine castiga (daca se joaca optim).
Date de intrare
Fişierul de intrare cmmdcgame.in contine, pe primul rand, numarul T de teste in fisier. Urmeaza descrierea celor T teste.
Pe primul rand al unei descrieri de test se gaseste numarul N de orase.
Pe al doilea rand al unei descrieri de test se gasesc populatiile oraselor, numere naturale nenule, separate prin spatii.
Date de ieşire
În fişierul de ieşire cmmdcgame.out se vor afisa raspunsurile la cele N teste. Daca castigatorul unui test ar fi Daenarys, se afiseaza D, altfel se afiseaza J.
Restricţii
- Fie SN suma valorilor lui N intr-un fisier de intrare.
- Fie V marimea maxima a oricarui oras intr-un fisier de intrare.
- 1 ≤ T ≤ 300.000
- 1 ≤ SN ≤ 300.000
- 1 ≤ V ≤ 300.000
- Pentru 20 de puncte, V ≤ 1.000 si orasele au populatia numar prim (sau 1).
- Pentru alte 20 de puncte, V ≤ 1.000
- Pentru alte 20 de puncte, orasele au populatia numar prim (sau 1).
Exemplu
| cmmdcgame.in | cmmdcgame.out |
|---|---|
| 2 2 2 3 2 123 123 | D J |
Explicaţie
In cazul primului joc, pentru a castiga, Daenarys trebuie sa atace cel de-al doilea oras, reducandu-i populatia la 2. Apoi, oricare miscare facuta de Jon duce la o situatie cu un oras cu populatia 1, si unul cu populatia 2. Dupa ce Daenarys ataca orasul cu populatia 2, Jon castiga.
In cazul celui de-al doilea joc, Jon poate mereu imita strategia lui Daenarys pe orasul pe care Daenarys nu il ataca. Astfel Jon castiga.
