## Mock CCO '17 Day 1 P1 - Fast Fuhrer Transform

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Imaxblue has travelled back in time to kill Fuhrer Bradley. Unfortunately, this plan involves infiltrating the Amestris government. This means that he must bribe purchase legal government security cards. There are security levels in the Amestris government, numbered to . There is a new security card available for purchase at each level, and you can purchase cards at lower levels as well. Initially, Imaxblue has a security level of , and his total security level is equal to the sum of his cards. Imaxblue would like to raise as little suspicion as possible, by purchasing the most amount of cards before going past the th security level. In addition, each card he purchases must have a higher security number than the previous one purchased. Print -1 if it is impossible.

For all cases,
For 5 of the 25 points,

#### Input Specification

On the first line:
On the second line: integers, representing the security cards available for purchase on the -th day

#### Sample Input

9
1 2 5 4 2 3 10 1 1

#### Sample Output

4

#### Explanation for Sample Output

First, purchase the card of value , raising your security level to .
Then, purchase the card of value , raising your level to .
Then, purchase the card of value , raising your level to .
Then, purchase the card of value , raising your level to .

Note: you cannot purchase the second card of value 2 or the card of value 3, since the cards you purchase must be strictly increasing.

• commented on April 12, 2018, 10:26 a.m.

Why cannot imaxblue buy the card of value 10?

• commented on April 12, 2018, 10:37 a.m.

Upon purchasing the card of value 5, he'd already surpassed the th security level, and so he couldn't buy any more past that point. It would have been another valid solution to buy the card of value 10 in place of the card of value 5.

• commented on April 13, 2018, 12:06 a.m.

Is it because his security value can beat any of the security cards at every level? (12>10, 12>2 ....)

• commented on April 13, 2018, 12:05 a.m.

How have he surpassed the N-1th security level?

• commented on April 13, 2018, 8:21 a.m.

For help, I recommend you join DMOJ's Slack to prevent spamming on comments.