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.

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ă.

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>