Editing 1237 - Numereiajb

== Cerinta ==

Numerele <code>iajb</code> sunt numerele care pot fi scrise sub forma <code>i * a + j * b</code>, cu <code>i</code> și <code>j</code> numere naturale și <code>i + j > 0</code>.

Cunoscând <code>a</code> și <code>b</code> și un număr <code>n</code>, să se determine valorile <code>i</code> și <code>j</code> pentru care se vor forma primele <code>n</code> numere <code>iajb</code> in ordine crescătoare.

= Date de intrare =
Fișierul de intrare <code>numereiajbIN.txt</code> conține pe prima linie numărul <code>3</code> numere naturale <code>a</code>, <code>b</code> și <code>n</code>, având semnificațiile de mai sus.

= Date de ieșire =
Fișierul de ieșire <code>numereiajbOUT.txt</code> va conține pe cele <code>n</code> linii câte o pereche de numere naturale <code>i</code> și <code>j</code> 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 =

* <code>1 ≤ n ≤ 2.000.000</code> (!)
* <code>1 ≤ a, b ≤ 50.000</code>
* Dacă un număr <code>iajb</code> se obține din perechi diferite de <code>(i, j)</code> atunci se va afișa doar cea cu <code>i</code>-ul minim

= Exemplul 1: =
<code>numereiajbIN.txt</code>
 2 3 5
<code>numereiajbOUT.txt</code>
 1 0
 0 1
 2 0
 1 1
 0 2

== Explicație ==
<code>1 * 2 + 0 * 3 = 2</code>

<code>0 * 2 + 1 * 3 = 3</code>

<code>2 * 2 + 0 * 3 = 4</code>

<code>1 * 2 + 1 * 3 = 5</code>

<code>0 * 2 + 2 * 3 = 6</code>

== Exemplul 2: ==
<code>numereiajbIN.txt</code>
 2 3 50001
<code>numereiajbOUT.txt</code>
 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>