wip

83. Growth

Time Limit: 1 seconds

Memory Limit: 1024 MB

Rating: 1000

In another world of snakes, the apples can have different sizes! In fact, most of the apples are larger than the snake's mouth. The snake can only eat apples with size less than or equal to the size of its mouth. However, the snake has the ability to grow. After eating an apple with size $k$, the size of the snake’s mouth increases by $k$. For example, if the snake’s mouth is currently size 5, after eating an apple of size 3, the snake’s mouth is now size 8. The snake can now eat apples with size less than or equal to 8. The snake begins with a mouth of size 1.

You are first given an integer $n$, the number of apples available. Next, you are given an array of apple sizes. (the array will contain $n$ elements) Determine the maximum number of apples the snake can eat. The apples can be eaten in any order.

Output the answer.

Sample Input 1:
7
1 1 6 1 1 24 1

Sample Output 1:
6


Sample Input 2:
6
1 2 7 4 11 27

Sample Output 2:
5


Sample Input 3:
9
138 53 2 1 19 3 1 6 1

Sample Output 2:
6

For the first sample case, The snake can first eat the 5 apples with size 1, increasing the size of its mouth to 6. The snake can then eat the apple of size 6, increasing the size of its mouth to 12. 12 is less than 24, so the snake cannot eat the last apple with size 24.

KL Coding Cup March 2023 > Snake > Problem 2