极品飞车

ID: 5268

传统题

3000ms

256MiB

难度: 3

上传者:

标签>

深搜

二进制枚举

普及

dfs

数组排序

分支结构

下标计数

题目描述

Bessie 准备参加赛车比赛，她的赛车初始马力为 $F$ ，初始质量为 $M$ 。为了提升赛车性能，她可以前往加工店为赛车加装零件。

加工店共有 $N$ 种零件，编号从 $1$ 到 $N$ ，每种零件仅有一件。第 $i$ 件零件可以为赛车增加 $F_i$ 的马力，同时会增加 $M_i$ 的质量。

根据牛顿第二定律 $F = MA$ （ $F$ 表示力， $M$ 表示质量， $A$ 表示加速度），Bessie 希望赛车的加速度尽可能大。如果存在多种方案可以得到相同的最大加速度，则选择赛车总质量最小的方案。

请你求出 Bessie 应该配置哪些零件。

第一行包含三个整数 $F, M, N$ ，分别表示赛车的初始马力、初始质量，以及零件的种类数。

接下来 $N$ 行，每行包含两个整数 $F_i, M_i$ ，描述第 $i$ 件零件增加的马力与增加的质量。

若不需要加装任何零件即为最优方案，则输出 NONE。

否则，输出若干行，每行一个正整数，表示被选中的零件的编号，按编号从小到大的顺序输出。答案是唯一的。

2
3
4

样例解释

仅配置零件 2 时，加速度为 $\frac{1500+150}{100+9} = \frac{1650}{109} \approx 15.13761$。

遍历所有零件组合后，同时配置零件 2、3、4 时，总马力为 $1970$ ，总质量为 $122$ ，加速度 $\frac{1970}{122} \approx 16.1475$ 为最大值，因此选择该方案。