CodeEff/ECCO huggingface dataset:
Problem Description: Score : 400 points
Problem Statement
You are given an undirected connected weighted graph with
N
vertices and
M
edges that contains neither self-loops nor double edges.
The
i
-th
(1≤i≤M)
edge connects vertex
a_i
and vertex
b_i
with a distance of
c_i
.
Here, a
self-loop
is an edge where
a_i = b_i (1≤i≤M)
, and
double edges
are two edges where
(a_i,b_i)=(a_j,b_j)
or
(a_i,b_i)=(b_j,a_j) (1≤i<j≤M)
.
A
connected graph
is a graph where there is a path between every pair of different vertices.
Find the number of the edges that are not contained in any shortest path between any pair of different vertices.
Constraints
2≤N≤100
N-1≤M≤min(N(N-1)/2,1000)
1≤a_i,b_i≤N
1≤c_i≤1000
c_i
is an integer.
The given graph contains neither self-loops nor double edges.
The given graph is connected.
Input
The input is given from Standard Input in the following format:
N
M
a_1
b_1
c_1
a_2
b_2
c_2
:
a_M
b_M
c_M
Output
Print the number of the edges in the graph that are not contained in any shortest path between any pair of different vertices.
Sample Input 1
3 3
1 2 1
1 3 1
2 3 3
Sample Output 1
1
In the given graph, the shortest paths between all pairs of different vertices are as follows:
The shortest path from vertex
1
to vertex
2
is: vertex
1
→ vertex
2
, with the length of
1
.
The shortest path from vertex
1
to vertex
3
is: vertex
1
→ vertex
3
, with the length of
1
.
The shortest path from vertex
2
to vertex
1
is: vertex
2
→ vertex
1
, with the length of
1
.
The shortest path from vertex
2
to vertex
3
is: vertex
2
→ vertex
1
→ vertex
3
, with the length of
2
.
The shortest path from vertex
3
to vertex
1
is: vertex
3
→ vertex
1
, with the length of
1
.
The shortest path from vertex
3
to vertex
2
is: vertex
3
→ vertex
1
→ vertex
2
, with the length of
2
.
Thus, the only edge that is not contained in any shortest path, is the edge of length
3
connecting vertex
2
and vertex
3
, hence the output should be
1
.
Sample Input 2
3 2
1 2 1
2 3 1
Sample Output 2
0
Every edge is contained in some shortest path between some pair of different vertices.
Problem Description: Score : 200 points
Problem Statement
Joisino is about to compete in the final round of a certain programming competition.
In this contest, there are
N
problems, numbered
1
through
N
.
Joisino knows that it takes her
T_i
seconds to solve problem
i(1≦i≦N)
.
Also, there are
M
kinds of drinks offered to the contestants, numbered
1
through
M
.
If Joisino takes drink
i(1≦i≦M)
, her brain will be stimulated and the time it takes for her to solve problem
P_i
will become
X_i
seconds.
It does not affect the time to solve the other problems.
A contestant is allowed to take exactly one of the drinks before the start of the contest.
For each drink, Joisino wants to know how many seconds it takes her to solve all the problems if she takes that drink.
Here, assume that the time it takes her to solve all the problems is equal to the sum of the time it takes for her to solve individual problems.
Your task is to write a program to calculate it instead of her.
Constraints
All input values are integers.
1≦N≦100
1≦T_i≦10^5
1≦M≦100
1≦P_i≦N
1≦X_i≦10^5
Input
The input is given from Standard Input in the following format:
N
T_1
T_2
...
T_N
M
P_1
X_1
P_2
X_2
:
P_M
X_M
Output
For each drink, calculate how many seconds it takes Joisino to solve all the problems if she takes that drink, and print the results, one per line.
Sample Input 1
3
2 1 4
2
1 1
2 3
Sample Output 1
6
9
If Joisino takes drink
1
, the time it takes her to solve each problem will be
1
,
1
and
4
seconds, respectively, totaling
6
seconds.
If Joisino takes drink
2
, the time it takes her to solve each problem will be
2
,
3
and
4
seconds, respectively, totaling
9
seconds.
Sample Input 2
5
7 2 3 8 5
3
4 2
1 7
4 13
Sample Output 2
19
25
30
Problem Description: Score : 200 points
Problem Statement
Snuke is interested in strings that satisfy the following conditions:
The length of the string is at least
N
.
The first
N
characters equal to the string
s
.
The last
N
characters equal to the string
t
.
Find the length of the shortest string that satisfies the conditions.
Constraints
1≤N≤100
The lengths of
s
and
t
are both
N
.
s
and
t
consist of lowercase English letters.
Input
The input is given from Standard Input in the following format:
N
s
t
Output
Print the length of the shortest string that satisfies the conditions.
Sample Input 1
3
abc
cde
Sample Output 1
5
The shortest string is
abcde
.
Sample Input 2
1
a
z
Sample Output 2
2
The shortest string is
az
.
Sample Input 3
4
expr
expr
Sample Output 3
4
The shortest string is
expr
.
Problem Description: Score : 200 points
Problem Statement
There are
K
pieces of cakes.
Mr. Takahashi would like to eat one cake per day, taking
K
days to eat them all.
There are
T
types of cake, and the number of the cakes of type
i
(
1 ≤ i ≤ T
) is
a_i
.
Eating the same type of cake two days in a row would be no fun,
so Mr. Takahashi would like to decide the order for eating cakes that minimizes the number of days on which he has to eat the same type of cake as the day before.
Compute the minimum number of days on which the same type of cake as the previous day will be eaten.
Constraints
1 ≤ K ≤ 10000
1 ≤ T ≤ 100
1 ≤ a_i ≤ 100
a_1 + a_2 + ... + a_T = K
Input
The input is given from Standard Input in the following format:
K
T
a_1
a_2
...
a_T
Output
Print the minimum number of days on which the same type of cake as the previous day will be eaten.
Sample Input 1
7 3
3 2 2
Sample Output 1
0
For example, if Mr. Takahashi eats cakes in the order of
2, 1, 2, 3, 1, 3, 1
, he can avoid eating the same type of cake as the previous day.
Sample Input 2
6 3
1 4 1
Sample Output 2
1
There are
6
cakes.
For example, if Mr. Takahashi eats cakes in the order of
2, 3, 2, 2, 1, 2
, he has to eat the same type of cake (i.e., type
2
) as the previous day only on the fourth day.
Since this is the minimum number, the answer is
1
.
Sample Input 3
100 1
100
Sample Output 3
99
Since Mr. Takahashi has only one type of cake, he has no choice but to eat the same type of cake as the previous day from the second day and after.
Problem Description: Score : 900 points
Problem Statement
AtCoDeer the deer has
N
square tiles. The tiles are numbered
1
through
N
, and the number given to each tile is written on one side of the tile. Also, each corner of each tile is painted in one of the
1000
colors, which are represented by the integers
0
between
999
. The top-left, top-right, bottom-right and bottom-left corner of the tile with the number
i
are painted in color
C_{i,0}, C_{i,1}, C_{i,2}
and
C_{i,3}
, respectively, when seen in the direction of the number written on the tile (See Figure
1
).
Figure
1
: The correspondence between the colors of a tile and the input
AtCoDeer is constructing a cube using six of these tiles, under the following conditions:
For each tile, the side with the number must face outward.
For each vertex of the cube, the three corners of the tiles that forms it must all be painted in the same color.
Help him by finding the number of the different cubes that can be constructed under the conditions.
Since each tile has a number written on it, two cubes are considered different if the set of the used tiles are different, or the tiles are used in different directions, even if the formation of the colors are the same. (Each tile can be used in one of the four directions, obtained by
90°
rotations.) Two cubes are considered the same only if rotating one in the three dimensional space can obtain an exact copy of the other, including the directions of the tiles.
Figure
2
: The four directions of a tile
Constraints
6≦N≦400
0≦C_{i,j}≦999 (1≦i≦N , 0≦j≦3)
Input
The input is given from Standard Input in the following format:
N
C_{1,0}
C_{1,1}
C_{1,2}
C_{1,3}
C_{2,0}
C_{2,1}
C_{2,2}
C_{2,3}
:
C_{N,0}
C_{N,1}
C_{N,2}
C_{N,3}
Output
Print the number of the different cubes that can be constructed under the conditions.
Sample Input 1
6
0 1 2 3
0 4 6 1
1 6 7 2
2 7 5 3
6 4 5 7
4 0 3 5
Sample Output 1
1
The cube below can be constructed.
Sample Input 2
8
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
Sample Output 2
144
Sample Input 3
6
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Sample Output 3
122880
Problem Description: Score : 800 points
Problem Statement
12:17 (UTC): The sample input 1 and 2 were swapped. The error is now fixed. We are very sorry for your inconvenience.
There are
N
children in AtCoder Kindergarten, conveniently numbered
1
through
N
. Mr. Evi will distribute
C
indistinguishable candies to the children.
If child
i
is given
a
candies, the child's
happiness
will become
x_i^a
, where
x_i
is the child's
excitement level
. The
activity level
of the kindergarten is the
product
of the happiness of all the
N
children.
For each possible way to distribute
C
candies to the children by giving zero or more candies to each child, calculate the activity level of the kindergarten. Then, calculate the sum over all possible way to distribute
C
candies. This sum can be seen as a function of the children's excitement levels
x_1,..,x_N
, thus we call it
f(x_1,..,x_N)
.
You are given integers
A_i,B_i (1≦i≦N)
. Find
modulo
10^9+7
.
Constraints
1≦N≦400
1≦C≦400
1≦A_i≦B_i≦400 (1≦i≦N)
Partial Score
400
points will be awarded for passing the test set satisfying
A_i=B_i (1≦i≦N)
.
Input
The input is given from Standard Input in the following format:
N
C
A_1
A_2
...
A_N
B_1
B_2
...
B_N
Output
Print the value of
modulo
10^9+7
.
Sample Input 1
2 3
1 1
1 1
Sample Output 1
4
This case is included in the test set for the partial score, since
A_i=B_i
.
We only have to consider the sum of the activity level of the kindergarten where the excitement level of both child
1
and child
2
are
1
(
f(1,1)
).
If child
1
is given
0
candy, and child
2
is given
3
candies, the activity level of the kindergarten is
1^0*1^3=1
.
If child
1
is given
1
candy, and child
2
is given
2
candies, the activity level of the kindergarten is
1^1*1^2=1
.
If child
1
is given
2
candies, and child
2
is given
1
candy, the activity level of the kindergarten is
1^2*1^1=1
.
If child
1
is given
3
candies, and child
2
is given
0
candy, the activity level of the kindergarten is
1^3*1^0=1
.
Thus,
f(1,1)=1+1+1+1=4
, and the sum over all
f
is also
4
.
Sample Input 2
1 2
1
3
Sample Output 2
14
Since there is only one child, child
1
's happiness itself will be the activity level of the kindergarten. Since the only possible way to distribute
2
candies is to give both candies to child
1
, the activity level in this case will become the value of
f
.
When the excitement level of child
1
is
1
,
f(1)=1^2=1
.
When the excitement level of child
1
is
2
,
f(2)=2^2=4
.
When the excitement level of child
1
is
3
,
f(3)=3^2=9
.
Thus, the answer is
1+4+9=14
.
Sample Input 3
2 3
1 1
2 2
Sample Output 3
66
Since it can be seen that
f(1,1)=4 , f(1,2)=15 , f(2,1)=15 , f(2,2)=32
, the answer is
4+15+15+32=66
.
Sample Input 4
4 8
3 1 4 1
3 1 4 1
Sample Output 4
421749
This case is included in the test set for the partial score.
Sample Input 5
3 100
7 6 5
9 9 9
Sample Output 5
139123417