CodeEff/ECCO huggingface dataset:
Problem Description: Score : 500 points
Problem Statement
Snuke is conducting an optical experiment using mirrors and his new invention, the rifle of
Mysterious Light
.
Three mirrors of length
N
are set so that they form an equilateral triangle.
Let the vertices of the triangle be
a, b
and
c
.
Inside the triangle, the rifle is placed at the point
p
on segment
ab
such that
ap = X
.
(The size of the rifle is negligible.)
Now, the rifle is about to fire a ray of Mysterious Light in the direction of
bc
.
The ray of Mysterious Light will travel in a straight line, and will be reflected by mirrors, in the same ways as "ordinary" light.
There is one major difference, though: it will be also reflected by its own trajectory as if it is a mirror!
When the ray comes back to the rifle, the ray will be absorbed.
The following image shows the ray's trajectory where
N = 5
and
X = 2
.
It can be shown that the ray eventually comes back to the rifle and is absorbed, regardless of the values of
N
and
X
.
Find the total length of the ray's trajectory.
Constraints
2≦N≦10^{12}
1≦X≦N-1
N
and
X
are integers.
Partial Points
300
points will be awarded for passing the test set satisfying
N≦1000
.
Another
200
points will be awarded for passing the test set without additional constraints.
Input
The input is given from Standard Input in the following format:
N
X
Output
Print the total length of the ray's trajectory.
Sample Input 1
5 2
Sample Output 1
12
Refer to the image in the Problem Statement section.
The total length of the trajectory is
2+3+2+2+1+1+1 = 12
.
Problem Description: Score : 600 points
Problem Statement
Given an undirected tree, let the distance between vertices
u
and
v
be the
number of edges on the simple path from
u
to
v
.
The diameter of a tree is the maximum among the distances between any two vertices.
We will call a tree
good
if and only if its diameter is at most
K
.
You are given an undirected tree with
N
vertices numbered
1
through
N
.
For each
i (1≦i≦N-1)
, there is an edge connecting vertices
A_i
and
B_i
.
You want to remove zero or more vertices from the tree, so that the resulting tree is good.
When a vertex is removed, all incident edges will also be removed.
The resulting graph must be connected.
Find the minimum number of vertices that you need to remove in order to produce a good tree.
Constraints
2≦N≦2000
1≦K≦N-1
1≦A_i≦N, 1≦B_i≦N
The graph defined by
A_i
and
B_i
is a tree.
Input
The input is given from Standard Input in the following format:
N
K
A_1
B_1
A_2
B_2
:
A_{N-1}
B_{N-1}
Output
Print the minimum number of vertices that you need to remove in order to produce a good tree.
Sample Input 1
6 2
1 2
3 2
4 2
1 6
5 6
Sample Output 1
2
The tree is shown below. Removing vertices
5
and
6
will result in a good tree with the diameter of
2
.
Sample Input 2
6 5
1 2
3 2
4 2
1 6
5 6
Sample Output 2
0
Since the given tree is already good, you do not need to remove any vertex.
Problem Description: Score : 1400 points
Problem Statement
Snuke is having another barbeque party.
This time, he will make one serving of
Skewer Meal
.
He has a stock of
N
Skewer Meal Packs
. The
i
-th Skewer Meal Pack contains one skewer,
A_i
pieces of beef and
B_i
pieces of green pepper.
All skewers in these packs are different and distinguishable, while all pieces of beef and all pieces of green pepper are, respectively, indistinguishable.
To make a Skewer Meal, he chooses two of his Skewer Meal Packs, and takes out all of the contents from the chosen packs, that is, two skewers and some pieces of beef or green pepper.
(Remaining Skewer Meal Packs will not be used.)
Then, all those pieces of food are threaded onto both skewers, one by one, in any order.
(See the image in the Sample section for better understanding.)
In how many different ways can he make a Skewer Meal? Two ways of making a Skewer Meal is different if and only if the sets of the used skewers are different, or the orders of the pieces of food are different.
Since this number can be extremely large, find it modulo
10^9+7
.
Constraints
2≦N≦200,000
1≦A_i≦2000, 1≦B_i≦2000
Input
The input is given from Standard Input in the following format:
N
A_1
B_1
A_2
B_2
:
A_N
B_N
Output
Print the number of the different ways Snuke can make a serving of Skewer Meal, modulo
10^9+7
.
Sample Input 1
3
1 1
1 1
2 1
Sample Output 1
26
The
26
ways of making a Skewer Meal are shown below.
Gray bars represent skewers, each with a number denoting the Skewer Meal Set that contained the skewer.
Brown and green rectangles represent pieces of beef and green pepper, respectively.