Թաքցնել տուփերը
Տրված է
n տուփ։ Ձեր խնդիրն է հնարավորինս շատ տուփեր տեղադրել այլ, ավելի մեծ տուփերի մեջ։ Սակայն պետք է մի քանի պայմաններ պահպանվեն.- Փոքր տուփը կարելի է դնել մեկ այլ, մեծ տուփի մեջ միայն այն դեպքում, երբ մեծ տուփի չափը առնվազն կրկնակի մեծ է փոքր տուփի չափից:
- Ամեն մի տուփի մեջ կարելի է տեղադրել միայն մեկ այլ տուփ (չի կարելի մեկ տուփի մեջ տեղադրել մեկից ավելի տուփեր):
Ո՞րն է տեսանելի տուփերի նվազագույն հնարավոր քանակը:
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ ), որը ցույց է տալիս տուփերի քանակը։Հաջորդ տողում տրված են
n բացատով բաժանված ամբողջ թվեր (1 ≤ ≤ ), որոնք ցույց են տալիս յուրաքանչյուր տուփի չափը:Ելք
Ծրագիրը պետք է տպի տեսանելի տուփերի նվազագույն հնարավոր քանակը:
Օրինակներ
Input | Output |
8
7 5 2 6 4 8 9 2 | 5 |
8
3 1 8 2 6 5 6 9 | 5 |
Բացատրություն
- 7 5 2 6 4 8 9 2 → (2, 5) (2, 6) (7) (4, 8) (9)
- 3 1 8 2 6 5 6 9 → 1 2 3 5 6 6 8 9 → (1, 5) (2, 6) (3, 6) (8) (9)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB