Atenţie! Aceasta este ultima versiune a paginii, scrisă la 2008-11-15 16:19:43.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:caluti.in, caluti.outSursăStelele Informaticii 2006, clasele 11-12
AutorAdrian VladuAdăugată debogdan2412Bogdan-Cristian Tataroiu •bogdan2412
Timp execuţie pe test0.25 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Caluti

Fermierul Chernel are o mare problema. Trebuie sa transporte N caluti de la pasune la hambar. Pentru aceasta el foloseste un camion in care incap maxim K caluti pentru un transport. Timpul in care Chernel efectueaza un transport de la pasune la hambar si se intoarce la pasune cu camionul gol este P.

Insa calutii zburdalnici sunt greu de convins sa intre in camion inainte de o anumita ora. Pentru fiecare calut i se cunoaste timpul Ti dupa care acesta va putea fi bagat in camion. Chernel doreste sa isi termine munca cat mai repede, altfel spus ar vrea sa minimizeze timpul dupa care toti calutii vor fi fost transportati la hambar iar el ajuns cu camionul inapoi la pasune.

Cerinta

Ajutati-l pe Chernel sa isi indeplineasca dificila sarcina de a transporta toti calutii in timp minim.

Date de intrare

Prima linie a fisierului de intrare caluti.in contine un numar natural T, reprezentand numarul de teste. Pe urmatoarele linii sunt descrise cele T teste, fiecare dintre ele avand formatul urmator: pe prima linie se afla trei numere intregi N, K si P, iar pe urmatoarele N linii se afla timpii Ti ai calutilor, sortati crescator.

Date de iesire

Fisierul de iesire caluti.out va contine T linii. Pe linia i se va afla un singur numar intreg, reprezentand timpul minim de transport al calutilor corespunzator testului i din fisierul de intrare.

Restrictii

  • 1 ≤ T ≤ 10
  • 1 ≤ K ≤ N ≤ 100 000
  • 1 ≤ P ≤ 10 000 000 000
  • 1 ≤ Ti ≤ 10 000 000 000
  • Pentru 40% din teste N ≤ 500

Exemplu

caluti.incaluti.out
1
3 2 15
10
20
30
45

Explicatie

Chernel incarca primul calut la timpul 10, il transporta la hambar si ajunge inapoi la pasune la timpul 25.
Asteapta pana la momentul 30, apoi incarca al doilea si al treilea calut, pe care ii transporta la hambar, intorcandu-se apoi la pasune la timpul 45.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content