CodeEff/ECCO huggingface dataset:
Problem Description: Score : 700 points
Problem Statement
Find the smallest possible sum of the digits in the decimal notation of a positive multiple of
K
.
Constraints
2 \leq K \leq 10^5
K
is an integer.
Input
Input is given from Standard Input in the following format:
K
Output
Print the smallest possible sum of the digits in the decimal notation of a positive multiple of
K
.
Sample Input 1
6
Sample Output 1
3
12=6×2
yields the smallest sum.
Sample Input 2
41
Sample Output 2
5
11111=41×271
yields the smallest sum.
Sample Input 3
79992
Sample Output 3
36
Problem Description: Score : 100 points
Problem Statement
Takahashi is a user of a site that hosts programming contests.
When a user competes in a contest, the
rating
of the user (not necessarily an integer) changes according to the
performance
of the user, as follows:
Let the current rating of the user be
a
.
Suppose that the performance of the user in the contest is
b
.
Then, the new rating of the user will be the avarage of
a
and
b
.
For example, if a user with rating
1
competes in a contest and gives performance
1000
, his/her new rating will be
500.5
, the average of
1
and
1000
.
Takahashi's current rating is
R
, and he wants his rating to be exactly
G
after the next contest.
Find the performance required to achieve it.
Constraints
0 \leq R, G \leq 4500
All input values are integers.
Input
Input is given from Standard Input in the following format:
R
G
Output
Print the performance required to achieve the objective.
Sample Input 1
2002
2017
Sample Output 1
2032
Takahashi's current rating is
2002
.
If his performance in the contest is
2032
, his rating will be the average of
2002
and
2032
, which is equal to the desired rating,
2017
.
Sample Input 2
4500
0
Sample Output 2
-4500
Although the current and desired ratings are between
0
and
4500
, the performance of a user can be below
0
.
Problem Description: Score : 200 points
Problem Statement
Square1001 has seen an electric bulletin board displaying the integer
1
.
He can perform the following operations A and B to change this value:
Operation A: The displayed value is doubled.
Operation B: The displayed value increases by
K
.
Square1001 needs to perform these operations
N
times in total.
Find the minimum possible value displayed in the board after
N
operations.
Constraints
1 \leq N, K \leq 10
All input values are integers.
Input
Input is given from Standard Input in the following format:
N
K
Output
Print the minimum possible value displayed in the board after
N
operations.
Sample Input 1
4
3
Sample Output 1
10
The value will be minimized when the operations are performed in the following order: A, A, B, B.
In this case, the value will change as follows:
1
→
2
→
4
→
7
→
10
.
Sample Input 2
10
10
Sample Output 2
76
The value will be minimized when the operations are performed in the following order: A, A, A, A, B, B, B, B, B, B.
In this case, the value will change as follows:
1
→
2
→
4
→
8
→
16
→
26
→
36
→
46
→
56
→
66
→
76
.
By the way, this contest is AtCoder Beginner Contest 076.
Problem Description: Score : 300 points
Problem Statement
E869120 found a chest which is likely to contain treasure.
However, the chest is locked. In order to open it, he needs to enter a string
S
consisting of lowercase English letters.
He also found a string
S'
, which turns out to be the string
S
with some of its letters (possibly all or none) replaced with
?
.
One more thing he found is a sheet of paper with the following facts written on it:
Condition 1: The string
S
contains a string
T
as a contiguous substring.
Condition 2:
S
is the lexicographically smallest string among the ones that satisfy Condition 1.
Print the string
S
.
If such a string does not exist, print
UNRESTORABLE
.
Constraints
1 \leq |S'|, |T| \leq 50
S'
consists of lowercase English letters and
?
.
T
consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
T'
Output
Print the string
S
.
If such a string does not exist, print
UNRESTORABLE
instead.
Sample Input 1
?tc????
coder
Sample Output 1
atcoder
There are
26
strings that satisfy Condition 1:
atcoder
,
btcoder
,
ctcoder
,...,
ztcoder
.
Among them, the lexicographically smallest is
atcoder
, so we can say
S =
atcoder
.
Sample Input 2
??p??d??
abc
Sample Output 2
UNRESTORABLE
There is no string that satisfies Condition 1, so the string
S
does not exist.
Problem Description: Score : 200 points
Problem Statement
We will say that two integer sequences of length
N
,
x_1, x_2, ..., x_N
and
y_1, y_2, ..., y_N
, are
similar
when
|x_i - y_i| \leq 1
holds for all
i
(
1 \leq i \leq N
).
In particular, any integer sequence is similar to itself.
You are given an integer
N
and an integer sequence of length
N
,
A_1, A_2, ..., A_N
.
How many integer sequences
b_1, b_2, ..., b_N
are there such that
b_1, b_2, ..., b_N
is similar to
A
and the product of all elements,
b_1 b_2 ... b_N
, is even?
Constraints
1 \leq N \leq 10
1 \leq A_i \leq 100
Input
Input is given from Standard Input in the following format:
N
A_1
A_2
...
A_N
Output
Print the number of integer sequences that satisfy the condition.
Sample Input 1
2
2 3
Sample Output 1
7
There are seven integer sequences that satisfy the condition:
1, 2
1, 4
2, 2
2, 3
2, 4
3, 2
3, 4
Sample Input 2
3
3 3 3
Sample Output 2
26
Sample Input 3
1
100
Sample Output 3
1
Sample Input 4
10
90 52 56 71 44 8 13 30 57 84
Sample Output 4
58921
Problem Description: Score : 400 points
Problem Statement
We have a string
s
consisting of lowercase English letters.
Snuke can perform the following operation repeatedly:
Insert a letter
x
to any position in
s
of his choice, including the beginning and end of
s
.
Snuke's objective is to turn
s
into a palindrome.
Determine whether the objective is achievable. If it is achievable, find the minimum number of operations required.
Notes
A
palindrome
is a string that reads the same forward and backward.
For example,
a
,
aa
,
abba
and
abcba
are palindromes, while
ab
,
abab
and
abcda
are not.
Constraints
1 \leq |s| \leq 10^5
s
consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
s
Output
If the objective is achievable, print the number of operations required.
If it is not, print
-1
instead.
Sample Input 1
xabxa
Sample Output 1
2
One solution is as follows (newly inserted
x
are shown in bold):
xabxa → xa
x
bxa → xaxbxa
x
Sample Input 2
ab
Sample Output 2
-1
No sequence of operations can turn
s
into a palindrome.
Sample Input 3
a
Sample Output 3
0
s
is a palindrome already at the beginning.
Sample Input 4
oxxx
Sample Output 4
3
One solution is as follows:
oxxx →
x
oxxx →
x
xoxxx →
x
xxoxxx
Problem Description: Score : 700 points
Problem Statement
We have a string
s
consisting of lowercase English letters.
Snuke is partitioning
s
into some number of non-empty substrings.
Let the subtrings obtained be
s_1
,
s_2
,
...
,
s_N
from left to right. (Here,
s = s_1 + s_2 + ... + s_N
holds.)
Snuke wants to satisfy the following condition:
For each
i
(
1 \leq i \leq N
), it is possible to permute the characters in
s_i
and obtain a palindrome.
Find the minimum possible value of
N
when the partition satisfies the condition.
Constraints
1 \leq |s| \leq 2 \times 10^5
s
consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
s
Output
Print the minimum possible value of
N
when the partition satisfies the condition.
Sample Input 1
aabxyyzz
Sample Output 1
2
The solution is to partition
s
as
aabxyyzz
=
aab
+
xyyzz
.
Here,
aab
can be permuted to form a palindrome
aba
, and
xyyzz
can be permuted to form a palindrome
zyxyz
.
Sample Input 2
byebye
Sample Output 2
1
byebye
can be permuted to form a palindrome
byeeyb
.
Sample Input 3
abcdefghijklmnopqrstuvwxyz
Sample Output 3
26
Sample Input 4
abcabcxabcx
Sample Output 4
3
The solution is to partition
s
as
abcabcxabcx
=
a
+
b
+
cabcxabcx
.
Problem Description: Score : 100 points
Problem Statement
You are given three integers,
A
,
B
and
C
.
Among them, two are the same, but the remaining one is different from the rest.
For example, when
A=5,B=7,C=5
,
A
and
C
are the same, but
B
is different.
Find the one that is different from the rest among the given three integers.
Constraints
-100 \leq A,B,C \leq 100
A
,
B
and
C
are integers.
The input satisfies the condition in the statement.
Input
Input is given from Standard Input in the following format:
A
B
C
Output
Among
A
,
B
and
C
, print the integer that is different from the rest.
Sample Input 1
5 7 5
Sample Output 1
7
This is the same case as the one in the statement.
Sample Input 2
1 1 7
Sample Output 2
7
In this case,
C
is the one we seek.
Sample Input 3
-100 100 100
Sample Output 3
-100
Problem Description: Score : 300 points
Problem Statement
You are given an undirected connected graph with
N
vertices and
M
edges that does not contain self-loops and double edges.
The
i
-th edge
(1 \leq i \leq M)
connects Vertex
a_i
and Vertex
b_i
.
An edge whose removal disconnects the graph is called a
bridge
.
Find the number of the edges that are bridges among the
M
edges.
Notes
A
self-loop
is an edge
i
such that
a_i=b_i
(1 \leq i \leq M)
.
Double edges
are a pair of edges
i,j
such that
a_i=a_j
and
b_i=b_j
(1 \leq i<j \leq M)
.
An undirected graph is said to be
connected
when there exists a path between every pair of vertices.
Constraints
2 \leq N \leq 50
N-1 \leq M \leq min(N(N−1)⁄2,50)
1 \leq a_i<b_i \leq N
The given graph does not contain self-loops and double edges.
The given graph is connected.
Input
Input is given from Standard Input in the following format:
N
M
a_1
b_1
a_2
b_2
:
a_M
b_M
Output
Print the number of the edges that are bridges among the
M
edges.
Sample Input 1
7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7
Sample Output 1
4
The figure below shows the given graph:
The edges shown in red are bridges. There are four of them.
Sample Input 2
3 3
1 2
1 3
2 3
Sample Output 2
0
It is possible that there is no bridge.
Sample Input 3
6 5
1 2
2 3
3 4
4 5
5 6
Sample Output 3
5
It is possible that every edge is a bridge.
Problem Description: Score : 400 points
Problem Statement
We have
N
points in a two-dimensional plane.
The coordinates of the
i
-th point
(1 \leq i \leq N)
are
(x_i,y_i)
.
Let us consider a rectangle whose sides are parallel to the coordinate axes that contains
K
or more of the
N
points in its interior.
Here, points on the sides of the rectangle are considered to be in the interior.
Find the minimum possible area of such a rectangle.
Constraints
2 \leq K \leq N \leq 50
-10^9 \leq x_i,y_i \leq 10^9 (1 \leq i \leq N)
x_i≠x_j (1 \leq i<j \leq N)
y_i≠y_j (1 \leq i<j \leq N)
All input values are integers. (Added at 21:50 JST)
Input
Input is given from Standard Input in the following format:
N
K
x_1
y_1
:
x_{N}
y_{N}
Output
Print the minimum possible area of a rectangle that satisfies the condition.
Sample Input 1
4 4
1 4
3 3
6 2
8 1
Sample Output 1
21
One rectangle that satisfies the condition with the minimum possible area has the following vertices:
(1,1)
,
(8,1)
,
(1,4)
and
(8,4)
.
Its area is
(8-1) × (4-1) = 21
.
Sample Input 2
4 2
0 0
1 1
2 2
3 3
Sample Output 2
1
Sample Input 3
4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999
Sample Output 3
3999999996000000001
Watch out for integer overflows.
Problem Description: Score : 200 points
Problem Statement
Rng is preparing a problem set for a qualification round of CODEFESTIVAL.
He has
N
candidates of problems. The difficulty of the
i
-th candidate is
D_i
.
There must be
M
problems in the problem set, and the difficulty of the
i
-th problem must be
T_i
. Here, one candidate of a problem cannot be used as multiple problems.
Determine whether Rng can complete the problem set without creating new candidates of problems.
Constraints
1 \leq N \leq 200,000
1 \leq D_i \leq 10^9
1 \leq M \leq 200,000
1 \leq T_i \leq 10^9
All numbers in the input are integers.
Partial Score
100
points will be awarded for passing the test set satisfying
N \leq 100
and
M \leq 100
.
Input
Input is given from Standard Input in the following format:
N
D_1
D_2
...
D_N
M
T_1
T_2
...
T_M
Output
Print
YES
if Rng can complete the problem set without creating new candidates of problems; print
NO
if he cannot.
Sample Input 1
5
3 1 4 1 5
3
5 4 3
Sample Output 1
YES
Sample Input 2
7
100 200 500 700 1200 1600 2000
6
100 200 500 700 1600 1600
Sample Output 2
NO
Not enough
1600
s.
Sample Input 3
1
800
5
100 100 100 100 100
Sample Output 3
NO
Sample Input 4
15
1 2 2 3 3 3 4 4 4 4 5 5 5 5 5
9
5 4 3 2 1 2 3 4 5
Sample Output 4
YES
Problem Description: Score : 500 points
Problem Statement
Rng has a connected undirected graph with
N
vertices.
Currently, there are
M
edges in the graph, and the
i
-th edge connects Vertices
A_i
and
B_i
.
Rng will add new edges to the graph by repeating the following operation:
Operation: Choose
u
and
v
(u \neq v)
such that Vertex
v
can be reached by traversing exactly three edges from Vertex
u
, and add an edge connecting Vertices
u
and
v
. It is not allowed to add an edge if there is already an edge connecting Vertices
u
and
v
.
Find the maximum possible number of edges that can be added.
Constraints
2 \leq N \leq 10^5
1 \leq M \leq 10^5
1 \leq A_i,B_i \leq N
The graph has no self-loops or multiple edges.
The graph is connected.
Input
Input is given from Standard Input in the following format:
N
M
A_1
B_1
A_2
B_2
:
A_M
B_M
Output
Find the maximum possible number of edges that can be added.
Sample Input 1
6 5
1 2
2 3
3 4
4 5
5 6
Sample Output 1
4
If we add edges as shown below, four edges can be added, and no more.
Sample Input 2
5 5
1 2
2 3
3 1
5 4
5 1
Sample Output 2
5
Five edges can be added, for example, as follows:
Add an edge connecting Vertex
5
and Vertex
3
.
Add an edge connecting Vertex
5
and Vertex
2
.
Add an edge connecting Vertex
4
and Vertex
1
.
Add an edge connecting Vertex
4
and Vertex
2
.
Add an edge connecting Vertex
4
and Vertex
3
.
Problem Description: Score : 700 points
Problem Statement
N
cells are arranged in a row.
Some of them may contain tokens.
You are given a string
s
that consists of
0
s and
1
s.
If the
i
-th character of
s
is
1
, the
i
-th cell (from left) contains a token.
Otherwise, it doesn't contain a token.
Snuke wants to perform the following operation as many times as possible.
In each operation, he chooses three consecutive cells.
Let's call the cells
X, Y, Z
from left to right.
In order for the operation to be valid, both
X
and
Z
must contain tokens and
Y
must not contain a token.
Then, he removes these two tokens and puts a new token on
Y
.
How many operations can he perform if he performs operations in the optimal way?
Constraints
1 \leq N \leq 500,000
|s| = N
Each character in
s
is either
0
or
1
.
Input
Input is given from Standard Input in the following format:
N
s
Output
Print the answer.
Sample Input 1
7
1010101
Sample Output 1
2
For example, he can perform two operations in the following way:
Perform an operation on the last three cells. Now the string that represents tokens becomes
1010010
.
Perform an operation on the first three cells. Now the string that represents tokens becomes
0100010
.
Note that the choice of operations matters.
For example, if he chooses three cells in the middle first, he can perform no more operations.
Sample Input 2
50
10101000010011011110001001111110000101010111100110
Sample Output 2
10
Problem Description: Score : 500 points
Problem Statement
Seisu-ya
, a store specializing in non-negative integers, sells
N
non-negative integers. The
i
-th integer is
A_i
and has a
utility
of
B_i
.
There may be multiple equal integers with different utilities.
Takahashi will buy some integers in this store. He can buy a combination of integers whose
bitwise OR
is less than or equal to
K
. He wants the sum of utilities of purchased integers to be as large as possible.
Find the maximum possible sum of utilities of purchased integers.
Constraints
1 \leq N \leq 10^5
0 \leq K < 2^{30}
0 \leq A_i < 2^{30}(1\leq i\leq N)
1 \leq B_i \leq 10^9(1\leq i\leq N)
All input values are integers.
Inputs
Input is given from Standard Input in the following format:
N
K
A_1
B_1
:
A_N
B_N
Outputs
Print the maximum possible sum of utilities of purchased integers.
Sample Input 1
3 5
3 3
4 4
2 5
Sample Output 1
8
Buy
2
and
3
to achieve the maximum possible total utility,
8
.
Sample Input 2
3 6
3 3
4 4
2 5
Sample Output 2
9
Buy
2
and
4
to achieve the maximum possible total utility,
9
.
Sample Input 3
7 14
10 5
7 4
11 4
9 8
3 6
6 2
8 9
Sample Output 3
32
Problem Description: Score : 200 points
Problem Statement
A group of people played a game. All players had distinct scores, which are positive integers.
Takahashi knows
N
facts on the players' scores. The
i
-th fact is as follows: the
A_i
-th highest score among the players is
B_i
.
Find the maximum possible number of players in the game.
Constraints
1 \leq N \leq 10^5
1 \leq A_i \leq 10^9(1\leq i\leq N)
0 \leq B_i \leq 10^9(1\leq i\leq N)
If
i ≠ j
,
A_i ≠ A_j
.
There exists a possible outcome of the game that are consistent with the facts.
All input values are integers.
Inputs
Input is given from Standard Input in the following format:
N
A_1
B_1
:
A_N
B_N
Outputs
Print the maximum possible number of players in the game.
Sample Input 1
3
4 7
2 9
6 2
Sample Output 1
8
The maximum possible number of players is achieved when, for example, the players have the following scores:
12,9,8,7,5,2,1,0
.
Sample Input 2
5
1 10
3 6
5 2
4 4
2 8
Sample Output 2
7
Sample Input 3
2
1 1000000000
1000000000 1
Sample Output 3
1000000001
Problem Description: Score : 300 points
Problem Statement
You are given an integer
N
.
Find a triple of positive integers
h
,
n
and
w
such that
4/N = 1/h + 1/n + 1/w
.
If there are multiple solutions, any of them will be accepted.
Constraints
It is guaranteed that, for the given integer
N
, there exists a solution such that
h,n,w \leq 3500
.
Inputs
Input is given from Standard Input in the following format:
N
Outputs
Print a triple of positive integers
h
,
n
and
w
that satisfies the condition, in the following format:
h
n
w
Sample Input 1
2
Sample Output 1
1 2 2
4/2 = 1/1 + 1/2 + 1/2
.
Sample Input 2
3485
Sample Output 2
872 1012974 1539173474040
It is allowed to use an integer exceeding
3500
in a solution.
Sample Input 3
4664
Sample Output 3
3498 3498 3498
Problem Description: Score : 200 points
Problem Statement
We have a grid with
N
rows and
M
columns of squares. Initially, all the squares are white.
There is a button attached to each row and each column.
When a button attached to a row is pressed, the colors of all the squares in that row are inverted; that is, white squares become black and vice versa.
When a button attached to a column is pressed, the colors of all the squares in that column are inverted.
Takahashi can freely press the buttons any number of times. Determine whether he can have exactly
K
black squares in the grid.
Constraints
1 \leq N,M \leq 1000
0 \leq K \leq NM
Input
Input is given from Standard Input in the following format:
N
M
K
Output
If Takahashi can have exactly
K
black squares in the grid, print
Yes
; otherwise, print
No
.
Sample Input 1
2 2 2
Sample Output 1
Yes
Press the buttons in the order of the first row, the first column.
Sample Input 2
2 2 1
Sample Output 2
No
Sample Input 3
3 5 8
Sample Output 3
Yes
Press the buttons in the order of the first column, third column, second row, fifth column.
Sample Input 4
7 9 20
Sample Output 4
No
Problem Description: Score : 400 points
Problem Statement
We have an
H
-by-
W
matrix.
Let
a_{ij}
be the element at the
i
-th row from the top and
j
-th column from the left.
In this matrix, each
a_{ij}
is a lowercase English letter.
Snuke is creating another
H
-by-
W
matrix,
A'
, by freely rearranging the elements in
A
.
Here, he wants to satisfy the following condition:
Every row and column in
A'
can be read as a palindrome.
Determine whether he can create a matrix satisfying the condition.
Note
A
palindrome
is a string that reads the same forward and backward.
For example,
a
,
aa
,
abba
and
abcba
are all palindromes, while
ab
,
abab
and
abcda
are not.
Constraints
1 ≤ H, W ≤ 100
a_{ij}
is a lowercase English letter.
Input
Input is given from Standard Input in the following format:
H
W
a_{11}
a_{12}
...
a_{1W}
:
a_{H1}
a_{H2}
...
a_{HW}
Output
If Snuke can create a matrix satisfying the condition, print
Yes
; otherwise, print
No
.
Sample Input 1
3 4
aabb
aabb
aacc
Sample Output 1
Yes
For example, the following matrix satisfies the condition.
abba
acca
abba
Sample Input 2
2 2
aa
bb
Sample Output 2
No
It is not possible to create a matrix satisfying the condition, no matter how we rearrange the elements in
A
.
Sample Input 3
5 1
t
w
e
e
t
Sample Output 3
Yes
For example, the following matrix satisfies the condition.
t
e
w
e
t
Sample Input 4
2 5
abxba
abyba
Sample Output 4
No
Sample Input 5
1 1
z
Sample Output 5
Yes
Problem Description: Score : 100 points
Problem Statement
We have an
N \times N
square grid.
We will paint each square in the grid either black or white.
If we paint exactly
A
squares white, how many squares will be painted black?
Constraints
1 \leq N \leq 100
0 \leq A \leq N^2
Inputs
Input is given from Standard Input in the following format:
N
A
Outputs
Print the number of squares that will be painted black.
Sample Input 1
3
4
Sample Output 1
5
There are nine squares in a
3 \times 3
square grid.
Four of them will be painted white, so the remaining five squares will be painted black.
Sample Input 2
19
100
Sample Output 2
261
Sample Input 3
10
0
Sample Output 3
100
As zero squares will be painted white, all the squares will be painted black.
Problem Description: Score : 200 points
Problem Statement
There are
N
balls in the
xy
-plane. The coordinates of the
i
-th of them is
(x_i, i)
.
Thus, we have one ball on each of the
N
lines
y = 1
,
y = 2
,
...
,
y = N
.
In order to collect these balls, Snuke prepared
2N
robots,
N
of type A and
N
of type B.
Then, he placed the
i
-th type-A robot at coordinates
(0, i)
, and the
i
-th type-B robot at coordinates
(K, i)
.
Thus, now we have one type-A robot and one type-B robot on each of the
N
lines
y = 1
,
y = 2
,
...
,
y = N
.
When activated, each type of robot will operate as follows.
When a type-A robot is activated at coordinates
(0, a)
, it will move to the position of the ball on the line
y = a
, collect the ball, move back to its original position
(0, a)
and deactivate itself. If there is no such ball, it will just deactivate itself without doing anything.
When a type-B robot is activated at coordinates
(K, b)
, it will move to the position of the ball on the line
y = b
, collect the ball, move back to its original position
(K, b)
and deactivate itself. If there is no such ball, it will just deactivate itself without doing anything.
Snuke will activate some of the
2N
robots to collect all of the balls. Find the minimum possible total distance covered by robots.
Constraints
1 \leq N \leq 100
1 \leq K \leq 100
0 < x_i < K
All input values are integers.
Inputs
Input is given from Standard Input in the following format:
N
K
x_1
x_2
...
x_N
Outputs
Print the minimum possible total distance covered by robots.
Sample Input 1
1
10
2
Sample Output 1
4
There are just one ball, one type-A robot and one type-B robot.
If the type-A robot is used to collect the ball, the distance from the robot to the ball is
2
, and the distance from the ball to the original position of the robot is also
2
, for a total distance of
4
.
Similarly, if the type-B robot is used, the total distance covered will be
16
.
Thus, the total distance covered will be minimized when the type-A robot is used. The output should be
4
.
Sample Input 2
2
9
3 6
Sample Output 2
12
The total distance covered will be minimized when the first ball is collected by the type-A robot, and the second ball by the type-B robot.
Sample Input 3
5
20
11 12 9 17 12
Sample Output 3
74