Fişierul intrare/ieşire:cmmdcgame.in, cmmdcgame.outSursăWinter Challenge 2020
AutorTamio-Vesa NakajimaAdăugată dewinterchallenge2020Comisia winterchallenge2020
Timp execuţie pe test0.3 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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.incmmdcgame.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?