2960 - Abx - Revision history

Corjuc Eunice: Pagină nouă: Un număr natural `n` se numește putere dacă există două numere naturale `a`, `b`, `a ≥ 1`, `b ≥ 2` astfel încât . De exemplu, numerele `32` , `169` , `1` sunt puteri ( , , ), iar `72` , `2000` și `31` nu sunt puteri. Se citesc numerele naturale `N` , `M` și un șir de `N` numere naturale din intervalul
2024-01-04T03:36:03Z

Pagină nouă: Un număr natural <code>n</code> se numește putere dacă există două numere naturale <code>a</code>, <code>b</code>, <code>a ≥ 1</code>, <code>b ≥ 2</code> astfel încât . De exemplu, numerele <code>32</code> , <code>169</code> , <code>1</code> sunt puteri ( , , ), iar <code>72</code> , <code>2000</code> și <code>31</code> nu sunt puteri. Se citesc numerele naturale <code>N</code> , <code>M</code> și un șir de <code>N</code> numere naturale din intervalul <c...

New page
Un număr natural <code>n</code> se numește putere dacă există două numere naturale <code>a</code>, <code>b</code>, <code>a ≥ 1</code>, <code>b ≥ 2</code> astfel încât . De exemplu, numerele <code>32</code> , <code>169</code> , <code>1</code> sunt puteri ( , , ), iar <code>72</code> , <code>2000</code> și <code>31</code> nu sunt puteri.

Se citesc numerele naturale <code>N</code> , <code>M</code> și un șir de <code>N</code> numere naturale din intervalul <code>[1,M]</code>.

= Cerința =
Pentru fiecare din cele <code>N</code> numere determinați câte un număr natural din intervalul <code>[1,M]</code>, cu proprietatea că este o putere și pentru orice altă putere <code>p</code> din intervalul <code>[1,M]</code> este îndeplinită condiția , unde <code>|x|</code> reprezintă valoarea absolută a lui <code>x</code> (modulul).

Dacă există două puteri egal depărtate de se va alege puterea cea mai mică. De exemplu pentru numărul <code>26</code>, dintre puterile <code>25</code> și <code>27</code> va fi ales numărul <code>25</code>.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie două numere <code>N</code> și <code>M</code>, iar pe fiecare dintre următoarele <code>N</code> linii se găsește câte un număr natural (<code>1 ≤ i ≤ N</code>), 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 <code>output.txt</code> va conține <code>N</code> linii, pe fiecare linie <code>i</code> (<code>1 ≤ i ≤ N</code>) aflându-se numărul natural cu semnificația din enunț.

= Restricții și precizări =

* 1<=n<=5000
* 10<=m<=10^18

== Exemplul 1 ==
input.txt:

8 1000

345

99

999

500

123

124

99

256

output.txt:

343

100

1000

512

121

125

100

256

Explicație:

343 = 7^3

100 = 10^2

1000 = 10^3

512 = 2^9

121 = 11^2

125 = 5^3

100 = 10^2

256 = 2^8

== Exemplul 2 ==
input.txt:

999999999999 1000

345

99

999

500

123

124

99

256

Output:

Error: n is not within the valid range (1 <= n <= 5000)

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import math
import sys

def verify_constraints(n, m):
if not (1 <= n <= 5000):
sys.exit("Error: n is not within the valid range (1 <= n <= 5000)")

if not (10 <= m <= 10**18):
sys.exit("Error: m is not within the valid range (1 <= m <= 10^18)")

def lgput(x, y):
ans = 1
aux = x
p = 1
while p <= y:
if y & p:
ans = aux
aux = aux
p <<= 1
return ans

def cautb(x, put):
st = 1
dr = int(x ** (1 / put))
while st <= dr:
mij = (st + dr) // 2
if lgput(mij, put) > x:
dr = mij - 1
else:
st = mij + 1
return dr

with open("input.txt", "r") as f, open("output.txt", "w") as g:
n, m = map(int, f.readline().split())
verify_constraints(n, m)
a_values = [int(f.readline()) for _ in range(n)]

for a in a_values:
sol = 0
dif = m + 100

for j in range(2, 61):
y = cautb(a, j)
z = lgput(y, j)

if abs(a - z) <= dif and z <= m:
sol = z
dif = abs(a - z)

z = lgput(y + 1, j)

if abs(a - z) < dif and z <= m:
sol = z
dif = abs(a - z)

g.write(str(sol) + "\n")

</syntaxhighlight>