Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | cmmmc.in, cmmmc.out | Sursă | ONI 2010, clasa a 9-a |
| Autor | Stelian Ciurea | Adăugată de |  Gavrila Vlad •GavrilaVlad |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 6144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cmmmc
Definim noţiunea de pereche ordonată, perechea de numere naturale (x, y) cu x ≤ y. Definim cel mai mic multiplu comun al unei perechi ordonate ca fiind cel mai mic multiplu comun al numerelor care formează perechea.
Se dau k numere naturale n1, n2, ..., nk.
Cerinţă
Să se determine pentru fiecare dintre numerele ni ∈ (i = 1, 2, ..., k):
a) câte perechi ordonate au cel mai mic multiplu comun egal cu ni.
b) dintre acestea, perechea ordonată care are suma minimă.
Date de intrare
Prima linie a fişierului cmmmc.in conţine un număr natural k. Următoarele k linii din acest fişier vor conţine câte un număr natural; linia i+1 va conţine numărul ni ∈ (i = 1 ,2 , ..., k).
Date de ieşire
Fişierul cmmmc.out va conţine k linii. Pe fiecare dintre acestea se vor afla trei numere. Cele trei numere de pe linia i vor reprezenta:
- primul, numărul de perechi ordonate care au cel mai mic multiplu comun egal cu ni;
- următoarele două, numerele care alcătuiesc perechea ordonată care are cel mai mic multiplu comun egal cu ni şi a căror sumă este minimă, afişate în ordine crescătoare.
Restricţii şi precizări
- 1 ≤ k ≤ 100
- 1 ≤ ni ≤ 2 000 000 000
- Pentru 20% dintre teste, k ≤ 100 şi ni ≤ 1000.
- Fiecare dintre cele k linii ale fişierului cmmmc.out trebuie să conţină exact trei numere separate prin câte un spaţiu; în caz contrar, soluţia se consideră greşită şi se obţin 0 puncte pentru testul respectiv. Rezolvarea corectă a cerinţei a) valorează 40% din punctajul unui test iar rezolvarea corectă a cerinţei b) 60%.
Exemplu
| cmmmc.in | cmmmc.out |
|---|---|
| 2 10 11 | 5 2 5 2 1 11 |
Explicaţie
Există cinci perechi distincte care au cel mai mic multiplu comun egal cu 10: (1, 10), (2, 10), (5, 10), (2, 5) si (10, 10). Dintre acestea perechea cu cea mai mică sumă este (2, 5).
Pentru n = 11 există două perechi ordonate care au cel mai mic multiplu comun 11: (1, 11), (11, 11). Dintre acestea perechea cu cea mai mică sumă este (1, 11).
