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

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()