.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » pic

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
pic


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
15 MB/1 MB

Un grup de cercetatori pleaca într-o expeditie în Oceanul Pacific. Dupa o furtuna puternica ramân fara apa. Desi se aflau într-o situatie grea norocul vine pe neasteptate printr-o ploaie torentiala. Toate vasele existente pe vapor sunt scoase si umplute cu apa. Fiecare vas în care se retine apa de ploaie dispune de un dispozitiv care contorizeaza picaturile de apa. Dupa ce se termina ploaia, apa strânsa este mutata în butoaiele (toate goale) existente pe vapor.
Apa de ploaie s-a strâns în n vase. Dupa ploaie se stie ca fiecare vas i contine un numar de xi picaturi (calculate de dispozitivele de contorizare), 1<=i <=n. Pe vas exista k butoaie, în fiecare butoi i se pot pune vi picaturi, 1<=i<= k.

Cerinta

Sa se determine numarul maxim de butoaie care se pot umple.

Date de intrare

Fisierul de intrare pic.in are urmatoarea structura:
- pe prima linie numarul n
- urmeaza n linii; pe cea de-a i-a linie dintre cele n se afla cifrele lui xi precedate de numarul de cifre (toate separate între ele prin câte un spatiu).
- pe linia n+2 se afla numarul k
- urmeaza k linii; cea de-a i-a linie dintre cele k contine cifrele lui vi precedate de numarul de cifre (toate separate între ele prin câte un spatiu).

Date de iesire

Fisierul pic.out va contine o linie pe care se afla numarul maxim de butoaie care se pot umple.

Restrictii

  • n -numar natural nenul <70
  • xi -numar natural nenul <1022, 1<=i<=n
  • k -numar natural nenul <40
  • vi-numar natural nenul <1022, 1<=i<=k

Exemple

pic.in

pic.out

4
1 5
2 1 0
2 2 0
1 7
3
2 3 0
3 4 0 0
2 1 1

2

prof. Doru Popescu Anastasiu
C.N. "Radu Greceanu" Slatina
Contact: dopopan at yahoo.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor