Fişierul intrare/ieşire:zapada2.in, zapada2.outSursăOlimpiada pe scoala 2017 clasele a 11-a si a 12-a
AutorVictor ManzAdăugată devmanzVictor Manz vmanz
Timp execuţie pe test0.2 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Zapada2 (clasele 11-12)

După cum spune o vorbă din bătrâni, ”iarna nu-i ca vara” şi din când în când mai şi ninge. În această iarnă, în frumoasa noastră capitală s-a strâns o cantitate mare de zăpadă, care este adunată în N mormane cu volumele v(1), v(2), ..., v(N) metri cubi. Primăria şi-a propus să strângă toată zăpada. Pentru asta are la dispoziţie M buldozere care pot ridica într-o noapte (ziua traficul îngreunează operaţiunea) câte c(1), c(2), ..., respectiv c(M) metri cubi de zăpadă. Pentru că doreşte să ajungă la costuri cât mai mici şi asta înseamnă să folosească un număr cât mai mic de buldozere, primăria ar vrea să ştie dacă poate rezolva problema zăpezii într-o singură noapte şi care e numărul minim de buldozere necesare.

Cerinţă

Scrieţi un program care răspunde la întrebarea pusă de primărie pe baza datelor de intrare.

Date de intrare

Fişierul de intrare zapada2.in conţine pe prima linie un număr natural nenul N, pe cea de-a doua linie N numere naturale nenule separate prin câte un spaţiu, reprezentând volumele mormanelor de zăpadă, pe a treia linie M reprezentând numărul de buldozere, iar pe cea de-a patra linie, M numere naturale nenule separate prin câte un spaţiu.

Date de ieşire

În fişierul de ieşire zapada2.out se va afla un singur număr P, reprezentând numărul minim de buldozere necesare.

Restricţii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ M ≤ 100 000
  • 1 ≤ v(i) ≤ 100 000 pentru orice 1 ≤ i ≤ N
  • 1 ≤ c(i) ≤ 100 000 pentru orice 1 ≤ i ≤ M
  • dacă buldozerele disponibile nu pot încărca toată zăpada într-o singură noapte, atunci în fişierul de ieşire se va scrie -1
  • un buldozer poate să încarce zăpada din 1 sau mai multe mormane

Exemplu

zapada2.inzapada2.out
2
10 16
4
20 1 3 4
3
2
20 16
4
20 1 3 4
-1

Explicaţie

Pentru primul exemplu, se pot folosi buldozerele 1, 3 şi 4, de capacităţi 20, 3 şi 4. Ultimul buldozer nu va fi folosit la capacitate maximă.
Pentru cel de-al doilea exemplu, buldozerele disponibile nu pot încărca într-o noapte întreaga cantitate de zăpadă.

Trebuie sa te autentifici pentru a trimite solutii. Click aici