Twins

题意翻译

# 题目描述 ``` 想象一下你是双胞胎。另一个人看起来和你完全一样。不知道有另一个你到底是好的还是坏的。如果你真的是双胞胎，那么你就知道了... 现在假设你是一对双胞胎中的一人。 一个平凡的早上，你又赖床了，妈妈为了工作早走了，以至于她忘了带你们去自助餐厅吃早餐，但她在钱包里发现了一些硬币，或者是说n个任意值的硬币a[1],a[2],a[3]...,a[n]; 但妈妈急着去上班，没有给你们分硬币，于是她潦草的写下一句话 “你们要平分钱哟(╯3╰)” 当你醒来时，你发现了妈妈的硬币，读了她的笔记。但为什么要平分钱呢？你想，毕竟，另一个你正在睡觉，他什么都不知道。所以你决定这样做：选一些硬币，使你的硬币的价值总和就比你的兄弟所拥有的剩余硬币的价值总和大得多。然而，作为一名好哥哥，你认为，如果你拿太多硬币，你的兄弟会怀疑。所以，你决定采用以下方法以避免破坏兄弟情谊： 你取尽可能少的的硬币，但使它们的值总和大于剩余硬币的值之和（没有等于）。用这种方法，确定你可以拿的最小硬币数 ``` # 输入输出格式 ## 输入格式： 第一行是硬币的数量n( 1<=n<=100 )，第二行是各个硬币的值a1,a2,a3,...,an。数字与数字之间有空格 ## 输出格式 输出你可以拿的最小的硬币数。 # 样例说明 在第一个样例中，你必须取2个硬币（你和你的孪生兄弟的取的价值相当于（6，0）。如果你拿1个硬币，你得到（3,3）。如果你拿0个硬币，你得到（0，6）。这些结果并不满足你，因为你可是要拿更多的钱！！。 在第二个样例中，一枚硬币对你来说还不够。你可以选择一组（1,2）或（2,2）的组合。无论如何，你都要拿2枚硬币。 由 @该起什么名字 提供翻译

题目描述

Imagine that you have a twin brother or sister. Having another person that looks exactly like you seems very unusual. It's hard to say if having something of an alter ego is good or bad. And if you do have a twin, then you very well know what it's like. Now let's imagine a typical morning in your family. You haven't woken up yet, and Mom is already going to work. She has been so hasty that she has nearly forgotten to leave the two of her darling children some money to buy lunches in the school cafeteria. She fished in the purse and found some number of coins, or to be exact, $ n $ coins of arbitrary values $ a_{1},a_{2},...,a_{n} $ . But as Mom was running out of time, she didn't split the coins for you two. So she scribbled a note asking you to split the money equally. As you woke up, you found Mom's coins and read her note. "But why split the money equally?" — you thought. After all, your twin is sleeping and he won't know anything. So you decided to act like that: pick for yourself some subset of coins so that the sum of values of your coins is strictly larger than the sum of values of the remaining coins that your twin will have. However, you correctly thought that if you take too many coins, the twin will suspect the deception. So, you've decided to stick to the following strategy to avoid suspicions: you take the minimum number of coins, whose sum of values is strictly more than the sum of values of the remaining coins. On this basis, determine what minimum number of coins you need to take to divide them in the described manner.

输入输出格式

输入格式

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.

输出格式

In the single line print the single number — the minimum needed number of coins.

输入输出样例

输入样例 #1

2
3 3

输出样例 #1

2

输入样例 #2

3
2 1 2

输出样例 #2

2

说明

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 $ .