| Fişierul intrare/ieşire: | referat.in, referat.out | Sursă | Algoritmiada 2016 - Runda 4 - Juniors |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Referat
Dani si prietenii lui Adi, Alex si Ioan au de scris un referat pentru proiectul de la facultate. Acestia au scris in Latex un text format din N cuvinte numerotate de la 1 la N. Pentru fiecare cuvant i se stie lungimea cuvantului: Si. Latex-ul are o limita de L caractere pe rand. Ca urmare, in timp ce scriau textul, daca se aflau la randul X si voiau sa scrie un cuvant nou dar acest cuvant nu mai avea loc pe rand, cuvantul trecea automat pe randul X + 1. Cuvintele sunt scrise unul dupa altul fara spatii (in schimb, ei folosesc litera mare sa fie clar textul). Dupa multa munca, baietii au reusit sa scrie textul in Latex.
Ca in orice poveste care contine cuvantul "facultate", a intervenit o problema. Baietii au uitat sa scrie un cuvant foarte important de lungime P. Partea buna in schimb era ca oricat de important era cuvantul, nu avea relevanta foarte mare unde in text era introdus (corectorii oricum nu isi dadeau seama). Ca urmare, cei 4 baieti s-au decis sa introduca cuvantul undeva astfel incat numarul total de linii sa creasca cu cel putin 1 (cu cat e mai mare proiectul, cu atat pare mai bine facut). Deoarece ei nu o prea au cu informatica, treaba voastra este sa le spuneti in cate locuri distincte pot introduce acestia noul cuvant. Un cuvant poate sa fie introdus la inceputul textului, la sfarsitul textului sau intre 2 cuvinte deja existente din text.
Date de intrare
Fişierul de intrare referat.in va contine pe prima linie N, L si T (numarul de teste). Pe urmatoarea linie vor fi N numere naturale, al i-lea numar este Si, reprezentand lungimea cuvantului i. Pe urmatoarele T linii se va afla cate un numar P, reprezentand lungimea cuvantului pe care dorim sa il inseram in text.
Date de ieşire
Fişierul de ieşire referat.out va contine T linii cu exact un numar natural, reprezentand numarul de pozitii in care poate sa fie introdus noul cuvant astfel incat baietii sa obtina cel putin un rand in plus pentru testul respectiv.
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ T ≤ 10
- 1 ≤ P,Si ≤ L ≤ 1.000.000.000
- Pentru 30% din teste N ≤ 1000
Exemplu
| referat.in | referat.out |
|---|---|
| 5 10 1 7 1 5 2 8 4 | 3 |
Explicatii
Copii au 5 cuvinte de lungime 7, 1, 5, 2, 8, sa zicem urmatoarele cuvinte: Sambata A Venit Cu Beatrice, iar cuvantul pe care vrem sa-l introducem este Rece.
Initial textul pus pe linii de lugime maxim 10 este:
SambataA
VenitCu
Beatrice
In functie de unde introducem cuvantul Rece se obtin urmatoarele distribuiri pe linii:
Rece
SambataA
VenitCu
Beatrice
Sambata
ReceAVenit
CuBeatrice
SambataA
ReceVenit
CuBeatrice
SambataA
VenitRece
CuBeatrice
SambataA
VenitCu
Rece
Beatrice
si
SambataA
VenitCu
Beatrice
Rece
Observam ca doar daca introducem cuvantul Rece la inceput, fix inainte de cuvantul Beatrice, si la final numarul de linii creste cu 1. Astfel raspunsul este 3.
