A Busy Morning at Mariam and Tithi’s Home
Time: 1 s
Memory: 125 MB
Memory: 125 MB
It was an early morning at the home of two sisters, Mariam and Tithi. The sisters look very similar, often making it hard for others to tell them apart.
Tithi is smart and always wakes up early, while Mariam is a bit lazy and usually wakes up late. That morning, their mother was in a great hurry to leave for work. While rushing out, she almost forgot to leave money for the sisters to buy lunch at their school cafeteria. At the last moment, she searched her purse and found some coins—specifically, n coins with arbitrary values : \(a_1,a_2,a_3,.........,a_n .\) Since she had no time to divide the money properly, she left all the coins together and quickly wrote a note:“Split the money equally between the two of you.”
After waking up, Tithi found the coins and read the note. Mariam was still asleep and knew nothing about it. Tithi thought to herself: “Why should I split the money equally? Mariam won’t notice anything.” So Tithi decided to take advantage of the situation. She chose a subset of coins for herself such that the total value of the coins she takes is strictly greater than the total value of the remaining coins, which Mariam would receive.
However, Tithi also realized that if she took too many coins, Mariam might become suspicious later. To avoid suspicion, she followed this rule:
Tithi is smart and always wakes up early, while Mariam is a bit lazy and usually wakes up late. That morning, their mother was in a great hurry to leave for work. While rushing out, she almost forgot to leave money for the sisters to buy lunch at their school cafeteria. At the last moment, she searched her purse and found some coins—specifically, n coins with arbitrary values : \(a_1,a_2,a_3,.........,a_n .\) Since she had no time to divide the money properly, she left all the coins together and quickly wrote a note:“Split the money equally between the two of you.”
After waking up, Tithi found the coins and read the note. Mariam was still asleep and knew nothing about it. Tithi thought to herself: “Why should I split the money equally? Mariam won’t notice anything.” So Tithi decided to take advantage of the situation. She chose a subset of coins for herself such that the total value of the coins she takes is strictly greater than the total value of the remaining coins, which Mariam would receive.
However, Tithi also realized that if she took too many coins, Mariam might become suspicious later. To avoid suspicion, she followed this rule:
- She will take the minimum number of coins
- The sum of their values must be strictly greater than the sum of the remaining coins
Input
The first line contains integer n (1 ≤ n ≤ 100) — the number of coins. The second line contains a sequence of n integers \(a_1,a_2,....,a_n(1<= a_i <=100) \) — the coins' values. All numbers are separated with spaces.
Output
In the single line print the single number — the minimum needed number of coins.
Examples
| Input | Output |
|---|---|
|
2
3 3 |
2
|
| Input | Output |
|---|---|
|
3
2 1 2 |
2
|
| Input | Output |
|---|---|
|
5
4 2 2 2 2 |
3
|
Notes
In the first sample you will have to take 2 coins (you and your twin have sums equal to 6, 0 correspondingly). If you take 1 coin, you get sums 3, 3. If you take 0 coins, you get sums 0, 6. Those variants do not satisfy you as your sum should be strictly more that your twins' sum.In the second sample one coin isn't enough for us, too. You can pick coins with values 1, 2 or 2, 2. In any case, the minimum number of coins equals 2.
Problem Info
| Problem ID | 843 |
| Time Limit | 1000 ms |
| Memory Limit | 128000 KB |
| Moderators | shoriful41 |
Statistics
Submit
You need to Login or Registration for submit your solution