RebecaBud: Pagină nouă: == 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...

2024-06-03T17:53:09Z

Pagină nouă: == 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...

New page

== 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>

3044 - Comun 1 - Revision history