本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1036. Reading Comprehension


Description

【问题描述】

AFei is a trainee magician who likes to study various magical materials. Today, he came to

the forest to find rare materials. He was so lucky that he found a piece of high-level magic stone.

He knew that this stone always appeared in the pile, so there must be more nearby. Then he

went deeper.

As expected, he found many magic stones. These stones were arranged in a row. Just as he

was ready to pick up one, a magical circle was triggered. He was petrified and the stones began

to move. As mentioned above, the stones were lined up. Now, some stones moved to one end of

the line and the other stones moved to the other end. Stones would not change direction of

movement unless they collided with other stones. Collision meant that two stones moved to the

same position, and then the directions of the two stones would both change. Whether or not a

collision occured, the speed was always 1 m/s. Stone would disappear when it reached one of the

ends.

AFei knew that the magical circle would disappear after t seconds. It meant that after t

seconds, he could move and the stones would return to immobility. This also meant that AFei

would get those stones. He wondered how many magic stones he could get in the end, including

the first one he got when he came to the forest.

Input

【输入形式】

The first line contains three integers n, L, t (0 ≤ n ≤ 1000000, 2 ≤ L ≤ 1000000000,

0<=t<=1000000) − the number of stones on the line is n,the length of the line is L meter, and

the magic circle will disappear after t seconds.

The following n lines contain description of magic stones on the line. Each i-th of these lines

contains two space-separated integers x[i] and d[i] (0<x[i]<L, d[i]∈{1,2} for i<=n), which stand for

initial position and direction of motion(1 means from 0 to L, 2 means from L to 0.).

Output

【输出形式】

Output a number indicating the amount of the magic stones that AFei will eventually be able

to obtain.

Samples

Input Copy
4 10 6
1 1
5 2
6 1
9 2
Output
3

Hint

Hint

The stones are A(1,1), B(5,2), C(6,1), D(9,2).

After 1s, they become A(2,1), B(4,2), C(7,1), D(8,2);

After 2s, they become A(3,2), B(3,1), C(7,2), D(8,1);

After 3s, they become A(2,2), B(4,1), C(6,2), D(9,1);

After 4s, they become A(1,2), B(5,2), C(5,1), D reach L and disappears;

After 5s, they become A reach 0 and disappears, B(4, 2), C(6,1), D disappeared;

After 6s, they become A disappeared, B(3, 2), C(7, 1), D disappeared.

AFei finially gets the first one, B and C.

PS:

1,Input guarantees that there will not be two magic stones in one location.

2,If stone A and stone B are located at 4 and 5, respectively, and A's direction is 1, B's direction is

2. Then next second, the position of the two stones have not changed, but they have gone in the

opposite direction.

 

Source

2019徐州工程学院新生赛
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 0 / 2
Tags:
My history solutions

You didn't submit any solution!
Submit your solution

Login Register