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>