In bucataria unei
gospodine se afla un teanc format din N
farfurii. Gospodina care urmeaza sa le spele este pusa in fata unei probleme.
Ea cunoaste cat timp dureaza spalarea fiecarei farfurii. De asemenea ea poate
sa renunte la spalarea ei si sa o sparga, insa spargerea dureaza exact un minut,
pentru oricare farfurie. Farfuriile sunt numerotate cu numere de la 1
la N, incepand cu farfuria din
varful teancului spre cea de la baza teancului. Farfuria care poate fi spalata
la un moment dat este cea situata in varful teancului. Initial gospodina poate
spala sau sparge farfuria cu numarul 1,
dupa care poate face acelasi lucru cu farfuria numarul 2,
s.a.m.d. De asemenea, gospodina poate lasa in teanc farfurii nespalate.
Este cunoscut timpul T exprimat
in minute, pe care gospodina il are la dispozitie.
Cerinta
Realizati un program care
determina care este numarul maxim de farfurii pe care le poate spala gospodina
in timpul T dat. Pentru acest
numar maxim de farfurii obtinut, determinati si timpul minim necesar spalarii
lor.
Date de intrare
Fisierul de intrare farfurii.in
contine pe prima linie doua numere naturale N
T separate printr-un spatiu, reprezentand numarul de farfurii si respectiv
timpul avut la dispozitie de gospodina. Pe urmatoarea linie se gaseste un sir
de N numere naturale ts1,
ts2, ..., tsN,
separate prin cate un spatiu, reprezentand timpii de spalare al fiecarei farfurii,
in ordine, incepand cu farfuria 1.
Date de iesire
In fisierul de iesire farfurii.out
se vor scrie pe o singura linie numerele Nmax
si Tmin despartite printr-un spatiu.
Nmax reprezinta numarul maxim de
farfurii pe are le poate spala gospodina in timpul T,
iar Tmin timpul minim de spalarea
lor.
Restrictii
0 < N <= 1000
0 < T <= 10000
0 <= tsi<= 100
Exemplu
farfurii.in
farfurii.out
farfurii.in
farfurii.out
Explicatii
4 4
1 4 1 3
2 3
7 11
10 3 2 1 4 2 4
4 10
Primul
exemplu:
Se spala prima farfurie (1
min), se sparge a doua farfurie (1
min), se spala a treia farfurie (1
min).
Al doilea exemplu:
Se sparg farfuriile 1 si
5 si se spala farfuriile
2, 3,
4 si 6.
(Tmin=1+3+2+1+1+2=10)
prof. Dana Lica
Colegiul National “Ion Luca Caragiale” Ploiesti
Contact: danal182001@yahoo.com