B - Al doilea Crack

Time limit: 0.5s Memory limit: 8MB Input: Output:

Cerință

Șmenul lui Aquilla ne ajută să rezolvăm următoarea problemă:

Dacă avem o tablă de șah NN-dimensională, adică avem doar casuțe de culori albe și negre și nu există 22 căsuțe de aceași culoare adiacente, iar în fiecare căsuță este un cărăbuș cu o anumita orientare (daca N=2N=2, aceasta poate fi: sus, jos, stânga, dreapta, deci se poate muta către o căsuță adiacentă).

Putem alege o orientare a cărăbușilor astfel încât dacă se mută toți deodată să nu se ajungă cu 22 sau mai mulți cărăbuși pe aceași căsuță (orientarea trebuia aleasă ca cărăbușii să nu iasă de pe tablă)?
Să se răspundă la TT teste.

Date de intrare

Pe prima linie se află TT, urmat de TT linii, pe fiecare se află câte un NN.

Date de ieșire

Se cer NN rânduri, răspunsul poate fii DA sau NU.

Restricții și precizări

  • 1T1051 \leq T \leq 10^5;
  • 2N1052 \leq N \leq 10^5;
  • Atenție, răspusul este DA sau NU, nu YES sau NO :)
  • O tablă de șah NN dimensională are si laturile de lungime NN. (O tablă 55 dimensională este de 5×5×5×5×55 \times 5 \times 5 \times 5 \times 5).
  • Să fie si mai clar, de exemplu într-o tablă 33 dimensională un cărăbuș se poate mișca: sus, jos, față, spate, stânga, dreapta. Iar pentru N=4N=4 sunt 88 direcții de mișcare.

Exemplul 1

stdin

1
2

stdout

DA

Explicație

T=1T=1.
Avem o tablă de 2×22 \times 2.
Orientările pot fi alese:
Cărăbușul de pe (1,1)(1,1) se mută jos.
Cărăbușul de pe (1,2)(1,2) se mută stânga.
Cărăbușul de pe (2,1)(2,1) se mută dreapta.
Cărăbușul de pe (2,2)(2,2) se mută sus.
Carăbușii se mișcă simulta, după ce se mișcă nu va exista o căsuță cu 22 sau mai mulți cărăbuși.

Exemplul 2

stdin

2
3
16

stdout

NU
DA

Explicație

Tabla este un cub de 3×3×33 \times 3 \times 3, se poate demonstra că nu există soluție.
Tabla este un cub de 16×16×16×16×1616 \times 16 \times 16 \times 16 \times 16..., există o soluție.

Log in or sign up to be able to send submissions!