B - Colorful Creatures

Contest Duration: 2017-03-12(Sun) 12:00 - 2017-03-12(Sun) 13:50 (local time) (110 minutes) Back to Home

B - Colorful Creatures Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : $400$ 点

問題文

すぬけ君は， $N$ 匹の変わった生き物を見つけました．それぞれの生き物には色と大きさが定まっており， $i$ 番目の生き物の色は $i$ ，大きさは $A_i$ で表されます．

どの生き物も，大きさが自分の $2$ 倍以下であるような他の生き物を吸収することができます．大きさ $A$ ，色 $B$ の生き物が大きさ $C$ ，色 $D$ の生き物を吸収すると ( $C \leq 2 \times A$ )，合体して大きさ $A+C$ ，色 $B$ の生き物になります．ここで， $2$ 匹の生き物の大きさによっては，どちらも他方を吸収することが可能な場合があります．

すぬけ君がこの生き物たちを観察していると，合体を繰り返して，最終的に $1$ 匹になりました．このとき，残った生き物の色として考えられるものは何種類あるかを求めてください．

制約

$2 \leq N \leq 100000$
$1 \leq A_i \leq 10^9$
$A_i$ は整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $A_1$   $A_2$  …  $A_N$

出力

この生き物たちが合体を繰り返して，最終的に $1$ 匹になったとき，残った生き物の色として考えられるものは何通りあるかを出力せよ．

入力例 1Copy

Copy

3
3 1 4

出力例 1Copy

Copy

最終的に残った生き物の色としては色 $1$ , $3$ が考えられます．例えば，色 $3$ の生き物が色 $2$ の生き物を吸収し，次に色 $1$ の生き物が色 $3$ の生き物と合体すると，色 $1$ の生き物のみが残ります．

入力例 2Copy

Copy

5
1 1 1 1 1

出力例 2Copy

Copy

同じ大きさの生き物が複数いる場合もあります．

入力例 3Copy

Copy

6
40 1 30 2 7 20

出力例 3Copy

Copy

Score : $400$ points

Problem Statement

Snuke found $N$ strange creatures. Each creature has a fixed color and size. The color and size of the $i$ -th creature are represented by $i$ and $A_i$ , respectively.

Every creature can absorb another creature whose size is at most twice the size of itself. When a creature of size $A$ and color $B$ absorbs another creature of size $C$ and color $D$ ( $C \leq 2 \times A$ ), they will merge into one creature of size $A+C$ and color $B$ . Here, depending on the sizes of two creatures, it is possible that both of them can absorb the other.

Snuke has been watching these creatures merge over and over and ultimately become one creature. Find the number of the possible colors of this creature.

Constraints

$2 \leq N \leq 100000$
$1 \leq A_i \leq 10^9$
$A_i$ is an integer.

Input

The input is given from Standard Input in the following format:

 $N$ 
 $A_1$   $A_2$  …  $A_N$

Output

Print the number of the possible colors of the last remaining creature after the $N$ creatures repeatedly merge and ultimately become one creature.

Sample Input 1Copy

Copy

3
3 1 4

Sample Output 1Copy

Copy

The possible colors of the last remaining creature are colors $1$ and $3$ . For example, when the creature of color $3$ absorbs the creature of color $2$ , then the creature of color $1$ absorbs the creature of color $3$ , the color of the last remaining creature will be color $1$ .

Sample Input 2Copy

Copy

5
1 1 1 1 1

Sample Output 2Copy

Copy

There may be multiple creatures of the same size.

Sample Input 3Copy

Copy

6
40 1 30 2 7 20

Sample Output 3Copy

Copy