Fişierul intrare/ieşire: | abx.in, abx.out | Sursă | OJI 2019, clasa a 9-a |
Autor | Nistor Eugen Mot | Adăugată de | |
Timp execuţie pe test | 0.5 sec | Limită de memorie | 256000 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Abx
Un număr natural n se numește putere dacă există două numere naturale a, b, a ≥ 1, b ≥ 2 astfel încât n = ab. De exemplu, numerele 32, 169, 1 sunt puteri (32 = 25, 169 = 132, 1 = 12), iar 72, 2000 și 31 nu sunt puteri.
Se citesc numerele naturale N, M și un șir de N numere naturale x1, x2, ..., xN din intervalul [1, M].
Pentru fiecare din cele N numere xi determinați câte un număr natural ri din intervalul [1, M], cu proprietatea că ri este o putere și pentru orice altă putere p din intervalul [1, M] este îndeplinită condiția |xi – ri| ≤ |xi – p|, unde |x| reprezintă valoarea absolută a lui x (modulul).
Dacă există două puteri egal depărtate de xi se va alege puterea cea mai mică. De exemplu pentru numărul 26, dintre puterile 25 și 27 va fi ales numărul 25.
Date de intrare
Fișierul de intrare abx.in conține pe prima linie două numere N și M, iar pe fiecare dintre următoarele N linii se găsește câte un număr natural xi (1 ≤ i ≤ N), cu semnificația de mai sus. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.
Date de ieșire
Fișierul de ieșire abx.out va conține N linii, pe fiecare linie i (1 ≤ i ≤ N) aflându-se numărul natural ri cu semnificația din enunț.
Restricții și precizări
- 1 ≤ N ≤ 5000
- 10 ≤ M ≤ 1018
- Pentru teste valorând 40 de puncte M ≤ 5000
- Pentru teste valorând 70 de puncte M ≤ 109
- 10 puncte sunt din oficiu (corespund unor teste egale cu exemplul).
Exemplu
abx.in | abx.out | Explicație |
---|---|---|
8 1000 345 99 999 500 123 124 99 256 | 343 100 1000 512 121 125 100 256 | 343 = 73 100 = 102 1000 = 103 512 = 29 121 = 112 125 = 53 100 = 102 256 = 28 |