[AGC011B] Colorful Creatures
题意翻译
## 题目描述
sunuke君见到了 $ N $ 只奇怪的生物。每只生物有两个属性:颜色和大小。第 $ i $ 只生物的颜色是 $ i $ ,大小是 $ A_i $ 。对于每只生物,它能够吸收大小在自己的两倍以下(包括两倍)的其它生物。大小为 $ A $ ,颜色为 $ B $ 的生物能够吸收大小为 $ C $ ,颜色为 $ D $ 的生物 $ (C \leq 2 × A) $ ,合体成为大小为 $ A+C $ ,颜色为 $ B $ 的生物。(可能会存在两只都可以吸收对方的生物)
这些生物会不停合体直到只剩下一只。请求出剩下的一只生物的颜色有多少种情况。
## 数据范围
- $ 2 \leq N \leq 10^5 $
- $ 1 \leq A_i \leq 10^9 $
- $ A_i $ 是整数。
## 输入
输入按以下形式:
$ N $
$ A_1 $ $ A_2 $ $\dots$ $ A_N $
## 输出
请输出一行一个整数:这种生物经过不断合体后,最后剩下的一只的颜色情况数。
## 样例解释
### 样例1解释
最后剩下的生物的颜色可以为 $ 1 $ 和 $ 3 $ 。例如,颜色为 $ 3 $ 的生物吸收颜色为 $ 2 $ 的生物,接下来颜色为 $ 1 $ 的生物吸收颜色为 $ 3 $ 的生物。最后剩下的生物颜色为 $ 1 $ 。
### 样例2解释
相同大小的生物可能有多个。
题目描述
[problemUrl]: https://atcoder.jp/contests/agc011/tasks/agc011_b
すぬけ君は,$ N $ 匹の変わった生き物を見つけました. それぞれの生き物には色と大きさが定まっており,$ i $ 番目の生き物の色は $ i $,大きさは $ A_i $ で表されます.
どの生き物も,大きさが自分の $ 2 $ 倍以下であるような他の生き物を吸収することができます. 大きさ $ A $,色 $ B $ の生き物が大きさ $ C $,色 $ D $ の生き物を吸収すると ($ C\ \leq\ 2\ \times\ A $),合体して大きさ $ A+C $,色 $ B $ の生き物になります. ここで,$ 2 $ 匹の生き物の大きさによっては,どちらも他方を吸収することが可能な場合があります.
すぬけ君がこの生き物たちを観察していると,合体を繰り返して,最終的に $ 1 $ 匹になりました. このとき,残った生き物の色として考えられるものは何種類あるかを求めてください.
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ A_1 $ $ A_2 $ … $ A_N $
输出格式
この生き物たちが合体を繰り返して,最終的に $ 1 $ 匹になったとき,残った生き物の色として考えられるものは何通りあるかを出力せよ.
输入输出样例
输入样例 #1
3
3 1 4
输出样例 #1
2
输入样例 #2
5
1 1 1 1 1
输出样例 #2
5
输入样例 #3
6
40 1 30 2 7 20
输出样例 #3
4
说明
### 制約
- $ 2\ \leq\ N\ \leq\ 100000 $
- $ 1\ \leq\ A_i\ \leq\ 10^9 $
- $ A_i $ は整数
### Sample Explanation 1
最終的に残った生き物の色としては色 $ 1 $, $ 3 $ が考えられます. 例えば,色 $ 3 $ の生き物が色 $ 2 $ の生き物を吸収し,次に色 $ 1 $ の生き物が色 $ 3 $ の生き物と合体すると,色 $ 1 $ の生き物のみが残ります.
### Sample Explanation 2
同じ大きさの生き物が複数いる場合もあります.