TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3823
  • Problem
  • P3823果冻怪
    Limits : Time Limit : - MS   Memory Limit : 165536 KB
    Judgment Tips : 1000ms
    Description

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

    Input Format

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

    Output Format

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

    Sample Input

    2 2 2 
    0 3 
    1 2 

    Sample Output

    3

    Hint

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


    Source  WJJ