← 返回题目列表

AtCoder · agc011_b

B. 色彩缤纷的生物

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

发现蛇核 N 奇怪的生物。 每个生物都有固定的颜色和大小。颜色和尺寸 i-th 生物由 i 和 A_i。

每个生物都可以吸收另一个体型至多是其自身体型两倍的生物。 当一个生物的体型 A 和颜色 B 吸收了另一个同等大小的生物 C 和颜色 D (C \leq 2 \times A),它们将合并成一个大小相同的生物 A+C 和颜色 B。 在这里,根据两个生物的大小,它们有可能都可以吸收对方。

Snuke 一直在看着这些生物一遍又一遍地融合并最终成为一个生物。 找出该生物可能的颜色数量。

约束

  • 2 \leq N \leq 100000
  • 1 \leq A_i \leq 10^9
  • A_i 是一个整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 … A_N

输出

输出最后一个生物的可能颜色数 N 生物反复合并并最终成为一个生物。


示例输入 1

3
3 1 4

示例输出 1

2

最后剩下的生物可能的颜色是颜色 1 和 3。 例如,当彩色生物 3 吸收彩色生物 2,然后是彩色生物 1 吸收彩色生物 3,最后剩下的生物的颜色将为 color 1.


示例输入 2

5
1 1 1 1 1

示例输出 2

5

可能有多个相同大小的生物。


示例输入 3

6
40 1 30 2 7 20

示例输出 3

4