CodeEff/ECCO huggingface dataset:
Problem Description: Score : 200 points
Problem Statement
Takahashi has
A
cookies, and Aoki has
B
cookies.
Takahashi will do the following action
K
times:
If Takahashi has one or more cookies, eat one of his cookies.
Otherwise, if Aoki has one or more cookies, eat one of Aoki's cookies.
If they both have no cookies, do nothing.
In the end, how many cookies will Takahashi and Aoki have, respectively?
Constraints
0 \leq A \leq 10^{12}
0 \leq B \leq 10^{12}
0 \leq K \leq 10^{12}
All values in input are integers.
Input
Input is given from Standard Input in the following format:
A
B
K
Output
Print the numbers of Takahashi's and Aoki's cookies after
K
actions.
Sample Input 1
2 3 3
Sample Output 1
0 2
Takahashi will do the following:
He has two cookies, so he eats one of them.
Now he has one cookie left, and he eats it.
Now he has no cookies left, but Aoki has three, so Takahashi eats one of them.
Thus, in the end, Takahashi will have
0
cookies, and Aoki will have
2
.
Sample Input 2
500000000000 500000000000 1000000000000
Sample Output 2
0 0
Watch out for overflows.
Problem Description: Score: 300 points
Problem Statement
Find the minimum prime number greater than or equal to
X
.
Notes
A prime number is an integer greater than
1
that cannot be evenly divided by any positive integer except
1
and itself.
For example,
2
,
3
, and
5
are prime numbers, while
4
and
6
are not.
Constraints
2 \le X \le 10^5
All values in input are integers.
Input
Input is given from Standard Input in the following format:
X
Output
Print the minimum prime number greater than or equal to
X
.
Sample Input 1
20
Sample Output 1
23
The minimum prime number greater than or equal to
20
is
23
.
Sample Input 2
2
Sample Output 2
2
X
itself can be a prime number.
Sample Input 3
99992
Sample Output 3
100003
Problem Description: Score : 500 points
Problem Statement
Takahashi has come to a party as a special guest.
There are
N
ordinary guests at the party. The
i
-th ordinary guest has a
power
of
A_i
.
Takahashi has decided to perform
M
handshakes
to increase the
happiness
of the party (let the current happiness be
0
).
A handshake will be performed as follows:
Takahashi chooses one (ordinary) guest
x
for his left hand and another guest
y
for his right hand (
x
and
y
can be the same).
Then, he shakes the left hand of Guest
x
and the right hand of Guest
y
simultaneously to increase the happiness by
A_x+A_y
.
However, Takahashi should not perform the same handshake more than once. Formally, the following condition must hold:
Assume that, in the
k
-th handshake, Takahashi shakes the left hand of Guest
x_k
and the right hand of Guest
y_k
. Then, there is no pair
p, q
(1 \leq p < q \leq M)
such that
(x_p,y_p)=(x_q,y_q)
.
What is the maximum possible happiness after
M
handshakes?
Constraints
1 \leq N \leq 10^5
1 \leq M \leq N^2
1 \leq A_i \leq 10^5
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
M
A_1
A_2
...
A_N
Output
Print the maximum possible happiness after
M
handshakes.
Sample Input 1
5 3
10 14 19 34 33
Sample Output 1
202
Let us say that Takahashi performs the following handshakes:
In the first handshake, Takahashi shakes the left hand of Guest
4
and the right hand of Guest
4
.
In the second handshake, Takahashi shakes the left hand of Guest
4
and the right hand of Guest
5
.
In the third handshake, Takahashi shakes the left hand of Guest
5
and the right hand of Guest
4
.
Then, we will have the happiness of
(34+34)+(34+33)+(33+34)=202
.
We cannot achieve the happiness of
203
or greater, so the answer is
202
.
Sample Input 2
9 14
1 3 5 110 24 21 34 5 3
Sample Output 2
1837
Sample Input 3
9 73
67597 52981 5828 66249 75177 64141 40773 79105 16076
Sample Output 3
8128170
Problem Description: Score : 600 points
Problem Statement
Given is a tree
T
with
N
vertices. The
i
-th edge connects Vertex
A_i
and
B_i
(
1 \leq A_i,B_i \leq N
).
Now, each vertex is painted black with probability
1/2
and white with probability
1/2
, which is chosen independently from other vertices. Then, let
S
be the smallest subtree (connected subgraph) of
T
containing all the vertices painted black. (If no vertex is painted black,
S
is the empty graph.)
Let the
holeyness
of
S
be the number of white vertices contained in
S
. Find the expected holeyness of
S
.
Since the answer is a rational number, we ask you to print it
\bmod 10^9+7
, as described in Notes.
Notes
When you print a rational number, first write it as a fraction
\frac{y}{x}
, where
x, y
are integers, and
x
is not divisible by
10^9 + 7
(under the constraints of the problem, such representation is always possible).
Then, you need to print the only integer
z
between
0
and
10^9 + 6
, inclusive, that satisfies
xz \equiv y \pmod{10^9 + 7}
.
Constraints
2 \leq N \leq 2 \times 10^5
1 \leq A_i,B_i \leq N
The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N
A_1
B_1
:
A_{N-1}
B_{N-1}
Output
Print the expected holeyness of
S
,
\bmod 10^9+7
.
Sample Input 1
3
1 2
2 3
Sample Output 1
125000001
If the vertices
1, 2, 3
are painted black, white, black, respectively, the holeyness of
S
is
1
.
Otherwise, the holeyness is
0
, so the expected holeyness is
1/8
.
Since
8 \times 125000001 \equiv 1 \pmod{10^9+7}
, we should print
125000001
.
Sample Input 2
4
1 2
2 3
3 4
Sample Output 2
375000003
The expected holeyness is
3/8
.
Since
8 \times 375000003 \equiv 3 \pmod{10^9+7}
, we should print
375000003
.
Sample Input 3
4
1 2
1 3
1 4
Sample Output 3
250000002
The expected holeyness is
1/4
.
Sample Input 4
7
4 7
3 1
2 6
5 2
7 1
2 7
Sample Output 4
570312505
Problem Description: Score : 300 points
Problem Statement
2N
players are running a competitive table tennis training on
N
tables numbered from
1
to
N
.
The training consists of
rounds
.
In each round, the players form
N
pairs, one pair per table.
In each pair, competitors play a match against each other.
As a result, one of them wins and the other one loses.
The winner of the match on table
X
plays on table
X-1
in the next round,
except for the winner of the match on table
1
who stays at table
1
.
Similarly, the loser of the match on table
X
plays on table
X+1
in the next round,
except for the loser of the match on table
N
who stays at table
N
.
Two friends are playing their first round matches on distinct tables
A
and
B
.
Let's assume that the friends are strong enough to win or lose any match at will.
What is the smallest number of rounds after which the friends can get to play a match against each other?
Constraints
2 \leq N \leq 10^{18}
1 \leq A < B \leq N
All input values are integers.
Input
Input is given from Standard Input in the following format:
N
A
B
Output
Print the smallest number of rounds after which the friends can get to play a match against each other.
Sample Input 1
5 2 4
Sample Output 1
1
If the first friend loses their match and the second friend wins their match, they will both move to table
3
and play each other in the next round.
Sample Input 2
5 2 3
Sample Output 2
2
If both friends win two matches in a row, they will both move to table
1
.
Problem Description: Score : 500 points
Problem Statement
For an integer
n
not less than
0
, let us define
f(n)
as follows:
f(n) = 1
(if
n < 2
)
f(n) = n f(n-2)
(if
n \geq 2
)
Given is an integer
N
. Find the number of trailing zeros in the decimal notation of
f(N)
.
Constraints
0 \leq N \leq 10^{18}
Input
Input is given from Standard Input in the following format:
N
Output
Print the number of trailing zeros in the decimal notation of
f(N)
.
Sample Input 1
12
Sample Output 1
1
f(12) = 12 × 10 × 8 × 6 × 4 × 2 = 46080
, which has one trailing zero.
Sample Input 2
5
Sample Output 2
0
f(5) = 5 × 3 × 1 = 15
, which has no trailing zeros.
Sample Input 3
1000000000000000000
Sample Output 3
124999999999999995
Problem Description: Score : 100 points
Problem Statement
Given are three integers
A_1
,
A_2
, and
A_3
.
If
A_1+A_2+A_3
is greater than or equal to
22
, print
bust
; otherwise, print
win
.
Constraints
1 \leq A_i \leq 13 \ \ (i=1,2,3)
All values in input are integers.
Input
Input is given from Standard Input in the following format:
A_1
A_2
A_3
Output
If
A_1+A_2+A_3
is greater than or equal to
22
, print
bust
; otherwise, print
win
.
Sample Input 1
5 7 9
Sample Output 1
win
5+7+9=21
, so print
win
.
Sample Input 2
13 7 2
Sample Output 2
bust
13+7+2=22
, so print
bust
.
Problem Description: Score : 200 points
Problem Statement
Takahashi loves palindromes. Non-palindromic strings are unacceptable to him. Each time he hugs a string, he can change one of its characters to any character of his choice.
Given is a string
S
. Find the minimum number of hugs needed to make
S
palindromic.
Constraints
S
is a string consisting of lowercase English letters.
The length of
S
is between
1
and
100
(inclusive).
Input
Input is given from Standard Input in the following format:
S
Output
Print the minimum number of hugs needed to make
S
palindromic.
Sample Input 1
redcoder
Sample Output 1
1
For example, we can change the fourth character to
o
and get a palindrome
redooder
.
Sample Input 2
vvvvvv
Sample Output 2
0
We might need no hugs at all.
Sample Input 3
abcdabc
Sample Output 3
2
Problem Description: Score : 300 points
Problem Statement
There are
N
people numbered
1
to
N
. Each of them is either an
honest
person whose testimonies are always correct or an
unkind
person whose testimonies may be correct or not.
Person
i
gives
A_i
testimonies. The
j
-th testimony by Person
i
is represented by two integers
x_{ij}
and
y_{ij}
. If
y_{ij} = 1
, the testimony says Person
x_{ij}
is honest; if
y_{ij} = 0
, it says Person
x_{ij}
is unkind.
How many honest persons can be among those
N
people at most?
Constraints
All values in input are integers.
1 \leq N \leq 15
0 \leq A_i \leq N - 1
1 \leq x_{ij} \leq N
x_{ij} \neq i
x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)
y_{ij} = 0, 1
Input
Input is given from Standard Input in the following format:
N
A_1
x_{11}
y_{11}
x_{12}
y_{12}
:
x_{1A_1}
y_{1A_1}
A_2
x_{21}
y_{21}
x_{22}
y_{22}
:
x_{2A_2}
y_{2A_2}
:
A_N
x_{N1}
y_{N1}
x_{N2}
y_{N2}
:
x_{NA_N}
y_{NA_N}
Output
Print the maximum possible number of honest persons among the
N
people.
Sample Input 1
3
1
2 1
1
1 1
1
2 0
Sample Output 1
2
If Person
1
and Person
2
are honest and Person
3
is unkind, we have two honest persons without inconsistencies, which is the maximum possible number of honest persons.
Sample Input 2
3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0
Sample Output 2
0
Assuming that one or more of them are honest immediately leads to a contradiction.
Sample Input 3
2
1
2 0
1
1 0
Sample Output 3
1
Problem Description: Score : 500 points
Problem Statement
We have a grid with
H
horizontal rows and
W
vertical columns. Let
(i,j)
denote the square at the
i
-th row from the top and the
j
-th column from the left.
The square
(i, j)
has two numbers
A_{ij}
and
B_{ij}
written on it.
First, for each square, Takahashi paints one of the written numbers red and the other blue.
Then, he travels from the square
(1, 1)
to the square
(H, W)
. In one move, he can move from a square
(i, j)
to the square
(i+1, j)
or the square
(i, j+1)
. He must not leave the grid.
Let the
unbalancedness
be the absolute difference of the sum of red numbers and the sum of blue numbers written on the squares along Takahashi's path, including the squares
(1, 1)
and
(H, W)
.
Takahashi wants to make the unbalancedness as small as possible by appropriately painting the grid and traveling on it.
Find the minimum unbalancedness possible.
Constraints
2 \leq H \leq 80
2 \leq W \leq 80
0 \leq A_{ij} \leq 80
0 \leq B_{ij} \leq 80
All values in input are integers.
Input
Input is given from Standard Input in the following format:
H
W
A_{11}
A_{12}
\ldots
A_{1W}
:
A_{H1}
A_{H2}
\ldots
A_{HW}
B_{11}
B_{12}
\ldots
B_{1W}
:
B_{H1}
B_{H2}
\ldots
B_{HW}
Output
Print the minimum unbalancedness possible.
Sample Input 1
2 2
1 2
3 4
3 4
2 1
Sample Output 1
0
By painting the grid and traveling on it as shown in the figure below, the sum of red numbers and the sum of blue numbers are
3+3+1=7
and
1+2+4=7
, respectively, for the unbalancedness of
0
.
Sample Input 2
2 3
1 10 80
80 10 1
1 2 3
4 5 6
Sample Output 2
2
Problem Description: Score : 600 points
Problem Statement
We have an integer sequence
A
of length
N
, where
A_1 = X, A_{i+1} = A_i + D (1 \leq  i < N )
holds.
Takahashi will take some (possibly all or none) of the elements in this sequence, and Aoki will take all of the others.
Let
S
and
T
be the sum of the numbers taken by Takahashi and Aoki, respectively. How many possible values of
S - T
are there?
Constraints
-10^8 \leq X, D \leq 10^8
1 \leq N \leq 2 \times 10^5
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
X
D
Output
Print the number of possible values of
S - T
.
Sample Input 1
3 4 2
Sample Output 1
8
A
is
(4, 6, 8)
.
There are eight ways for (Takahashi, Aoki) to take the elements:
((), (4, 6, 8)), ((4), (6, 8)), ((6), (4, 8)), ((8), (4, 6))), ((4, 6), (8))), ((4, 8), (6))), ((6, 8), (4)))
, and
((4, 6, 8), ())
.
The values of
S - T
in these ways are
-18, -10, -6, -2, 2, 6, 10
, and
18
, respectively, so there are eight possible values of
S - T
.
Sample Input 2
2 3 -3
Sample Output 2
2
A
is
(3, 0)
. There are two possible values of
S - T
:
-3
and
3
.
Sample Input 3
100 14 20
Sample Output 3
49805
Problem Description: Score: 100 points
Problem Statement
In this problem, a date is written as Y-M-D. For example,
2019
-
11
-
30
means November
30
,
2019
.
Integers
M_1, D_1, M_2
, and
D_2
will be given as input.
It is known that the date
2019
-
M_2
-
D_2
follows
2019
-
M_1
-
D_1
.
Determine whether the date
2019
-
M_1
-
D_1
is the last day of a month.
Constraints
Both
2019
-
M_1
-
D_1
and
2019
-
M_2
-
D_2
are valid dates in the Gregorian calendar.
The date
2019
-
M_2
-
D_2
follows
2019
-
M_1
-
D_1
.
Input
Input is given from Standard Input in the following format:
M_1
D_1
M_2
D_2
Output
If the date
2019
-
M_1
-
D_1
is the last day of a month, print
1
; otherwise, print
0
.
Sample Input 1
11 16
11 17
Sample Output 1
0
November
16
is not the last day of a month.
Sample Input 2
11 30
12 1
Sample Output 2
1
November
30
is the last day of November.
Problem Description: Score: 300 points
Problem Statement
AtCoder Mart sells
1000000
of each of the six items below:
Riceballs, priced at
100
yen (the currency of Japan) each
Sandwiches, priced at
101
yen each
Cookies, priced at
102
yen each
Cakes, priced at
103
yen each
Candies, priced at
104
yen each
Computers, priced at
105
yen each
Takahashi wants to buy some of them that cost exactly
X
yen in total.
Determine whether this is possible.
(Ignore consumption tax.)
Constraints
1 \leq X \leq 100000
X
is an integer.
Input
Input is given from Standard Input in the following format:
X
Output
If it is possible to buy some set of items that cost exactly
X
yen in total, print
1
; otherwise, print
0
.
Sample Input 1
615
Sample Output 1
1
For example, we can buy one of each kind of item, which will cost
100+101+102+103+104+105=615
yen in total.
Sample Input 2
217
Sample Output 2
0
No set of items costs
217
yen in total.
Problem Description: Score: 400 points
Problem Statement
AtCoder Inc. has decided to lock the door of its office with a
3
-digit PIN code.
The company has an
N
-digit lucky number,
S
. Takahashi, the president, will erase
N-3
digits from
S
and concatenate the remaining
3
digits without changing the order to set the PIN code.
How many different PIN codes can he set this way?
Both the lucky number and the PIN code may begin with a
0
.
Constraints
4 \leq N \leq 30000
S
is a string of length
N
consisting of digits.
Input
Input is given from Standard Input in the following format:
N
S
Output
Print the number of different PIN codes Takahashi can set.
Sample Input 1
4
0224
Sample Output 1
3
Takahashi has the following options:
Erase the first digit of
S
and set
224
.
Erase the second digit of
S
and set
024
.
Erase the third digit of
S
and set
024
.
Erase the fourth digit of
S
and set
022
.
Thus, he can set three different PIN codes:
022
,
024
, and
224
.
Sample Input 2
6
123123
Sample Output 2
17
Sample Input 3
19
3141592653589793238
Sample Output 3
329
Problem Description: Score: 500 points
Problem Statement
N
people are standing in a queue, numbered
1, 2, 3, ..., N
from front to back. Each person wears a hat, which is red, blue, or green.
The person numbered
i
says:
"In front of me, exactly
A_i
people are wearing hats with the same color as mine."
Assuming that all these statements are correct, find the number of possible combinations of colors of the
N
people's hats.
Since the count can be enormous, compute it modulo
1000000007
.
Constraints
1 \leq N \leq 100000
0 \leq A_i \leq N-1
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1
A_2
A_3
...
A_N
Output
Print the number of possible combinations of colors of the
N
people's hats, modulo
1000000007
.
Sample Input 1
6
0 1 2 3 4 5
Sample Output 1
3
We have three possible combinations, as follows:
Red, Red, Red, Red, Red, Red
Blue, Blue, Blue, Blue, Blue, Blue
Green, Green, Green, Green, Green, Green
Sample Input 2
3
0 0 0
Sample Output 2
6
Sample Input 3
54
0 0 1 0 1 2 1 2 3 2 3 3 4 4 5 4 6 5 7 8 5 6 6 7 7 8 8 9 9 10 10 11 9 12 10 13 14 11 11 12 12 13 13 14 14 15 15 15 16 16 16 17 17 17
Sample Output 3
115295190
Problem Description: Score: 600 points
Problem Statement
Takahashi and Aoki are training for long-distance races in an infinitely long straight course running from west to east.
They start simultaneously at the same point and moves as follows
towards the east
:
Takahashi runs
A_1
meters per minute for the first
T_1
minutes,  then runs at
A_2
meters per minute for the subsequent
T_2
minutes, and alternates between these two modes forever.
Aoki runs
B_1
meters per minute for the first
T_1
minutes,  then runs at
B_2
meters per minute for the subsequent
T_2
minutes, and alternates between these two modes forever.
How many times will Takahashi and Aoki meet each other, that is, come to the same point? We do not count the start of the run. If they meet infinitely many times, report that fact.
Constraints
1 \leq T_i \leq 100000
1 \leq A_i \leq 10^{10}
1 \leq B_i \leq 10^{10}
A_1 \neq B_1
A_2 \neq B_2
All values in input are integers.
Input
Input is given from Standard Input in the following format:
T_1
T_2
A_1
A_2
B_1
B_2
Output
Print the number of times Takahashi and Aoki will meet each other.
If they meet infinitely many times, print
infinity
instead.
Sample Input 1
1 2
10 10
12 4
Sample Output 1
1
They will meet just once,
\frac{4}{3}
minutes after they start, at
\frac{40}{3}
meters from where they start.
Sample Input 2
100 1
101 101
102 1
Sample Output 2
infinity
They will meet
101, 202, 303, 404, 505, 606, ...
minutes after they start, that is, they will meet infinitely many times.
Sample Input 3
12000 15700
3390000000 3810000000
5550000000 2130000000
Sample Output 3
113
The values in input may not fit into a
32
-bit integer type.
Problem Description: Score : 100 points
Problem Statement
Given is a string
S
representing the day of the week today.
S
is
SUN
,
MON
,
TUE
,
WED
,
THU
,
FRI
, or
SAT
, for Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday, respectively.
After how many days is the next Sunday (tomorrow or later)?
Constraints
S
is
SUN
,
MON
,
TUE
,
WED
,
THU
,
FRI
, or
SAT
.
Input
Input is given from Standard Input in the following format:
S
Output
Print the number of days before the next Sunday.
Sample Input 1
SAT
Sample Output 1
1
It is Saturday today, and tomorrow will be Sunday.
Sample Input 2
SUN
Sample Output 2
7
It is Sunday today, and seven days later, it will be Sunday again.
Problem Description: Score : 200 points
Problem Statement
We have a string
S
consisting of uppercase English letters. Additionally, an integer
N
will be given.
Shift each character of
S
by
N
in alphabetical order (see below), and print the resulting string.
We assume that
A
follows
Z
. For example, shifting
A
by
2
results in
C
(
A
\to
B
\to
C
), and shifting
Y
by
3
results in
B
(
Y
\to
Z
\to
A
\to
B
).
Constraints
0 \leq N \leq 26
1 \leq |S| \leq 10^4
S
consists of uppercase English letters.
Input
Input is given from Standard Input in the following format:
N
S
Output
Print the string resulting from shifting each character of
S
by
N
in alphabetical order.
Sample Input 1
2
ABCXYZ
Sample Output 1
CDEZAB
Note that
A
follows
Z
.
Sample Input 2
0
ABCXYZ
Sample Output 2
ABCXYZ
Sample Input 3
13
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Sample Output 3
NOPQRSTUVWXYZABCDEFGHIJKLM
Problem Description: Score : 400 points
Problem Statement
Given is a tree
G
with
N
vertices.
The vertices are numbered
1
through
N
, and the
i
-th edge connects Vertex
a_i
and Vertex
b_i
.
Consider painting the edges in
G
with some number of colors.
We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.
Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.
Constraints
2 \le N \le 10^5
1 \le a_i \lt b_i \le N
All values in input are integers.
The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N
a_1
b_1
a_2
b_2
\vdots
a_{N-1}
b_{N-1}
Output
Print
N
lines.
The first line should contain
K
, the number of colors used.
The
(i+1)
-th line
(1 \le i \le N-1)
should contain
c_i
, the integer representing the color of the
i
-th edge, where
1 \le c_i \le K
must hold.
If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.
Sample Input 1
3
1 2
2 3
Sample Output 1
2
1
2
Sample Input 2
8
1 2
2 3
2 4
2 5
4 7
5 6
6 8
Sample Output 2
4
1
2
3
4
1
1
2
Sample Input 3
6
1 2
1 3
1 4
1 5
1 6
Sample Output 3
5
1
2
3
4
5
Problem Description: Score : 500 points
Problem Statement
Given are a sequence of
N
positive integers
A_1, A_2, \ldots, A_N
, and a positive integer
K
.
Find the number of non-empty contiguous subsequences in
A
such that the remainder when dividing the sum of its elements by
K
is equal to the number of its elements. We consider two subsequences different if they are taken from different positions, even if they are equal sequences.
Constraints
All values in input are integers.
1 \leq N \leq 2\times 10^5
1 \leq K \leq 10^9
1 \leq A_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N
K
A_1
A_2
\cdots
A_N
Output
Print the number of subsequences that satisfy the condition.
Sample Input 1
5 4
1 4 2 3 5
Sample Output 1
4
Four sequences satisfy the condition:
(1)
,
(4,2)
,
(1,4,2)
, and
(5)
.
Sample Input 2
8 4
4 2 4 2 4 2 4 2
Sample Output 2
7
(4,2)
is counted four times, and
(2,4)
is counted three times.
Sample Input 3
10 7
14 15 92 65 35 89 79 32 38 46
Sample Output 3
8