比赛场次 | 226 |
---|---|
比赛名称 | 20131130 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2013-11-30 14:30:00 |
结束时间 | 2013-11-30 18:00:00 |
开放分组 | 全部用户 |
注释介绍 |
题目名称 | 提高速度 |
---|---|
输入输出 | sboost.in/out |
时间限制 | 1000 ms (1 s) |
内存限制 | 256 MiB |
测试点数 | 10 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
Chenyao2333 | AAAAAAAAAA | 0.008 s | 0.47 MiB | 100 |
GDFRWMY | AAAAAAAAAA | 0.008 s | 2.21 MiB | 100 |
cstdio | AAAAAAAAAA | 0.009 s | 0.51 MiB | 100 |
digital-T | AWAAAAAAAA | 0.012 s | 0.52 MiB | 90 |
超级傲娇的AC酱 | WWWWWWWWWW | 0.006 s | 0.32 MiB | 0 |
Bessie在为即将来临的汽车大赛准备赛车,它想购买一些附加装备来增强赛车的性能。赛车当前的质量为M(1≤M≤1,000),具有F (1≤F≤1,000,000)大小的动力。商店里有N(1≤N≤10,000)个装备,编号1…N。Bessie可以随便购买多少个装备,但每个装备只能买一件。
装备P_i可以增加F_i (1≤F_i≤1,000,000)的动力,但同时也增加了M_i(1≤M_i≤1,000)的质量。牛顿第二定律说:F=MA,F是力,M是质量,A是加速度。如果Bessie希望赛车的加速度最大(否则的话希望赛车的质量最轻),那么它应当购买多少附加装备呢?
例如,一辆赛车的初始值为F=1500,M=100,有4种附加装备:
i F_i M_i
1 250 25
2 150 9
3 120 5
4 200 8
如果只购买装备2,加速度为:(1500+150)/(100+9)=165/109=15.13761。
下表列出了购买装备的各种组合情况,在第1列中,1表示要买,0表示不买。
Parts Aggregate Aggregate
1234 F M F/M
0000 1500 100 15.0000
0001 1700 108 15.7407
0010 1620 105 15.4286
001 1 1820 113 16.1062
0100 1650 109 15.1376
0101 1850 117 15.8120
0110 1770 114 15.5263
011 1 1970 122 16.1475<-最大的F/M
1000 1750 125 14.0000
1001 1950 133 14.6617
1010 1870 130 14.3846
1011 2070 138 15.0000
1100 1900 134 14.179l
1101 2100 142 14.7887
1110 2020 139 14.5324
1111 2220 147 15.1020
因此,最佳的购买方案是2,3,4。
第1行:3个整数F,M,N
第2…N+I行:第i+l行包含2个整数F_i和M_i
若干行,每行输出一个要购买的装备的编号,以升序输出。如果不需要购买,则输出'NONE'(不要引号)。
数据保证答案唯一。
1500 100 4 250 25 150 9 120 5 200 8
2 3 4
在此键入。
在此键入。