Editing 3044 - Comun 1

== Enunt ==
Tocmai ai primit un șir v de K numere naturale nenule distincte. Plecând de la acest șir, te-ai gândit să construiești un șir w de N numere naturale distincte, astfel încât un număr x este în șirul w dacă și numai dacă exista inițial în șirul v sau se pot alege cel puțin două numere din șirul v astfel încât x este cel mai mare divizor comun al acelor numere. De exemplu, dacă v = {4, 6, 7} atunci w = {1, 2, 4, 6, 7}.
Uimit de proprietățile matematice frumoase ale noului șir w, ai uitat din păcate șirul original v de la care ai pornit.
== Cerinţa ==
Dându-se șirul w, să se găsească un șir posibil inițial v având un număr minim de elemente.
== Date de intrare ==
Fișierul de intrare comun.in conține pe prima linie un număr natural N. Pe cea de-a doua linie se află N numere naturale nenule distincte, în ordine strict crescătoare, reprezentând șirul w.
== Date de ieșire ==
Fișierul de ieșire comun.out va conține pe prima linie numărul minim K de elemente ale șirului v. Pe cea de-a doua linie se vor afla K numere naturale distincte, în ordine strict crescătoare, reprezentând șirul propriu-zis.
== Restricţii şi precizări ==
* Toate valorile din fișierul de intrare sunt numere naturale nenule mai mici sau egale cu 100.000.
* Pentru teste în valoare de 15 puncte, toate valorile din fișierul de intrare sunt mai mici sau egale cu 20.
* Pentru teste în valoare de 50 de puncte, toate valorile din fișierul de intrare sunt mai mici sau egale cu 2000.
* Se garantează că există măcar o soluție.
* Dacă există mai multe șiruri inițiale cu număr minim de elemente, oricare este acceptat.
== Exemplul 1 ==
; comun.in

  5
  1 2 4 6 7
; comun.out

  3
  4 6 7
== Explicație ==
1 = cmmdc(6, 7) = cmmdc(4, 6, 7). 2 = cmmdc(4, 6). Se poate demonstra că orice alt șir cu proprietatea cerută are măcar 3 elemente.
<br>

== Exemplul 2 ==
; comun.in

  4
  2 4 8 16
; comun.out

  4
  2 4 8 16
== Explicație ==
Nu există niciun șir de mai puțin de 4 elemente cu proprietatea cerută.
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line>
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def find_initial_sequence(w):
    n = len(w)
    initial_sequence = []
    initial_sequence.append(w[0])
    for i in range(1, n):
        current_gcd = gcd(initial_sequence[-1], w[i])
        if current_gcd != w[i]:
            initial_sequence.append(w[i])
    return initial_sequence

def main():
    with open("comun.in", "r") as f:
        n = int(f.readline())
        w = list(map(int, f.readline().split()))

    initial_sequence = find_initial_sequence(w)

    with open("comun.out", "w") as f:
        f.write(str(len(initial_sequence)) + "\n")
        f.write(" ".join(map(str, initial_sequence)))

if __name__ == "__main__":
    main()

</syntaxhighlight>