TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3090
  • 题目
  • P3090【联训赛10.16】丢钉子
    限制 : 时间限制 : 20000 MS   空间限制 : 165536 KB
    问题描述

    学校里一年一度的自行车大赛又开始了!!可是ZL同学却非常不高兴,因为他不会骑自行车!所以他决定干扰这次比赛。他已经了解到了这次参加比赛的m名参赛选手的资料。他决定要进行一次惊天动地的干扰。
    我们假设比赛场地是一个从起点处向右和向前无限延伸的跑道。编号为1到m的参赛队员从左到右并列排列。从比赛开始后的第1秒末,第2秒末,第3秒末,第4秒末……第m秒末他分别会投一枚钉子到当前排名第一的自行车的前面使其爆胎!(爆胎的自行车自动退出比赛,不再计入排名),当有多个人同时并列第一时,由于ZL童鞋在起点左侧的观众席,他总是丢在最接近左侧边缘的那个第一名参赛选手前(字典序最小的第一名)。
    而参赛队员的资料只有两个,一个是他第一秒能前进的距离Vi,一个是他第一秒末后每秒秒能前进的距离Ai。
    现在要你来求,每秒钟,ZL童鞋把钉子丢在了编号为几的参赛选手前。

    输入格式

    第一行为一个整数m,表示有m名参赛选手。
    接下来有m行,分别表示编号为 i(从1到m)的参赛队员的数据,每行两个整数Vi,Ai。

    输出格式

    一行,m个整数,第i个数,表示第i秒退赛的选手的编号

    样例输入

    样例1
    3
    100 1
    100 2
    3 100

    样例2
    5
    1 1
    2 2
    3 3
    4 1
    3 4

    样例输出

    样例1:
    1 3 2

    样例2:
    4 5 3 2 1

    提示

    【样例1说明】
    第一组测试数据
    第1秒
    选手1前进到100米处。
    选手2前进到100米处。
    选手3前进到 3 米处。
    此时选手1、2并列第一,ZL把钉子丢在1号选手前,1号选手退出比赛。

    第2秒
    选手2前进到102米处。
    选手3前进到103米处。
    此时选手3第一。ZL把钉子丢在3号选手前,3号选手退出比赛。

    第3秒
    选手2前进到104米处。
    此时选手2第一。ZL把钉子丢在2号选手前,2号选手退出比赛。

    1 <= m <= 50000
    0 <= Vi <= 500
    0 < Ai <= 100


    来源  hdu4393