Rezolvare PBinfo #4428

Robotul Vasile s-a angajat la un depozit de pixuri. Aici pixurile sunt ambalate în cutii. Există N tipuri de cutii; într-o cutie de tipul i (1 ≤ i ≤ N) sunt ambalate exact nr[i] pixuri (nr[1] ≤ nr[2] ≤ ... ≤ nr[N]).

În depozit există un număr atât de mare de cutii de fiecare tip încât Vasile poate utiliza oricâte cutii doreşte, de orice tip. Sarcina robotului Vasile este să livreze pixurile comandate de diferite firme de birotică. El nu ştie câte pixuri va avea de livrat la următoarea comandă, dar ştie că vor fi cel mult Vmax pixuri. Ca urmare, pentru a fi eficient, robotul Vasile vrea să îşi pregătească în camera de livrare un număr minim de cutii de pixuri astfel încât să poată livra orice număr de pixuri cuprins între 1 şi Vmax folosind cutiile pregătite, evident, fără a deschide cutiile.

Cerința

Scrieţi un program care citeşte valorile N, nr[1], nr[2], … nr[N] şi Vmax și determină numărul minim de cutii pe care robotul Vasile trebuie să le pregătească în camera de livrare astfel încât să poată livra orice număr de pixuri cuprins între 1 şi Vmax, fără a deschide nicio cutie.

Date de intrare

Fișierul de intrare pix.in conține pe prima linie numărul natural N reprezentând numărul de tipuri de cutii. Pe a doua linie se află N numere naturale în ordine crescătoare, separate prin câte un spaţiu, nr[1], nr[2], …, nr[N] reprezentând numărul pixuri ambalate în fiecare tip de cutie. Pe a treia linie se află numărul natural Vmax cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire pix.out va conține o singură linie pe care va fi scris un număr natural reprezentând numărul minim de cutii pe care robotul Vasile trebuie să le pregătească în camera de livrare astfel încât să poată livra orice număr de pixuri cuprins între 1 şi Vmax.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 1 ≤ Vmax, nr[i] ≤ 1012, pentru 1 ≤ i ≤ N
• Se garantează că pentru toate datele de test există soluție.
• Pentru 20 de puncte, 1 ≤ N < 15
• Pentru 10 de puncte, 15 ≤ N < 600
• Pentru 40 de puncte, Vmax ≤ 100.000

Exemplu:

pix.in

4
1 2 3 5
15

pix.out

5

Explicație

Numărul minim de cutii pe care trebuie să le pregătească Vasile este 5 (o cutie de tipul 1, două de tipul 2 şi două de tipul 4, numărul de pixuri din aceste cutii fiind 1, 2, 2, 5, 5)
El poate astfel livra orice număr de pixuri între 1 şi 15, o modalitate posibilă fiind:
1: cutia de tip 1
2: o cutie de tip 2
3: o cutie de tip 1 şi o cutie de tip 2
4: două cutii de tip 2
5: o cutie de tip 4
6: o cutie de tip 1 şi o cutie de tip 4
7: o cutie de tip 2 și o cutie de tip 4
8: câte o cutie de tipurile 1, 2, 4
9: o cutie de tip 4 şi două cutii de tip 2
10: două cutii de tip 4
11: două cutii de tip 4 şi o cutie de tip 1
12: două cutii de tip 4 şi o cutie de tip 2
13: două cutii de tip 4, o cutie de tip 2 şi o cutie de tip 1
14: două cutii de tip 4 şi două cutii de tip 2
15: toate cutiile
Aceasta nu este singura posibilitate de a alege un număr minim de cutii pentru a obține toate valorile de la 1 la 15.