CodeEff/ECCO huggingface dataset:
Problem Description: Score : 600 points
Problem Statement
Takahashi is playing a board game called Sugoroku.
On the board, there are
N + 1
squares numbered
0
to
N
. Takahashi starts at Square
0
, and he has to stop exactly at Square
N
to win the game.
The game uses a roulette with the
M
numbers from
1
to
M
. In each turn, Takahashi spins the roulette. If the number
x
comes up when he is at Square
s
, he moves to Square
s+x
. If this makes him go beyond Square
N
, he loses the game.
Additionally, some of the squares are Game Over Squares. He also loses the game if he stops at one of those squares. You are given a string
S
of length
N + 1
, representing which squares are Game Over Squares. For each
i
(0 \leq i \leq N)
, Square
i
is a Game Over Square if
S[i] = 1
and not if
S[i] = 0
.
Find the sequence of numbers coming up in the roulette in which Takahashi can win the game in the fewest number of turns possible. If there are multiple such sequences, find the lexicographically smallest such sequence. If Takahashi cannot win the game, print
-1
.
Constraints
1 \leq N \leq 10^5
1 \leq M \leq 10^5
|S| = N + 1
S
consists of
0
and
1
.
S[0] =
0
S[N] =
0
Input
Input is given from Standard Input in the following format:
N
M
S
Output
If Takahashi can win the game, print the lexicographically smallest sequence among the shortest sequences of numbers coming up in the roulette in which Takahashi can win the game, with spaces in between.
If Takahashi cannot win the game, print
-1
.
Sample Input 1
9 3
0001000100
Sample Output 1
1 3 2 3
If the numbers
1
,
3
,
2
,
3
come up in this order, Takahashi can reach Square
9
via Square
1
,
4
, and
6
. He cannot reach Square
9
in three or fewer turns, and this is the lexicographically smallest sequence in which he reaches Square
9
in four turns.
Sample Input 2
5 4
011110
Sample Output 2
-1
Takahashi cannot reach Square
5
.
Sample Input 3
6 6
0101010
Sample Output 3
6
Problem Description: Score: 200 points
Problem Statement
Takahashi, who works at DISCO, is standing before an iron bar.
The bar has
N-1
notches, which divide the bar into
N
sections. The
i
-th section from the left has a length of
A_i
millimeters.
Takahashi wanted to choose a notch and cut the bar at that point into two parts with the same length.
However, this may not be possible as is, so he will do the following operations some number of times
before
he does the cut:
Choose one section and expand it, increasing its length by
1
millimeter. Doing this operation once costs
1
yen (the currency of Japan).
Choose one section of length at least
2
millimeters and shrink it, decreasing its length by
1
millimeter. Doing this operation once costs
1
yen.
Find the minimum amount of money needed before cutting the bar into two parts with the same length.
Constraints
2 \leq N \leq 200000
1 \leq A_i \leq 2020202020
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 an integer representing the minimum amount of money needed before cutting the bar into two parts with the same length.
Sample Input 1
3
2 4 3
Sample Output 1
3
The initial lengths of the sections are
[2, 4, 3]
(in millimeters). Takahashi can cut the bar equally after doing the following operations for
3
yen:
Shrink the second section from the left. The lengths of the sections are now
[2, 3, 3]
.
Shrink the first section from the left. The lengths of the sections are now
[1, 3, 3]
.
Shrink the second section from the left. The lengths of the sections are now
[1, 2, 3]
, and we can cut the bar at the second notch from the left into two parts of length
3
each.
Sample Input 2
12
100 104 102 105 103 103 101 105 104 102 104 101
Sample Output 2
0
Problem Description: Score: 500 points
Problem Statement
N
programmers are going to participate in the preliminary stage of DDCC 20XX. Due to the size of the venue, however, at most
9
contestants can participate in the finals.
The preliminary stage consists of several rounds, which will take place as follows:
All the
N
contestants will participate in the first round.
When
X
contestants participate in some round, the number of contestants advancing to the next round will be decided as follows:
The organizer will choose two consecutive digits in the decimal notation of
X
, and replace them with the sum of these digits. The number resulted will be the number of contestants advancing to the next round.
For example, when
X = 2378
, the number of contestants advancing to the next round will be
578
(if
2
and
3
are chosen),
2108
(if
3
and
7
are chosen), or
2315
(if
7
and
8
are chosen).
When
X = 100
, the number of contestants advancing to the next round will be
10
, no matter which two digits are chosen.
The preliminary stage ends when
9
or fewer contestants remain.
Ringo, the chief organizer, wants to hold as many rounds as possible.
Find the maximum possible number of rounds in the preliminary stage.
Since the number of contestants,
N
, can be enormous, it is given to you as two integer sequences
d_1, \ldots, d_M
and
c_1, \ldots, c_M
, which means the following: the decimal notation of
N
consists of
c_1 + c_2 + \ldots + c_M
digits, whose first
c_1
digits are all
d_1
, the following
c_2
digits are all
d_2
,
\ldots
, and the last
c_M
digits are all
d_M
.
Constraints
1 \leq M \leq 200000
0 \leq d_i \leq 9
d_1 \neq 0
d_i \neq d_{i+1}
c_i \geq 1
2 \leq c_1 + \ldots + c_M \leq 10^{15}
Input
Input is given from Standard Input in the following format:
M
d_1
c_1
d_2
c_2
:
d_M
c_M
Output
Print the maximum possible number of rounds in the preliminary stage.
Sample Input 1
2
2 2
9 1
Sample Output 1
3
In this case,
N = 229
contestants will participate in the first round. One possible progression of the preliminary stage is as follows:
229
contestants participate in Round
1
,
49
contestants participate in Round
2
,
13
contestants participate in Round
3
, and
4
contestants advance to the finals.
Here, three rounds take place in the preliminary stage, which is the maximum possible number.
Sample Input 2
3
1 1
0 8
7 1
Sample Output 2
9
In this case,
1000000007
will participate in the first round.
Problem Description: Score : 100 points
Problem Statement
Given is an integer
r
.
How many times is the area of a circle of radius
r
larger than the area of a circle of radius
1
?
It can be proved that the answer is always an integer under the constraints given.
Constraints
1 \leq r \leq 100
All values in input are integers.
Input
Input is given from Standard Input in the following format:
r
Output
Print the area of a circle of radius
r
, divided by the area of a circle of radius
1
, as an integer.
Sample Input 1
2
Sample Output 1
4
The area of a circle of radius
2
is
4
times larger than the area of a circle of radius
1
.
Note that output must be an integer - for example,
4.0
will not be accepted.
Sample Input 2
100
Sample Output 2
10000
Problem Description: Score : 200 points
Problem Statement
Given are a positive integer
N
and a string
S
of length
N
consisting of lowercase English letters.
Determine whether the string is a concatenation of two copies of some string.
That is, determine whether there is a string
T
such that
S = T + T
.
Constraints
1 \leq N \leq 100
S
consists of lowercase English letters.
|S| = N
Input
Input is given from Standard Input in the following format:
N
S
Output
If
S
is a concatenation of two copies of some string, print
Yes
; otherwise, print
No
.
Sample Input 1
6
abcabc
Sample Output 1
Yes
Let
T =
abc
, and
S = T + T
.
Sample Input 2
6
abcadc
Sample Output 2
No
Sample Input 3
1
z
Sample Output 3
No
Problem Description: Score : 400 points
Problem Statement
There is a knight - the chess piece - at the origin
(0, 0)
of a two-dimensional grid.
When the knight is at the square
(i, j)
, it can be moved to either
(i+1,j+2)
or
(i+2, j+1)
.
In how many ways can the knight reach the square
(X, Y)
?
Find the number of ways modulo
10^9 + 7
.
Constraints
1 \leq X \leq 10^6
1 \leq Y \leq 10^6
All values in input are integers.
Input
Input is given from Standard Input in the following format:
X
Y
Output
Print the number of ways for the knight to reach
(X, Y)
from
(0, 0)
, modulo
10^9 + 7
.
Sample Input 1
3 3
Sample Output 1
2
There are two ways:
(0,0) \to (1,2) \to (3,3)
and
(0,0) \to (2,1) \to (3,3)
.
Sample Input 2
2 2
Sample Output 2
0
The knight cannot reach
(2,2)
.
Sample Input 3
999999 999999
Sample Output 3
151840682
Print the number of ways modulo
10^9 + 7
.
Problem Description: Score : 500 points
Problem Statement
Takahashi is at an all-you-can-eat restaurant.
The restaurant offers
N
kinds of dishes. It takes
A_i
minutes to eat the
i
-th dish, whose deliciousness is
B_i
.
The restaurant has the following rules:
You can only order one dish at a time. The dish ordered will be immediately served and ready to eat.
You cannot order the same kind of dish more than once.
Until you finish eating the dish already served, you cannot order a new dish.
After
T-0.5
minutes from the first order, you can no longer place a new order, but you can continue eating the dish already served.
Let Takahashi's happiness be the sum of the deliciousness of the dishes he eats in this restaurant.
What is the maximum possible happiness achieved by making optimal choices?
Constraints
2 \leq N \leq 3000
1 \leq T \leq 3000
1 \leq A_i \leq 3000
1 \leq B_i \leq 3000
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
T
A_1
B_1
:
A_N
B_N
Output
Print the maximum possible happiness Takahashi can achieve.
Sample Input 1
2 60
10 10
100 100
Sample Output 1
110
By ordering the first and second dishes in this order, Takahashi's happiness will be
110
.
Note that, if we manage to order a dish in time, we can spend any amount of time to eat it.
Sample Input 2
3 60
10 10
10 20
10 30
Sample Output 2
60
Takahashi can eat all the dishes within
60
minutes.
Sample Input 3
3 60
30 10
30 20
30 30
Sample Output 3
50
By ordering the second and third dishes in this order, Takahashi's happiness will be
50
.
We cannot order three dishes, in whatever order we place them.
Sample Input 4
10 100
15 23
20 18
13 17
24 12
18 29
19 27
23 21
18 20
27 15
22 25
Sample Output 4
145
Problem Description: Score : 600 points
Problem Statement
We will create an artwork by painting black some squares in a white square grid with
10^9
rows and
N
columns.
The current plan is as follows: for the
i
-th column from the left, we will paint the
H_i
bottommost squares and will not paint the other squares in that column.
Before starting to work, you can choose at most
K
columns (possibly zero) and change the values of
H_i
for these columns to any integers of your choice between
0
and
10^9
(inclusive).
Different values can be chosen for different columns.
Then, you will create the modified artwork by repeating the following operation:
Choose one or more consecutive squares in one row and paint them black. (Squares already painted black can be painted again, but squares not to be painted according to the modified plan should not be painted.)
Find the minimum number of times you need to perform this operation.
Constraints
1 \leq N \leq 300
0 \leq K \leq N
0 \leq H_i \leq 10^9
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
K
H_1
H_2
...
H_N
Output
Print the minimum number of operations required.
Sample Input 1
4 1
2 3 4 1
Sample Output 1
3
For example, by changing the value of
H_3
to
2
, you can create the modified artwork by the following three operations:
Paint black the
1
-st through
4
-th squares from the left in the
1
-st row from the bottom.
Paint black the
1
-st through
3
-rd squares from the left in the
2
-nd row from the bottom.
Paint black the
2
-nd square from the left in the
3
-rd row from the bottom.
Sample Input 2
6 2
8 6 9 1 2 1
Sample Output 2
7
Sample Input 3
10 0
1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000
Sample Output 3
4999999996
Problem Description: Score : 100 points
Problem Statement
How many ways are there to choose two distinct positive integers totaling
N
, disregarding the order?
Constraints
1 \leq N \leq 10^6
N
is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
4
Sample Output 1
1
There is only one way to choose two distinct integers totaling
4
: to choose
1
and
3
. (Choosing
3
and
1
is not considered different from this.)
Sample Input 2
999999
Sample Output 2
499999
Problem Description: Score : 300 points
Problem Statement
Given is an integer sequence
D_1,...,D_N
of
N
elements. Find the number, modulo
998244353
, of trees with
N
vertices numbered
1
to
N
that satisfy the following condition:
For every integer
i
from
1
to
N
, the distance between Vertex
1
and Vertex
i
is
D_i
.
Notes
A tree of
N
vertices is a connected undirected graph with
N
vertices and
N-1
edges, and the distance between two vertices are the number of edges in the shortest path between them.
Two trees are considered different if and only if there are two vertices
x
and
y
such that there is an edge between
x
and
y
in one of those trees and not in the other.
Constraints
1 \leq N \leq 10^5
0 \leq D_i \leq N-1
Input
Input is given from Standard Input in the following format:
N
D_1
D_2
...
D_N
Output
Print the answer.
Sample Input 1
4
0 1 1 2
Sample Output 1
2
For example, a tree with edges
(1,2)
,
(1,3)
, and
(2,4)
satisfies the condition.
Sample Input 2
4
1 1 1 1
Sample Output 2
0
Sample Input 3
7
0 3 2 1 2 2 1
Sample Output 3
24
Problem Description: Score : 300 points
Problem Statement
Given is a string
S
of length
N-1
.
Each character in
S
is
<
or
>
.
A sequence of
N
non-negative integers,
a_1,a_2,\cdots,a_N
, is said to be
good
when the following condition is satisfied for all
i
(
1 \leq i \leq N-1
):
If
S_i=
<
:
a_i<a_{i+1}
If
S_i=
>
:
a_i>a_{i+1}
Find the minimum possible sum of the elements of a good sequence of
N
non-negative integers.
Constraints
2 \leq N \leq 5 \times 10^5
S
is a string of length
N-1
consisting of
<
and
>
.
Input
Input is given from Standard Input in the following format:
S
Output
Find the minimum possible sum of the elements of a good sequence of
N
non-negative integers.
Sample Input 1
<>>
Sample Output 1
3
a=(0,2,1,0)
is a good sequence whose sum is
3
.
There is no good sequence whose sum is less than
3
.
Sample Input 2
<>>><<><<<<<>>><
Sample Output 2
28
Problem Description: Score : 2200 points
Problem Statement
We have two indistinguishable pieces placed on a number line.
Both pieces are initially at coordinate
0
. (They can occupy the same position.)
We can do the following two kinds of operations:
Choose a piece and move it to the right (the positive direction) by
1
.
Move the piece with the smaller coordinate to the position of the piece with the greater coordinate.
If two pieces already occupy the same position, nothing happens, but it still counts as doing one operation.
We want to do a total of
N
operations of these kinds in some order so that one of the pieces will be at coordinate
A
and the other at coordinate
B
.
Find the number of ways to move the pieces to achieve it.
The answer can be enormous, so compute the count modulo
998244353
.
Two ways to move the pieces are considered different if and only if there exists an integer
i
(
1 \leq i \leq N
) such that the set of the coordinates occupied by the pieces after the
i
-th operation is different in those two ways.
Constraints
1 \leq N \leq 10^7
0 \leq A \leq B \leq N
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A
B
Output
Print the number of ways to move the pieces to achieve our objective, modulo
998244353
.
Sample Input 1
5 1 3
Sample Output 1
4
Shown below are the four ways to move the pieces, where
(x,y)
represents the state where the two pieces are at coordinates
x
and
y
.
(0,0)→(0,0)→(0,1)→(0,2)→(0,3)→(1,3)
(0,0)→(0,0)→(0,1)→(0,2)→(1,2)→(1,3)
(0,0)→(0,0)→(0,1)→(1,1)→(1,2)→(1,3)
(0,0)→(0,1)→(1,1)→(1,1)→(1,2)→(1,3)
Sample Input 2
10 0 0
Sample Output 2
1
Sample Input 3
10 4 6
Sample Output 3
197
Sample Input 4
1000000 100000 200000
Sample Output 4
758840509
Problem Description: Score : 200 points
Problem Statement
Having learned the multiplication table, Takahashi can multiply two integers between
1
and
9
(inclusive) together.
Given an integer
N
, determine whether
N
can be represented as the product of two integers between
1
and
9
. If it can, print
Yes
; if it cannot, print
No
.
Constraints
1 \leq N \leq 100
N
is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
If
N
can be represented as the product of two integers between
1
and
9
(inclusive), print
Yes
; if it cannot, print
No
.
Sample Input 1
10
Sample Output 1
Yes
10
can be represented as, for example,
2 \times 5
.
Sample Input 2
50
Sample Output 2
No
50
cannot be represented as the product of two integers between
1
and
9
.
Sample Input 3
81
Sample Output 3
Yes
Problem Description: Score : 300 points
Problem Statement
Takahashi is standing on a multiplication table with infinitely many rows and columns.
The square
(i,j)
contains the integer
i \times j
. Initially, Takahashi is standing at
(1,1)
.
In one move, he can move from
(i,j)
to either
(i+1,j)
or
(i,j+1)
.
Given an integer
N
, find the minimum number of moves needed to reach a square that contains
N
.
Constraints
2 \leq N \leq 10^{12}
N
is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the minimum number of moves needed to reach a square that contains the integer
N
.
Sample Input 1
10
Sample Output 1
5
(2,5)
can be reached in five moves. We cannot reach a square that contains
10
in less than five moves.
Sample Input 2
50
Sample Output 2
13
(5, 10)
can be reached in
13
moves.
Sample Input 3
10000000019
Sample Output 3
10000000018
Both input and output may be enormous.
Problem Description: Score: 500 points
Problem Statement
Takahashi will take part in an eating contest. Teams of
N
members will compete in this contest, and Takahashi's team consists of
N
players numbered
1
through
N
from youngest to oldest. The
consumption coefficient
of Member
i
is
A_i
.
In the contest,
N
foods numbered
1
through
N
will be presented, and the
difficulty
of Food
i
is
F_i
. The details of the contest are as follows:
A team should assign one member to each food, and should not assign the same member to multiple foods.
It will take
x \times y
seconds for a member to finish the food, where
x
is the consumption coefficient of the member and
y
is the difficulty of the dish.
The score of a team is the longest time it takes for an individual member to finish the food.
Before the contest, Takahashi's team decided to do some training. In one set of training, a member can reduce his/her consumption coefficient by
1
, as long as it does not go below
0
. However, for financial reasons, the
N
members can do at most
K
sets of training in total.
What is the minimum possible score of the team, achieved by choosing the amounts of members' training and allocating the dishes optimally?
Constraints
All values in input are integers.
1 \leq N \leq 2 \times 10^5
0 \leq K \leq 10^{18}
1 \leq A_i \leq 10^6\ (1 \leq i \leq N)
1 \leq F_i \leq 10^6\ (1 \leq i \leq N)
Input
Input is given from Standard Input in the following format:
N
K
A_1
A_2
...
A_N
F_1
F_2
...
F_N
Output
Print the minimum possible score of the team.
Sample Input 1
3 5
4 2 1
2 3 1
Sample Output 1
2
They can achieve the score of
2
, as follows:
Member
1
does
4
sets of training and eats Food
2
in
(4-4) \times 3 = 0
seconds.
Member
2
does
1
set of training and eats Food
3
in
(2-1) \times 1 = 1
second.
Member
3
does
0
sets of training and eats Food
1
in
(1-0) \times 2 = 2
seconds.
They cannot achieve a score of less than
2
, so the answer is
2
.
Sample Input 2
3 8
4 2 1
2 3 1
Sample Output 2
0
They can choose not to do exactly
K
sets of training.
Sample Input 3
11 14
3 1 4 1 5 9 2 6 5 3 5
8 9 7 9 3 2 3 8 4 6 2
Sample Output 3
12
Problem Description: Score : 100 points
Problem Statement
The window of Takahashi's room has a width of
A
. There are two curtains hung over the window, each of which has a horizontal length of
B
. (Vertically, the curtains are long enough to cover the whole window.)
We will close the window so as to minimize the total horizontal length of the uncovered part of the window.
Find the total horizontal length of the uncovered parts of the window then.
Constraints
1 \leq A \leq 100
1 \leq B \leq 100
A
and
B
are integers.
Input
Input is given from Standard Input in the following format:
A
B
Output
Print the total horizontal length of the uncovered parts of the window.
Sample Input 1
12 4
Sample Output 1
4
We have a window with a horizontal length of
12
, and two curtains, each of length
4
, that cover both ends of the window, for example. The uncovered part has a horizontal length of
4
.
Sample Input 2
20 15
Sample Output 2
0
If the window is completely covered, print
0
.
Sample Input 3
20 30
Sample Output 3
0
Each curtain may be longer than the window.
Problem Description: Score : 200 points
Problem Statement
It's now the season of TAKOYAKI FESTIVAL!
This year,
N
takoyaki (a ball-shaped food with a piece of octopus inside) will be served. The
deliciousness
of the
i
-th takoyaki is
d_i
.
As is commonly known, when you eat two takoyaki of deliciousness
x
and
y
together, you restore
x \times y
health points.
There are
\frac{N \times (N - 1)}{2}
ways to choose two from the
N
takoyaki served in the festival. For each of these choices, find the health points restored from eating the two takoyaki, then compute the sum of these
\frac{N \times (N - 1)}{2}
values.
Constraints
All values in input are integers.
2 \leq N \leq 50
0 \leq d_i \leq 100
Input
Input is given from Standard Input in the following format:
N
d_1
d_2
...
d_N
Output
Print the sum of the health points restored from eating two takoyaki over all possible choices of two takoyaki from the
N
takoyaki served.
Sample Input 1
3
3 1 2
Sample Output 1
11
There are three possible choices:
Eat the first and second takoyaki. You will restore
3
health points.
Eat the second and third takoyaki. You will restore
2
health points.
Eat the first and third takoyaki. You will restore
6
health points.
The sum of these values is
11
.
Sample Input 2
7
5 0 7 8 3 3 2
Sample Output 2
312
Problem Description: Score : 300 points
Problem Statement
There are
N
slimes lining up from left to right. The colors of these slimes will be given as a string
S
of length
N
consisting of lowercase English letters. The
i
-th slime from the left has the color that corresponds to the
i
-th character of
S
.
Adjacent slimes with the same color will fuse into one larger slime without changing the color. If there were a slime adjacent to this group of slimes before fusion, that slime is now adjacent to the new larger slime.
Ultimately, how many slimes will be there?
Constraints
1 \leq N \leq 10^5
|S| = N
S
consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
N
S
Output
Print the final number of slimes.
Sample Input 1
10
aabbbbaaca
Sample Output 1
5
Ultimately, these slimes will fuse into
abaca
.
Sample Input 2
5
aaaaa
Sample Output 2
1
All the slimes will fuse into one.
Sample Input 3
20
xxzaffeeeeddfkkkkllq
Sample Output 3
10
Problem Description: Score : 400 points
Problem Statement
Takahashi has
N
sticks that are distinguishable from each other. The length of the
i
-th stick is
L_i
.
He is going to form a triangle using three of these sticks. Let
a
,
b
, and
c
be the lengths of the three sticks used. Here, all of the following conditions must be satisfied:
a < b + c
b < c + a
c < a + b
How many different triangles can be formed? Two triangles are considered different when there is a stick used in only one of them.
Constraints
All values in input are integers.
3 \leq N \leq 2 \times 10^3
1 \leq L_i \leq 10^3
Input
Input is given from Standard Input in the following format:
N
L_1
L_2
...
L_N
Constraints
Print the number of different triangles that can be formed.
Sample Input 1
4
3 4 2 1
Sample Output 1
1
Only one triangle can be formed: the triangle formed by the first, second, and third sticks.
Sample Input 2
3
1 1000 1
Sample Output 2
0
No triangles can be formed.
Sample Input 3
7
218 786 704 233 645 728 389
Sample Output 3
23