## TLE '16 Contest 4 P1 - Stack of Presents

View as PDF

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
A stack of presents.

The CS Nerd is dreaming about giving Christmas presents to the girl. Unfortunately, he does not have enough courage to do this in real life.

In the dream, there are presents that he could possibly give to the girl. The present has a weight of . The CS Nerd wants to impress the girl by building a large stack of presents – that is, presents stacked one on top of each other – and giving it to her.

However, the CS Nerd needs to ensure that the sum of the weights of the presents above any present does not exceed that present's weight. What is the maximum number of presents that can be in the stack?

#### Input Specification

The first line of input will contain a single integer .

lines of input follow. The line will consist of a single integer, .

For 20% of the points, .

For an additional 30% of the points, .

#### Output Specification

Output a single integer, the maximum possible number of presents that can be in the stack.

#### Sample Input

5
7
8
2
5
10

#### Sample Output

3

#### Explanation for Sample Output

The CS Nerd can stack presents in the order , , and from the bottom. The weights of these presents are , , and , respectively. Note that this is not the only possible solution.

• commented on Dec. 24, 2016, 8:44 a.m.

If the weights of the presents on top the stack is equal to the weight on the bottom, does it count as a valid stack?

• commented on Dec. 24, 2016, 9:24 a.m.

Yes

• commented on Dec. 23, 2016, 12:27 p.m.

However, the CS Nerd needs to ensure that the sum of the weights of the presents above any present does not exceed that present’s weight. What is the maximum number of presents that can be in the stack? I can't understand this statement.

• commented on Dec. 23, 2016, 12:30 p.m.

The sum of the weights of the presents on top of the current present in consideration cannot exceed the weight of the current present.