Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | comun.in, comun.out | Sursă | ONI 2019, clasa a 9-a, ziua 1 |
| Autor | Lucian Bicsi | Adăugată de |  Alex Enache •Alex18mai |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Comun
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ţă
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
- Toate valorile din fişierul de intrare sunt numere naturale nenule mai mici sau egale cu 100000.
- 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.
Exemplu
| comun.in | comun.out | Explicaţie |
|---|---|---|
| 5 1 2 4 6 7 | 3 4 6 7 | 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. |
| 4 2 4 8 16 | 4 2 4 8 16 | Nu există niciun şir de mai puţin de 4 elemente cu proprietatea cerută. |
