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 cu i-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

<syntaxhighlight lang="python3" line="1"> 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()

</syntaxhighlight>