Fişierul intrare/ieşire:progresii.in, progresii.outSursăpreONI 2008, Runda finala
AutorAdrian Airinei, Filip Cristian BuruianaAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inprogresii.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content