TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3823
  • 题目
  • P3823果冻怪
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1000ms
    问题描述

    小南和小开在三友路上养了很多只果冻怪。我们可以将三友路想象成一根长度无限的数 轴,在这上面生活着n只果冻怪。每经过一秒,一只果冻怪便会分裂成两只。具体来说,一 只坐标为x的果冻怪,会分裂成两只分别在(x − 1),(x + 1)上的果冻怪,并且原来在x上的果 冻怪会消失。 由于生存空间有限,若一个位置上有不少于P只果冻怪,那么会立刻消失 P 只。经过测 定P = 10^9 + 7。 小南和小开想知道在第T秒末,位置w有多少只果冻怪。初始时刻是0秒初。 

    输入格式

    第一行为三个整数,n,T,w。含义如题所述。
    接下来 n 行,每行两个整数𝑥𝑖,𝑐𝑖,表示𝑥𝑖位置,有𝑐𝑖只果冻怪。注意𝑥𝑖可能有重复。 

    输出格式

    输出一个非负整数,表示 T 秒末 w 位置上的果冻怪个数

    样例输入

    2 2 2 
    0 3 
    1 2 

    样例输出

    3

    提示

    对于 30%的数据: 1 ≤ n ≤ 100,1 ≤ T ≤ 16。
    对于 60%的数据:1 ≤ n ≤ 10^5,1 ≤ T ≤ 16。
    对于 100%的数据:1 ≤ n,T,𝑐𝑖 ≤ 10^5,0 ≤ |𝑤|,|𝑥𝑖| ≤ 10^5。 


    来源  WJJ