logo AlgoBeat OnlineJudge
登录 注册

#102174. [BZOJ 2174] 元素之泉

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:无测试数据
上传者: 匿名

题目描述

传说中的 Dystopia 大陆是一片神圣美丽的土地,上面生活着具有极高文明的种族 Barbarian。这里是一个美好、人人平等、没有压迫的社会,就像世外桃源一般。

Dystopia 大陆上有 处泉水,每种泉水含有 种元素:冰,火,木等等(固定比例)。每一处泉水都是无穷无尽的,但是每次对于每一个矿的开采都需要耗费大量的魔法。 这里的泉水是 Dystopia 大陆的灵性和精华之源,令许多周边种族朝思暮想,也因此常常招致来战争。

由于 Dystopia 的人们不善于战争,为了保护这方乐土,Dystopia 的人委托爱与美的化身 Satan 来帮助他们保卫国家。但是 Satan 不会无条件保护他们,每一次保护他都必须得到每种泉水各 升。

经过几次战争后,Dystopia 的人们发觉 Satan 的要求实在太多了。为了减少魔法的使用,Dystopia 的大法师决定尽可能减少开采的矿的数量,而是增加每个矿开采的泉水总量,然后通过一定比例调配以假乱真。比如有 处泉水,第一处是 冰 + 火 + 木,第二处是 冰 + 火 + 木,第三处是 冰 + 火 + 木。我们可以只开采第一处和第三处的泉水,然后按照 的比例就可以调配出和第二处泉水完全相同的混合泉水。

现在大法师想知道有多少处泉水可以不开采,也就是有多少处泉水可以通过除它以外的其他泉水调配出来。如果有两处泉水的成分完全相同,大法师会不动脑子地认为它们都可以不开采,而不是必须开采一处或者都必须开采。

输入格式

输入的第一行包含两个整数 ,如题所述。

接下来 行,每行 个实数,分别是第 种元素的百分比。保证所有 个数之和为

输出格式

输出一个整数,表示可以不开采的泉水的数量。

样例输入 #1

3 3
10 10 80
20 20 60
30 30 40

样例输出 #1

1

样例输入 #2

2 1
100
100

样例输出 #2

2

数据范围与提示

数据满足:

数据满足:

数据满足:

数据满足:,且保证都是随机数据。

中有 满足:

所有数据满足: