TLE '16 Contest 8 P4 - Delivery Service

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem types
Fax McClad delivering Mighty Reactors and green goods. Note the dangerous microwave radiation from the Mighty Reactors.

Fax McClad, Croneria's best bounty hunter, has been hired by a mysterious group called BSE to deliver some goods from the planet Croneria to the planet Phantom-R. On his delivery confirmation list, he notices that the cargo consists of dangerously radioactive Mighty Reactors, and green goods. The hazardous goods don't concern Fax, because money is always more important than safety.

The route from Croneria to Phantom-R is D spacemiles long and consists of one planet every spacemile, named 1, \dots, D-1. Fax initially only has N units of fuel on his Kyuwing, so he may need to stop at some planets to refuel. There are P planets where Fax can refuel, and they have a limited supply of fuel. For each of the P planets, the i^{th} planet is numbered Q_i and contains R_i units of fuel. Unfortunately, because of security reasons, Fax must dump all of the fuel he has on his Kyuwing upon entering a planet. It takes one unit of fuel to travel one spacemile.

However, Fax knows that evil organizations such as the Dankey Kang Gang want to steal the precious goods that he is delivering. As such, Fax needs to plan several routes to get to his destination. To speed up his delivery, Fax will not backtrack, nor visit the same planet twice.

In order to prepare for this delivery, Fax needs to simulate different traveling conditions. If X=1, Fax must determine W, the number of distinct routes (modulo 10^9+7), given the fuel supplies of the planets. If X=2, Fax needs to determine the fuel supplies of the planets so that there are W (modulo 10^9+7) distinct routes. Two routes are distinct if there is at least one planet that is in one route but not the other.

Constraints

2 \le D \le 100\,000

1 \le N \le D

1 \le P,Q_i,R_i \le D-1

None of the P planets will share the same Q_i.

For test cases with X=2, 0 \le W < 10^9+7.

Subtask Points X Additional Constraints
1 20 X=1 D \le 10
2 10 X=1 D \le 1000
3 20 X=1 None
4 10 X=2 W \le 100\,000
5 20 X=2 None
6 20 X=2 D < 70

Input Specification

The first line contains X.

If X=1, the second line contains three integers D, N, and P.
On the next P lines, the i^{th} line will contain two integers, Q_i and R_i.

If X=2, the second line contains W, the number of routes (modulo 10^9+7).

Output Specification

If X=1, print W, the number of routes Fax can take to reach his destination, modulo 10^9+7.

If X=2, on the first line, print three integers D, N, and P.
On the next P lines, the i^{th} line should contain two integers, Q_i and R_i.
Your output must satisfy the given constraints. The number of routes (modulo 10^9+7) should be equal to W.

Sample Input 1

1
10 5 5
1 5
4 2
5 3
6 2
8 2

Sample Output 1

11

Explanation for Sample Output 1

The 11 routes are as follows:

  • 0 \to 1 \to 4 \to 5 \to 6 \to 8 \to 10
  • 0 \to 1 \to 4 \to 5 \to 8 \to 10
  • 0 \to 1 \to 4 \to 6 \to 8 \to 10
  • 0 \to 1 \to 5 \to 6 \to 8 \to 10
  • 0 \to 1 \to 5 \to 8 \to 10
  • 0 \to 1 \to 6 \to 8 \to 10
  • 0 \to 4 \to 5 \to 6 \to 8 \to 10
  • 0 \to 4 \to 5 \to 8 \to 10
  • 0 \to 4 \to 6 \to 8 \to 10
  • 0 \to 5 \to 6 \to 8 \to 10
  • 0 \to 5 \to 8 \to 10

Sample Input 2

2
420

Sample Output 2

10 10 9
1 6
2 8
3 5
4 6
5 4
6 4
7 2
8 2
9 1

Sample Input 3

2
1

Sample Output 3

2 1 1
1 1

Comments

There are no comments at the moment.