CodeEff/ECCO huggingface dataset:
Max Score: $250$ Points
Problem Statement
Snuke has a very long calendar. It has a grid with $n$ rows and $7$ columns. One day, he noticed that calendar has a following regularity.
The cell at the $i$-th row and $j$-th column contains the integer $7i+j-7$.
A good sub-grid is a $3 \times 3$ sub-grid and the sum of integers in this sub-grid mod $11$ is $k$.
How many good sub-grid are there? Write a program and help him.
Input
The input is given from standard input in the following format.
$n \quad k$
Output
Print the number of good sub-grid. If there are no solution exists, print
0
.
Constraints
$1 \le n \le 10^9$
$0 \le k \le 10$
Subtasks
Problem Description: Subtask 1 [ $150$ points ]
The testcase in the subtask satisfies $1 \le n \le 100$.
Subtask 2 [ $100$ points ]
There are no additional constraints.
Sample Input 1
7 7
Sample Output 1
2
In this case, the calendar likes this matrix.
Sun.
Mon.
Tue.
Wed.
Thu.
Fri.
Sat.
Week 1
1
2
3
4
5
6
7
Week 2
8
9
10
11
12
13
14
Week 3
15
16
17
18
19
20
21
Week 4
22
23
24
25
26
27
28
Week 5
29
30
31
32
33
34
35
Week 6
36
37
38
39
40
41
42
Week 7
43
44
45
46
47
48
49
The cell at $i$-th row and $j$-th column is denoted $(i, j)$.
If upper-left is $(1, 5)$, the sum of integers is $5+6+7+12+13+14+19+20+21=117$.
If upper-left is $(3, 2)$, the sum of integers is $16+17+18+23+24+25+30+31+32=216$.
Therefore, there are 2 good sub-grids.
Sample Input 2
6 0
Sample Output 2
2
If upper-left is $(1, 3)$ or $(4, 4)$, it is a good sub-grid.
Sample Input 3
18 10
Max Score: $400$ Points
Problem Statement
Sample testcase 3 has a mistake, so we erased this case and rejudged all solutions of this problem. (21:01)
Snuke got a sequence $a$ of length $n$ from AtCoder company. All elements in $a$ are distinct.
He made a sequence $b$, but actually, he is not remembered it.
However, he is remembered a few things about sequence $b$.
All elements in $b$ are distinct.
All elements in $b$ is in $a$.
$b_1 \oplus b_2 \oplus \cdots \oplus b_r = k$. ($r$ is length of sequence $b$) [$\oplus$ means XOR]
For example, if $a = { 1, 2, 3 }$ and $k = 1$, he can make $b = { 1 }, { 2, 3 }, { 3, 2 }$.
He wants to restore sequence $b$, but he says that there are too many ways and he can't restore it.
						Please calculate the ways to make $b$ and help him.
