Fişierul intrare/ieşire:cardinal.in, cardinal.outSursăGrigore Moisil 2018, 9
AutorVlad MihalyAdăugată degrigore.moisilGrigore Moisil grigore.moisil
Timp execuţie pe test0.3 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cardinal

Doi prieteni se joacă un joc pe o suprafaţă sub formă de pătrat infinit care este împărţită în pătrăţele unitate. Jocul decurge astfel: într-un pătrăţel oarecare se plasează primul jucător, iar celălalt îi spune un număr natural nenul N. Jucătorul de pe tablă este nevoit să ajungă din nou în poziţia iniţială efectuând în prima fază un pas pe verticală (sus sau jos), apoi doi paşi pe orizontală (stânga sau dreapta), trei pe verticală (sus sau jos), ..., până ajunge să facă N paşi într-o singură tură. Din păcate nu orice joc se poate finaliza, iar jucătorul de pe tablă nu vrea să facă încercări inutile. 

Deoarece jucătorul nu se prea descurcă la găsirea traseului, vă roagă să îl ajutaţi să găsească un traseu bun sau să îi spună celuilalt dacă acest lucru este imposibil.

Date de intrare

Fişierul de intrare cardinal.in conţine pe prima linie un număr natural nenul Q, reprezentând numărul de jocuri desfăşurate. Fiecare din următoarele Q linii conţine câte un număr N cu semnificaţia din enunţ.

Date de ieşire

Fişierul de ieşire cardinal.out trebuie să conţină răspunsurile pentru cele Q jocuri, fiecare pe câte o linie. Dacă al i-lea joc se poate finaliza, atunci linia i va conţine o secvenţă de litere din mulţimea {U, D, L, R}, fiecare literă semnificând o mutare a jucătorului în sus (up), jos (down), stânga (left) respectiv dreapta (right). În caz contrar, linia i va conţine cuvântul IMPOSIBIL.

Restricţii

  • 1 <= N <= 100 000.
  • 1 <= Q <= 10.
  • Pentru teste în valoare de 10 de puncte N <= 10.
  • Problema va fi evaluată pe teste în valoare de 90 de puncte.
  • Exemplul va reprezenta teste în valoare de 10 puncte "din oficiu".

Exemplu

cardinal.incardinal.out
2
8
3
URDLDLUR
IMPOSIBIL

Explicaţie

În primul joc, următoarea secvenţă de mutări duce jucătorul în celula de unde a pornit:

  • 1 pas în sus
  • 2 paşi la dreapta
  • 3 paşi în jos
  • 4 paşi la stânga
  • 5 paşi in jos
  • 6 paşi la stânga
  • 7 paşi în sus
  • 8 paşi la dreapta

În cel de-al doilea joc este imposibil ca jucătorul să revină în celula iniţială după 3 mutări.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?