Editing 3045 - Pro 3

Se consideră 3 progresii aritmetice de numere naturale nenule. Notăm cu <code>Pi</code>, <code>1 ≤ i ≤ 3</code>, mulțimile formate cu elementele progresiei <code>i</code>. Fie <code>P = P1</code>  <code>P2</code>  <code>P3</code> reuniunea mulțimilor <code>P1</code>, <code>P2</code>, <code>P3</code>.

= Cerința =
Să se determine cardinalul mulțimii <code>P</code>.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține <code>3</code> linii. Pe linia <code>i</code>, <code>1 ≤ i ≤ 3</code> se vor găsi câte trei numere naturale <code>ai</code>, <code>ri</code>, <code>ni</code>, separate prin câte un spațiu, ce reprezintă în această ordine primul termen, rația și numărul de termeni ai progresiei <code>Pi</code>.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține pe prima linie cardinalul mulțimii <code>P</code>.

== Exemplu ==
input.txt:

2 2 10

3 4 8

1 3 12

output.txt:

24

Explicație:

Prima progresie are primul termen <code>2</code>, rația <code>2</code> și <code>10</code> termeni.

A doua progresie are primul termen <code>3</code>, rația <code>4</code> și <code>8</code> termeni.

A treia progresie are primul termen <code>1</code>, rația <code>3</code> și <code>12</code> termeni.

Așadar:

<code>P1</code> <code>= {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}</code>

<code>P2</code> <code>= {3, 7, 11, 15, 19, 23, 27, 31}</code>

<code>P3</code> <code>= {1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34}</code>

Reuniunea termenilor celor trei progresii este mulțimea

<code>P = {1, 2, 3, 4, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 22, 23, 25, 27, 28, 31, 34}</code> și cardinalul mulțimii <code>P</code> este <code>24</code>.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
class Progresie:
    def __init__(self, first, ratio, n):
        self.first = first
        self.ratio = ratio
        self.n = n

def read():
    with open("input.txt", "r") as f:
        x_values = list(map(int, f.readline().split()))
        y_values = list(map(int, f.readline().split()))
        z_values = list(map(int, f.readline().split()))
    
    return Progresie(*x_values), Progresie(*y_values), Progresie(*z_values)

def cmmdc(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def cmmmc(a, b):
    return a * b // cmmdc(a, b)

def calc(a, b):
    Maxa = a.first + a.ratio * (a.n - 1)
    Maxb = b.first + b.ratio * (b.n - 1)
    Min = min(Maxa, Maxb)
    for i in range(int(1e6)):
        nr = a.first + i * a.ratio
        if nr >= b.first and nr <= Min and (nr - b.first) % b.ratio == 0:
            return Progresie(nr, cmmmc(a.ratio, b.ratio), (Min - nr) // cmmmc(a.ratio, b.ratio) + 1)
    return Progresie(0, 0, 0)

def solve(x, y, z):
    xy = calc(x, y)
    xz = calc(x, z)
    yz = calc(y, z)
    xyz = calc(xy, z)
    return x.n + y.n + z.n - xy.n - xz.n - yz.n + xyz.n

def output(rez):
    with open("output.txt", "w") as g:
        g.write(str(rez))

if __name__ == "__main__":
    x, y, z = read()
    rez = solve(x, y, z)
    output(rez)

</syntaxhighlight>