← 返回题目列表

Codeforces · 662/E

E. 黑客还是不黑客

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

考虑由三个使用动态评分的问题组成的常规 Codeforces 回合。

您将获得一个几乎最终的记分板。对于每个参与者(包括您自己),都会给出每个问题的接受提交时间。此外,对于每个解决方案,您已经知道是否能够破解它。本轮结束前记分牌上唯一发生的变化就是你的挑战。

最后你可能选择的最佳位置是什么?

更正式地说,有 n 个人参与(包括你自己)。对于任何问题,如果在一轮结束时恰好有 k 个人解决了该问题,则该问题的最高得分定义为:

1. 如果n < 2k ≤ 2n,则最大可能得分为500;
2. 如果n < 4k ≤ 2n,则最大可能得分为1000;
3. 如果n < 8k ≤ 2n,则最大可能得分为1500;
4. 如果n < 16k ≤ 2n,则最大可能得分为2000;
5. 如果n < 32k ≤ 2n,则最大可能得分为2500;
6. 如果 32k ≤ n,则最大可能得分为 3000。

令某个问题的最大可能得分等于 s。然后,未能成功接受该问题(或者他的解决方案被黑客攻击)的参赛者将因该问题获得 0 分。如果他在回合开始后 t 分钟内得到了接受的解决方案(并且他的解决方案没有被黑客入侵),他将因该问题获得 $$\frac{s \cdot (250 - t)}{250}$$ 积分。

参与者的总分等于他在每个问题上获得的分数之和加上每次成功 hack 的 100 分(只有你进行 hack)。

您获得的名次等于 1 加上总分严格大于您的参与者的数量。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 5000) - 参与者数量。你是1号参与者。

以下 n 行每行包含三个整数 ai、bi 和 ci。这里ai = 0 表示参与者编号i 未能接受第一个问题。如果 1 ≤ ai ≤ 120,则参赛者编号 i 在比赛开始后几分钟内接受了第一个问题 ai,并且您无法破解此解决方案。最后, - 120 ≤ ai ≤ - 1 表示参赛者编号 i 在比赛开始后几分钟内接受了第一个问题 - ai ,您可以破解此解决方案。类似地,bi 和 ci 以相同的格式提供有关第二个问题和第三个问题的信息。

保证整数 a1、b1 和 c1 为非负数。

输出

打印唯一的整数 - 您在回合结束时可以占据的最佳位置。

示例

输入 #1

4
120 120 1
61 61 120
-61 61 120
0 0 0

输出 #1

1

输入 #2

4
0 0 119
-3 -17 -42
0 7 0
51 0 0

输出 #2

2

注意

考虑第一个样本。如果您没有破解任何解决方案,您将赢得比赛(左侧记分板)。但是,如果您破解了第三个参与者(您唯一可以破解的)的第一个问题的解决方案,则第一个问题的最高分数将会改变,您将获得第二名(右侧的记分板)。