| 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
La o competitie sportivo-matematica denumita sugestiv "Progresii pentru toti" participa N concurenti. Pista pe care alearga acestia este dreapta si are lungimea de L metri. Pentru fiecare concurent i se cunoaste pozitia Pi de la care isi incepe alergarea, relativ cu capatul de start al pistei. Fiecare alergator poate alerga cu o viteza constanta intre 1 metru/secunda si M metri/secunda. Astfel, daca alergatorul i alearga cu vi metri/secunda, la secunda j el se va afla la pozitia Pi + vi * j. Deoarece caldura din ziua competitiei este inabusitoare, fiecare concurent bea un decilitru de suc energizant la fiecare secunda alergata pe pista.
Pentru ca este o competitie in scopuri caritabile, organizatorii doresc sa stranga un profit cat mai mare. De aceea ei doresc sa stabileasca pentru fiecare alergator viteza cu care trebuie sa alerge astfel incat cantitatea de suc energizant care este bauta in total de cei N alergatori sa nu depaseasca valoarea de K decilitri. Daca exista mai multe solutii se va afisa cea minim lexicografica.
Date de intrare
Fisierul de intrare progresii.in contine pe prima linie, separate printr-un spatiu, numerele naturale N, M, K si L, avand semnificatia din enunt. Fiecare din urmatoarele N linii contine cate un numar natural. Astfel, pe linia i+1 se va afla Pi, pozitia de start a alergatorului cu numarul i.
Date de iesire
Fisierul de iesire progresii.out va contine N linii. Pe a i-a dintre aceste linii va fi scris numarul natural vi, viteza cu care alearga concurentul cu numarul i din fisierul de intrare. Daca nu exista solutie, fisierul de iesire va contine o singura linie pe care se va afla doar numarul -1. Daca exista mai multe solutii se va afisa cea minim lexicografica.
Restrictii
- 1 ≤ N ≤ 100 000
- 1 ≤ M, Pi ≤ 2 000 000 000
- 1 ≤ K, L ≤ 260
- Pot exista doi alergatori cu aceeasi pozitie de start
- Pozitiile de start si vitezele cu care alearga participantii la competitie sunt numere naturale
- Un sir de viteze (X1,X2...XN) este mai mic din punct de vedere lexicografic decat un alt sir (Y1,Y2...YN) daca exista o pozitie p astfel incat Xp < Yp si X1 = Y1, X2 = Y2 ... Xp-1 = Yp-1
Exemplu
| progresii.in | progresii.out |
|---|---|
| 3 3 8 4 1 2 3 | 1 1 2 |
Explicatie
Sunt 3 alergatori care pot bea cel mult 8 decilitri de suc. Viteza unui alergator poate fi de maxim 3 metri/secunda, iar pista masoara 4 metri lungime. Primii doi concurenti vor alerga cu 1 metru pe secunda, in timp ce ultimul va alerga cu 2 metri/secunda. Primul concurent va bea un decilitru de suc in dreptul pozitiilor 1, 2, 3 si 4, dupa care isi termina cursa. Concurentul al doilea va bea cate un decilitru in dreptul pozitiilor 2, 3 si 4. Ultimul concurent va bea un singur decilitru de suc in dreptul pozitiei 3, la momentul 0, deoarece in secunda urmatoare el va termina cursa (se va afla la distanta 5 de capatul din stanga al pistei, care are lungimea 4). In total s-au baut 8 decilitri de suc.
O alta solutie ar fi fost (1, 1, 3), dar aceasta este mai mare din punct de vedere lexicografic.