Since the answer can be large, print the answer modulo $1,000,000,007$.
Input
The input is given from Standard Input in the following format:
$n \ k$
$a_1 \ a_2 \ \cdots \ a_n$
Output
Print the number of ways to make sequence $b$.
Print the answer modulo $1,000,000,007$.
Constraints
$1 \le n \le 100$
$1 \le a_i, k \le 255$
$i \neq j \Rightarrow a_i \neq a_j$
Subtasks
Subtask 1 [ $50$ points ]
$1 \le n \le 4$
Subtask 2 [ $170$ points ]
$1 \le n \le 20$
Subtask 3 [ $180$ points ]
There are no additional constraints.
Sample Input 1
3 1
1 2 3
Sample Output 1
3
You can make 3 patterns: $b = \{ 1 \}, \{ 2, 3 \}, \{ 3, 2 \}$
Sample Input 2
3 10
8 7 5
Sample Output 2
6
You can make 6 patterns: $b = \{ 5, 7, 8 \}, \{ 5, 8, 7 \}, \{ 7, 5, 8 \}, \{ 7, 8, 5 \}, \{ 8, 5, 7 \}, \{ 8, 7, 5 \}$.
Sample Input 4
25 127
5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125
Sample Output 4
235924722
Problem Description: Please output answer mod $1,000,000,007$.
writer: E869120
Problem Description: Score : 100 points
Problem Statement
Two students of AtCoder Kindergarten are fighting over candy packs.
There are three candy packs, each of which contains
a
,
b
, and
c
candies, respectively.
Teacher Evi is trying to distribute the packs between the two students so that each student gets the same number of candies. Determine whether it is possible.
Note that Evi cannot take candies out of the packs, and the whole contents of each pack must be given to one of the students.
Constraints
1 ≦ a, b, c ≦ 100
Input
The input is given from Standard Input in the following format:
a
b
c
Output
If it is possible to distribute the packs so that each student gets the same number of candies, print
Yes
. Otherwise, print
No
.
Sample Input 1
10 30 20
Sample Output 1
Yes
Give the pack with
30
candies to one student, and give the two packs with
10
and
20
candies to the other. Then, each gets
30
candies.
Sample Input 2
30 30 100
Sample Output 2
No
In this case, the student who gets the pack with
100
candies always has more candies than the other.
Note that every pack must be given to one of them.
Sample Input 3
56 25 31
Sample Output 3
Yes
Problem Description: Score : 300 points
Problem Statement
Two foxes Jiro and Saburo are playing a game called
1D Reversi
. This game is played on a board, using black and white stones. On the board, stones are placed in a row, and each player places a new stone to either end of the row. Similarly to the original game of Reversi, when a white stone is placed, all black stones between the new white stone and another white stone, turn into white stones, and vice versa.
In the middle of a game, something came up and Saburo has to leave the game. The state of the board at this point is described by a string
S
. There are |S| (the length of
S
) stones on the board, and each character in
S
represents the color of the
i
-th (
1 ≦ i ≦ |S|
) stone from the left. If the
i
-th character in
S
is
B
, it means that the color of the corresponding stone on the board is black. Similarly, if the
i
-th character in
S
is
W
, it means that the color of the corresponding stone is white.
Jiro wants all stones on the board to be of the same color. For this purpose, he will place new stones on the board according to the rules. Find the minimum number of new stones that he needs to place.
Constraints
1 ≦ |S| ≦ 10^5
Each character in
S
is
B
or
W
.
Input
The input is given from Standard Input in the following format:
S
Output
Print the minimum number of new stones that Jiro needs to place for his purpose.
Sample Input 1
BBBWW
Sample Output 1
1
By placing a new black stone to the right end of the row of stones, all white stones will become black. Also, by placing a new white stone to the left end of the row of stones, all black stones will become white.
In either way, Jiro's purpose can be achieved by placing one stone.
Sample Input 2
WWWWWW
Sample Output 2
0
If all stones are already of the same color, no new stone is necessary.
Sample Input 3
WBWBWBWBWB
Sample Output 3
9
Problem Description: Score : 400 points
Problem Statement
There are
N
towns located in a line, conveniently numbered
1
through
N
. Takahashi the merchant is going on a travel from town
1
to town
N
, buying and selling apples.
Takahashi will begin the travel at town
1
, with no apple in his possession. The actions that can be performed during the travel are as follows:
Move
: When at town
i
(
i < N
), move to town
i + 1
.
Merchandise
: Buy or sell an arbitrary number of apples at the current town. Here, it is assumed that one apple can always be bought and sold for
A_i
yen (the currency of Japan) at town
i
(
1 ≦ i ≦ N
), where
A_i
are distinct integers. Also, you can assume that he has an infinite supply of money.
For some reason, there is a constraint on merchandising apple during the travel: the sum of the number of apples bought and the number of apples sold during the whole travel, must be at most
T
. (Note that a single apple can be counted in both.)
During the travel, Takahashi will perform actions so that the
profit
of the travel is maximized. Here, the profit of the travel is the amount of money that is gained by selling apples, minus the amount of money that is spent on buying apples. Note that we are not interested in apples in his possession at the end of the travel.
Aoki, a business rival of Takahashi, wants to trouble Takahashi by manipulating the market price of apples. Prior to the beginning of Takahashi's travel, Aoki can change
A_i
into another arbitrary non-negative integer
A_i'
for any town
i
, any number of times. The cost of performing this operation is
|A_i - A_i'|
. After performing this operation, different towns may have equal values of
A_i
.
Aoki's objective is to decrease Takahashi's expected profit by at least
1
yen. Find the minimum total cost to achieve it. You may assume that Takahashi's expected profit is initially at least
1
yen.
Constraints
1 ≦ N ≦ 10^5
1 ≦ A_i ≦ 10^9
(
1 ≦ i ≦ N
)
A_i
are distinct.
2 ≦ T ≦ 10^9
In the initial state, Takahashi's expected profit is at least
1
yen.
Input
The input is given from Standard Input in the following format:
N
T
A_1
A_2
...
A_N
Output
Print the minimum total cost to decrease Takahashi's expected profit by at least
1
yen.
Sample Input 1
3 2
100 50 200
Sample Output 1
1
In the initial state, Takahashi can achieve the maximum profit of
150
yen as follows:
Move from town
1
to town
2
.
Buy one apple for
50
yen at town
2
.
Move from town
2
to town
3
.
Sell one apple for
200
yen at town
3
.
If, for example, Aoki changes the price of an apple at town
2
from
50
yen to
51
yen, Takahashi will not be able to achieve the profit of
150
yen. The cost of performing this operation is
1
, thus the answer is
1
.
There are other ways to decrease Takahashi's expected profit, such as changing the price of an apple at town
3
from
200
yen to
199
yen.
Sample Input 2
5 8
50 30 40 10 20
Sample Output 2
2
Sample Input 3
10 100
7 10 4 5 9 3 6 8 2 1
Sample Output 3
2
Problem Description: Score : 800 points
Problem Statement
We have a tree with
N
vertices. The vertices are numbered
1, 2, ..., N
. The
i
-th (
1 ≦ i ≦ N - 1
) edge connects the two vertices
A_i
and
B_i
.
Takahashi wrote integers into
K
of the vertices. Specifically, for each
1 ≦ j ≦ K
, he wrote the integer
P_j
into vertex
V_j
. The remaining vertices are left empty. After that, he got tired and fell asleep.
Then, Aoki appeared. He is trying to surprise Takahashi by writing integers into all empty vertices so that the following condition is satisfied:
Condition: For any two vertices directly connected by an edge, the integers written into these vertices differ by exactly
1
.
Determine if it is possible to write integers into all empty vertices so that the condition is satisfied. If the answer is positive, find one specific way to satisfy the condition.
Constraints
1 ≦ N ≦ 10^5
1 ≦ K ≦ N
1 ≦ A_i, B_i ≦ N
(
1 ≦ i ≦ N - 1
)
1 ≦ V_j ≦ N
(
1 ≦ j ≦ K
) (21:18, a mistake in this constraint was corrected)
0 ≦ P_j ≦ 10^5
(
1 ≦ j ≦ K
)
The given graph is a tree.
All
v_j
are distinct.
Input
The input is given from Standard Input in the following format:
N
A_1
B_1
A_2
B_2
:
A_{N-1}
B_{N-1}
K
V_1
P_1
V_2
P_2
:
V_K
P_K
Output
If it is possible to write integers into all empty vertices so that the condition is satisfied, print
Yes
. Otherwise, print
No
.
If it is possible to satisfy the condition, print
N
lines in addition. The
v
-th (
1 ≦ v ≦ N
) of these
N
lines should contain the integer that should be written into vertex
v
. If there are multiple ways to satisfy the condition, any of those is accepted.
Sample Input 1
5
1 2
3 1
4 3
3 5
2
2 6
5 7
Sample Output 1
Yes
5
6
6
5
7
The figure below shows the tree when Takahashi fell asleep. For each vertex, the integer written beside it represents the index of the vertex, and the integer written into the vertex is the integer written by Takahashi.
Aoki can, for example, satisfy the condition by writing integers into the remaining vertices as follows:
This corresponds to Sample Output 1. Note that other outputs that satisfy the condition will also be accepted, such as:
Yes
7
6
8
7
7
Sample Input 2
5
1 2
3 1
4 3
3 5
3
2 6
4 3
5 7
Sample Output 2
No
Sample Input 3
4
1 2
2 3
3 4
1
1 0
Sample Output 3
Yes
0
-1
-2
-3
The integers written by Aoki may be negative or exceed
10^6
.
Problem Description: Score : 100 points
Problem Statement
This contest is
CODEFESTIVAL
, which can be shortened to the string
CF
by deleting some characters.
Mr. Takahashi, full of curiosity, wondered if he could obtain
CF
from other strings in the same way.
You are given a string
s
consisting of uppercase English letters.
Determine whether the string
CF
can be obtained from the string
s
by deleting some characters.
Constraints
2 ≤ |s| ≤ 100
All characters in
s
are uppercase English letters (
A
-
Z
).
Input
The input is given from Standard Input in the following format:
s
Output
Print
Yes
if the string
CF
can be obtained from the string
s
by deleting some characters.
Otherwise print
No
.
Sample Input 1
CODEFESTIVAL
Sample Output 1
Yes
CF
is obtained by deleting characters other than the first character
C
and the fifth character
F
.
Sample Input 2
FESTIVALCODE
Sample Output 2
No
FC
can be obtained but
CF
cannot be obtained because you cannot change the order of the characters.
Sample Input 3
CF
Sample Output 3
Yes
It is also possible not to delete any characters.
Sample Input 4
FCF
Sample Output 4
Yes
CF
is obtained by deleting the first character.
Problem Description: Score : 400 points
Problem Statement
Mountaineers Mr. Takahashi and Mr. Aoki recently trekked across a certain famous mountain range.
The mountain range consists of
N
mountains, extending from west to east in a straight line as Mt.
1
, Mt.
2
, ..., Mt.
N
.
Mr. Takahashi traversed the range from the west and Mr. Aoki from the east.
The height of Mt.
i
is
h_i
, but they have forgotten the value of each
h_i
.
Instead, for each
i
(
1 ≤ i ≤ N
), they recorded the maximum height of the mountains climbed up to the time they reached the peak of Mt.
i
(including Mt.
i
).
Mr. Takahashi's record is
T_i
and Mr. Aoki's record is
A_i
.
We know that the height of each mountain
h_i
is a positive integer.
Compute the number of the possible sequences of the mountains' heights, modulo
10^9 + 7
.
Note that the records may be incorrect and thus there may be no possible sequence of the mountains' heights.
In such a case, output
0
.
Constraints
1 ≤ N ≤ 10^5
1 ≤ T_i ≤ 10^9
1 ≤ A_i ≤ 10^9
T_i ≤ T_{i+1}
(
1 ≤ i ≤ N - 1
)
A_i ≥ A_{i+1}
(
1 ≤ i ≤ N - 1
)
Input
The input is given from Standard Input in the following format:
N
T_1
T_2
...
T_N
A_1
A_2
...
A_N
Output
Print the number of possible sequences of the mountains' heights, modulo
10^9 + 7
.
Sample Input 1
5
1 3 3 3 3
3 3 2 2 2
Sample Output 1
4
The possible sequences of the mountains' heights are:
1, 3, 2, 2, 2
1, 3, 2, 1, 2
1, 3, 1, 2, 2
1, 3, 1, 1, 2
for a total of four sequences.
Sample Input 2
5
1 1 1 2 2
3 2 1 1 1
Sample Output 2
0
The records are contradictory, since Mr. Takahashi recorded
2
as the highest peak after climbing all the mountains but Mr. Aoki recorded
3
.
Sample Input 3
10
1 3776 3776 8848 8848 8848 8848 8848 8848 8848
8848 8848 8848 8848 8848 8848 8848 8848 3776 5
Sample Output 3
884111967
Don't forget to compute the number modulo
10^9 + 7
.
Sample Input 4
1
17
17
Sample Output 4
1
Some mountain ranges consist of only one mountain.
Problem Description: Score : 800 points
Problem Statement
Mr. Takahashi has in his room an art object with
H
rows and
W
columns, made up of
H \times W
blocks.
Each block has a color represented by a lowercase English letter (
a
-
z
).
The color of the block at the
i
-th row and
j
-th column is
c_{i,j}
.
Mr. Takahashi would like to dismantle the object, finding it a bit kitschy for his tastes.
The dismantling is processed by repeating the following operation:
Choose one of the
W
columns and push down that column one row.
The block at the bottom of that column disappears.
Each time the operation is performed, a cost is incurred.
Since blocks of the same color have a property to draw each other together, the cost of the operation is the number of the pairs of blocks
(p, q)
such that:
The block
p
is in the selected column.
The two blocks
p
and
q
are horizontally adjacent (before pushing down the column).
The two blocks
p
and
q
have the same color.
Mr. Takahashi dismantles the object by repeating the operation
H \times W
times to get rid of all the blocks.
Compute the minimum total cost to dismantle the object.
Constraints
1 ≤ H ≤ 300
2 ≤ W ≤ 300
All characters
c_{i,j}
are lowercase English letters (
a
-
z
).
Partial Score
In test cases worth
300
points,
W = 3
.
Input
The input is given from Standard Input in the following format:
H
W
c_{1,1}c_{1,2}
..
c_{1,W}
c_{2,1}c_{2,2}
..
c_{2,W}
:
c_{H,1}c_{H,2}
..
c_{H,W}
Output
Print the minimum total cost to dismantle the object.
Sample Input 1
2 3
rrr
brg
Sample Output 1
2
For example, the total cost of
2
can be achieved by performing the operation as follows and this is the minimum value.
Sample Input 2
6 3
xya
xya
ayz
ayz
xaz
xaz
Sample Output 2
0
The total cost of
0
can be achieved by first pushing down all blocks of the middle column, then all of the left column, and all of the right column.
Sample Input 3
4 2
ay
xa
xy
ay
Sample Output 3
0
The total cost of
0
can be achieved by the following operations:
pushing down the right column one row;
pushing down the left column one row;
pushing down all of the right column;
and pushing down all of the left column.
Sample Input 4
5 5
aaaaa
abbba
ababa
abbba
aaaaa
Sample Output 4
24
Sample Input 5
7 10
xxxxxxxxxx
ccccxxffff
cxxcxxfxxx
cxxxxxffff
cxxcxxfxxx
ccccxxfxxx
xxxxxxxxxx
Sample Output 5
130
Problem Description: Score : 100 points
Problem Statement
AtCoDeer the deer recently bought three paint cans.
The color of the one he bought two days ago is
a
, the color of the one he bought yesterday is
b
, and the color of the one he bought today is
c
.
Here, the color of each paint can is represented by an integer between
1
and
100
, inclusive.
Since he is forgetful, he might have bought more than one paint can in the same color.
Count the number of different kinds of colors of these paint cans and tell him.
Constraints
1≦a,b,c≦100
Input
The input is given from Standard Input in the following format:
a
b
c
Output
Print the number of different kinds of colors of the paint cans.
Sample Input 1
3 1 4
Sample Output 1
3
Three different colors:
1
,
3
, and
4
.
Sample Input 2
3 3 33
Sample Output 2
2
Two different colors:
3
and
33
.
Problem Description: Score : 200 points
Problem Statement
There are
N
balls placed in a row.
AtCoDeer the deer is painting each of these in one of the
K
colors of his paint cans.
For aesthetic reasons, any two adjacent balls must be painted in different colors.
Find the number of the possible ways to paint the balls.
Constraints
1≦N≦1000
2≦K≦1000
The correct answer is at most
2^{31}-1
.
Input
The input is given from Standard Input in the following format:
N
K
Output
Print the number of the possible ways to paint the balls.
Sample Input 1
2 2
Sample Output 1
2
We will denote the colors by
0
and
1
. There are two possible ways: we can either paint the left ball in color
0
and the right ball in color
1
, or paint the left in color
1
and the right in color
0
.
Sample Input 2
1 10
Sample Output 2
10
Since there is only one ball, we can use any of the ten colors to paint it. Thus, the answer is ten.
Problem Description: Score : 300 points
Problem Statement
AtCoDeer the deer is seeing a quick report of election results on TV.
Two candidates are standing for the election: Takahashi and Aoki.
The report shows the ratio of the current numbers of votes the two candidates have obtained, but not the actual numbers of votes.
AtCoDeer has checked the report
N
times, and when he checked it for the
i
-th
(1≦i≦N)
time, the ratio was
T_i:A_i
.
It is known that each candidate had at least one vote when he checked the report for the first time.
Find the minimum possible total number of votes obtained by the two candidates when he checked the report for the
N
-th time.
It can be assumed that the number of votes obtained by each candidate never decreases.
Constraints
1≦N≦1000
1≦T_i,A_i≦1000 (1≦i≦N)
T_i
and
A_i
(1≦i≦N)
are coprime.
It is guaranteed that the correct answer is at most
10^{18}
.
Input
The input is given from Standard Input in the following format:
N
T_1
A_1
T_2
A_2
:
T_N
A_N
Output
Print the minimum possible total number of votes obtained by Takahashi and Aoki when AtCoDeer checked the report for the
N
-th time.
Sample Input 1
3
2 3
1 1
3 2
Sample Output 1
10
When the numbers of votes obtained by the two candidates change as
2,3 → 3,3 → 6,4
, the total number of votes at the end is
10
, which is the minimum possible number.
Sample Input 2
4
1 1
1 1
1 5
1 100
Sample Output 2
101
It is possible that neither candidate obtained a vote between the moment when he checked the report, and the moment when he checked it for the next time.
Sample Input 3
5
3 10
48 17
31 199
231 23
3 2
Sample Output 3
6930
Problem Description: Score : 300 points
Problem Statement
AtCoDeer the deer and his friend TopCoDeer is playing a game.
The game consists of
N
turns.
In each turn, each player plays one of the two
gestures
,
Rock
and
Paper
, as in Rock-paper-scissors, under the following condition:
(※) After each turn, (the number of times the player has played Paper)
≦
(the number of times the player has played Rock).
Each player's score is calculated by (the number of turns where the player wins)
-
(the number of turns where the player loses), where the outcome of each turn is determined by the rules of Rock-paper-scissors.
(For those who are not familiar with Rock-paper-scissors: If one player plays Rock and the other plays Paper, the latter player will win and the former player will lose. If both players play the same gesture, the round is a tie and neither player will win nor lose.)
With his supernatural power, AtCoDeer was able to foresee the gesture that TopCoDeer will play in each of the
N
turns, before the game starts.
Plan AtCoDeer's gesture in each turn to maximize AtCoDeer's score.
The gesture that TopCoDeer will play in each turn is given by a string
s
. If the
i
-th
(1≦i≦N)
character in
s
is
g
, TopCoDeer will play Rock in the
i
-th turn. Similarly, if the
i
-th
(1≦i≦N)
character of
s
in
p
, TopCoDeer will play Paper in the
i
-th turn.
Constraints
1≦N≦10^5
N=|s|
Each character in
s
is
g
or
p
.
The gestures represented by
s
satisfy the condition (※).
Input
The input is given from Standard Input in the following format:
s
Output
Print the AtCoDeer's maximum possible score.
Sample Input 1
gpg
Sample Output 1
0
Playing the same gesture as the opponent in each turn results in the score of
0
, which is the maximum possible score.
Sample Input 2
ggppgggpgg
Sample Output 2
2
For example, consider playing gestures in the following order: Rock, Paper, Rock, Paper, Rock, Rock, Paper, Paper, Rock, Paper. This strategy earns three victories and suffers one defeat, resulting in the score of
2
, which is the maximum possible score.
Problem Description: Score : 100 points
Problem Statement
CODE FESTIVAL 2016 is going to be held. For the occasion, Mr. Takahashi decided to make a signboard.
He intended to write
CODEFESTIVAL2016
on it, but he mistakenly wrote a different string
S
. Fortunately, the string he wrote was the correct length.
So Mr. Takahashi decided to perform an operation that replaces a certain character with another in the minimum number of iterations, changing the string to
CODEFESTIVAL2016
.
Find the minimum number of iterations for the rewrite operation.
Constraints
S
is
16
characters long.
S
consists of uppercase and lowercase alphabet letters and numerals.
Input
Inputs are provided from Standard Input in the following form.
S
Output
Output an integer representing the minimum number of iterations needed for the rewrite operation.
Sample Input 1
C0DEFESTIVAL2O16
Sample Output 1
2
The second character
0
must be changed to
O
and the
14
th character
O
changed to
0
.
Sample Input 2
FESTIVAL2016CODE
Sample Output 2
16