Mock CCO '17 Problem 1 - Fast Fuhrer Transform

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

imaxblue

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 $N$ ~N~ security levels in the Amestris government, numbered $0$ ~0~ to $N-1$ ~N-1~. 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 $0$ ~0~, 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 $(N-1)^\text{th}$ ~(N-1)^\text{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.

Subtasks

For all cases, $N \le 200\,000$ ~N \le 200\,000~.
For 5 of the 25 points, $N \le 4\,000$ ~N \le 4\,000~.

Input Specification

On the first line: $N$ ~N~
On the second line: $N$ ~N~ integers, representing the security cards available for purchase on the $i^\text{th}$ ~i^\text{th}~ day.

Sample Input

9
1 2 5 4 2 3 10 1 1

Sample Output

Explanation for Sample Output

First, purchase the card of value $1$ ~1~, raising your security level to $1$ ~1~.
Then, purchase the card of value $2$ ~2~, raising your level to $3$ ~3~.
Then, purchase the card of value $4$ ~4~, raising your level to $7$ ~7~.
Then, purchase the card of value $5$ ~5~, raising your level to $12$ ~12~.

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.

Comments

0

DarthVader336 commented on April 12, 2018, 2:26 p.m. ← edited →

Why cannot imaxblue buy the card of value 10?

2

aeternalis1 commented on April 12, 2018, 2:37 p.m. ← edited →

Upon purchasing the card of value 5, he'd already surpassed the $N-1$ ~N-1~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.

0

DarthVader336 commented on April 13, 2018, 4:06 a.m. ← edited →

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

0

DarthVader336 commented on April 13, 2018, 4:05 a.m. ← edited →

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

2

Roynaruto commented on April 13, 2018, 12:21 p.m. ← edit 2 →

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