1237 - Numereiajb
Cerinta
Numerele iajb
sunt numerele care pot fi scrise sub forma i * a + j * b
, cu i
și j
numere naturale și i + j > 0
.
Cunoscând a
și b
și un număr n
, să se determine valorile i
și j
pentru care se vor forma primele n
numere iajb
in ordine crescătoare.
Date de intrare
Fișierul de intrare numereiajbIN.txt
conține pe prima linie numărul 3
numere naturale a
, b
și n
, având semnificațiile de mai sus.
Date de ieșire
Fișierul de ieșire numereiajbOUT.txt
va conține pe cele n
linii câte o pereche de numere naturale i
și j
care răspund cerinței. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".
Restricții și precizări
1 ≤ n ≤ 2.000.000
(!)1 ≤ a, b ≤ 50.000
- Dacă un număr
iajb
se obține din perechi diferite de(i, j)
atunci se va afișa doar cea cui
-ul minim
Exemplul 1:
numereiajbIN.txt
2 3 5
numereiajbOUT.txt
1 0 0 1 2 0 1 1 0 2
Explicație
1 * 2 + 0 * 3 = 2
0 * 2 + 1 * 3 = 3
2 * 2 + 0 * 3 = 4
1 * 2 + 1 * 3 = 5
0 * 2 + 2 * 3 = 6
Exemplul 2:
numereiajbIN.txt
2 3 50001
numereiajbOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
def verificare_restrictii(n, a, b):
if not (1 <= n <= 2000000 and 1 <= a <= 50000 and 1 <= b <= 50000):
with open("numereiajbOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return False
return True
def main():
fin = open("numereiajbIN.txt", "r")
fout = open("numereiajbOUT.txt", "w")
n, a, b = map(int, fin.readline().split())
if not verificare_restrictii(n, a, b):
fin.close()
fout.close()
return
Q = [[], []]
Q[0].append((1, 0))
Q[1].append((0, 1))
last = -1
for t in range(1, n + 1):
crt = [Q[j][0][0] * a + Q[j][0][1] * b for j in range(2)]
if crt[0] < crt[1]:
i, j = Q[0].pop(0)
nr = crt[0]
else:
i, j = Q[1].pop(0)
nr = crt[1]
if nr == last:
t -= 1
continue
last = nr
fout.write(f"{i} {j}\n")
Q[0].append((i + 1, j))
Q[1].append((i, j + 1))
fin.close()
fout.close()
if __name__ == "__main__":
main()