Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | progresii.in, progresii.out | Sursă | preONI 2008, Runda finala |
| Autor | Adrian Airinei, Filip Cristian Buruiana | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Progresii
O progresie aritmetica este un sir infinit de numere naturale nenule astfel incat diferenta dintre oricare doi termeni consecutivi din sir este constanta. Astfel, o progresie aritmetica este definita in mod unic de primul termen al sirului si de diferenta dintre doi termeni consecutivi (ratia).
Se dau numerele naturale X, K si M, precum si N progresii pentru care primul termen este cunoscut iar ratia trebuie determinata. Trebuie sa aflam un sir de ratii Q = {Q1, Q2, ..., QN}, unde Qi este ratia pentu progresia ce are primul termen Pi, care sa indeplineasca simultan proprietatile:
- 1 ≤ Qi ≤ M, Qi natural, pentru orice i de la 1 la N
- Numarul de numere mai mici sau egale cu X din toate progresiile este maxim K
Dintre toate sirurile Q ce indeplinesc proprietatile de mai sus trebuie determinat cel minim lexicografic.
Date de intrare
Fisierul de intrare progresii.in contine pe prima linie, separate printr-un spatiu, numerele naturale N, M, K si X, avand semnificatia din enunt. Fiecare din urmatoarele N linii contine cate un numar natural. Astfel, pe linia i+1 se va afla Pi, primul termen al progresiei i.
Date de iesire
Fisierul de iesire progresii.out va contine N linii. Pe a i-a dintre aceste linii va fi scris numarul Qi, ratia progresiei ce are primul termen egal cu Pi. Daca nu exista solutie, fisierul de iesire va contine o singura linie pe care se va afla doar numarul -1.
Restrictii
- 1 ≤ N ≤ 100 000
- 1 ≤ M, Pi ≤ 2 000 000 000
- 1 ≤ K, X ≤ 260
- Un sir (a1,a2...aN) este mai mic din punct de vedere lexicografic decat un alt sir (b1,b2...bN) daca exista o pozitie p astfel incat ap < bp si a1 = b1, a2 = b2 ... ap-1 = bp-1
Exemplu
| progresii.in | progresii.out |
|---|---|
| 3 3 8 4 1 2 3 | 1 1 2 |
Explicatie
Cele 3 progresii vor fi: (1,2,3,4,5,6...), (2,3,4,5,6...) si (3,5,7,9...). Prima progresie contine 4 termeni mai mici sau egali decat 4, a doua contine 3 termeni, iar ultima progresie contine un singur termen. In total sunt 8 termeni mai mici sau egali decat 4. O solutie posibila pentru sirul Q era si Q = {1, 1, 3}, dar aceasta este mai mare din punct de vedere lexicografic.
