CodeEff/ECCO huggingface dataset:
Problem Name: Moving
Problem Description: Taro is going to move. Since Taro has a lot of luggage, he decided to ask the moving company to carry them. Since there are various weights of luggage, he asked the moving company to place them in an easy-to-understand way by placing them in order from the lightest. However, the person from the moving company placed the luggage in random order. Therefore, Taro tried to rearrange the luggage, but since the luggage is heavy, it requires physical strength to carry. Each luggage can be moved to any location between other luggage or the end of the luggage from its current location. However, to carry a certain luggage, it takes the same amount of physical strength as the weight of that luggage. Taro doesn't have much physical strength, so he decided to think of a way to arrange the luggage from the lightest without using too much physical strength.
Input
n
x
1
x
2
...
x
n
n
represents the number of luggage held by Taro
From
x
1
to
x
n
, each represents the weight of each luggage, and they are currently listed in order of
x
1
,
x
2
,...,
x
n
.
Constraints
1 ≤ n ≤ 10
5
1 ≤ x
i
≤ n (1 ≤ i ≤ n)
x
i
≠ x
j
(
1 ≤ i, j ≤ n
and
i ≠ j
)
All inputs are integers.
Output
S
Output the minimum total physical strength required to arrange the luggage from lightest to heaviest, followed by a new line.
Sample Input 1
4
1 4 2 3
Output for the Sample Input 1
4
If you move the weight 4 to the right end, it will be in order from lightest to heaviest.
Sample Input 2
5
1 5 3 2 4
Output for the Sample Input 2
7
If you move the weight 2 to the right of the weight 1, and move the weight 5 to the right end, it will be in order from lightest to heaviest.
Sample Input 3
7
1 2 3 4 5 6 7
Output for the Sample Input 3
0
They are already in order from lightest to heaviest.
Sample Input 4
8
6 2 1 3 8 5 4 7
Output for the Sample Input 4
19
Problem Name: Problem Name DNA
Problem Description: A gene is a string consisting of A, T, G, and C.
In this world, genes are known to follow a strange syntactic rule.
The syntax rule is given in the following form.
non-terminal symbol 1: symbol 1_1 symbol 1_2 ... symbol 1_n1
non-terminal symbol 2: symbol 2_1 symbol 2_2 ... symbol 2_n2
...
non-terminal symbol m: symbol m_1 symbol m_2 ... symbol m_nm
A symbol is either a non-terminal symbol or a terminal symbol.
Non-terminal symbols are represented by lowercase character strings, and terminal symbols are represented by strings of some of
A
,
T
,
G
, and
C
enclosed in "
[
" and "
]
".
Examples of syntax rules are as follows.
dna: a a b b
a: [AT]
b: [GC]
The "
non-terminal symbol i: symbol i_1 symbol i_2 ... symbol i_ni
" is called the rule of non-terminal symbol
i
, and each non-terminal symbol appearing in the syntax rule has exactly one rule.
A string
s
is said to "
match
" non-terminal symbol
i
if there exists a substring
{s
j
}
of
s
such that
s = s
1
+ s
2
+ ... + s
ni
and
s
j
(
1 ≤ j ≤ n
i
) matches symbol
j
in the rule.
A string
s
is said to "
match
" a terminal symbol if the string consists of a single character and the character is included in the string representing the terminal symbol.
A string is said to follow the syntax rule if it matches non-terminal symbol 1.
Rule
i
does not include any symbols that include non-terminal symbols
j
(
j ≤ i
) among the symbols.
You are given a syntax rule and four integers
Na
,
Nt
,
Ng
, and
Nc
.
Find the total number of genes that contain exactly
Na
A
s,
Nt
T
s,
Ng
G
s, and
Nc
C
s according to the syntax rule, divided by 1,000,000,007.
Input
Na
Nt
Ng
Nc
m
non-terminal symbol 1: symbol
1
1
symbol
1
2
... symbol
1
n1
non-terminal symbol 2: symbol
2
1
symbol
2
2
... symbol
2
n2
...
non-terminal symbol
m
: symbol
m
1
symbol
m
2
... symbol
m
nm
0 ≤ Na, Nt, Ng, Nc ≤ 50
1 ≤ m ≤ 50
1 ≤ ni ≤ 10
1 ≤
the length of the string representing the symbol
≤ 20
(Note that this is not the length of the string that matches the symbol.)
Output
The total number of genes divided by 1,000,000,007
Sample Input 1
1 0 1 0
3
dna: a b
a: [AT]
b: [GC]
Output for the Sample Input 1
1
It is one of "AG".
Sample Input 2
1 1 1 2
1
k: [ATG] [ATG] [ATG] [C] [C]
Output for the Sample Input 2
6
The six genes are "ATGCC", "AGTCC", "TAGCC", "TGACC", "GATCC", and "GTACC".
Sample Input 3
3 1 1 1
3
inv: at b b b
at: [ATG] b
b: [C]
Output for the Sample Input 3
0
Problem Name: Substring
Problem Description: You are given a string s=s1,s2,…,sn of length n and m queries. 
Each query qk (1 ≤ k ≤ m) is one of the 4 types: "L++", "L--", "R++", "R--".
For the k-th query qk, let l[k] and r[k] be defined as follows:
L++: l[k]=l[k-1]+1,r[k]=r[k-1]
L--: l[k]=l[k-1]-1,r[k]=r[k-1]
R++: l[k]=l[k-1],r[k]=r[k-1]+1
R--: l[k]=l[k-1],r[k]=r[k-1]-1
However, l[0]=r[0]=1.
For each of the m substrings
s
l[k]
, s
l[k]+1
, …, s
r[k]-1
, s
r[k]
(1 ≤ k ≤ m),
find the number of distinct substrings that can be formed.
Input
The input is given in the following format:
n m
s
q
1
q
2
…
q
m
Constraints
The string s consists of lowercase alphabets.
1 ≤ n ≤ 3×10
5
1 ≤ m ≤ 3×10
5
The k-th query q
k
(1 ≤ k ≤ m) is one of "L++", "L--", "R++", "R--".
1 ≤ l[k] ≤ r[k] ≤ n (1 ≤ k ≤ m)
Output
Output the answer to the problem in one line.
Sample Input 1
5 4
abcde
R++
R++
L++
L--
Output for the Sample Input 1
3
For l[1]=1 and r[1]=2, the substring is "ab".
For l[2]=1 and r[2]=3, the substring is "abc".
For l[3]=2 and r[3]=3, the substring is "bc".
For l[4]=1 and r[4]=3, the substring is "abc".
Therefore, the number of distinct substrings that can be formed is 3: {"ab","abc","bc"}.
Sample Input 2
4 6
abab
R++
L++
R++
L++
R++
L++
Output for the Sample Input 2
4
For l[1]=1 and r[1]=2, the substring is "ab".
For l[2]=2 and r[2]=2, the substring is "b".
For l[3]=2 and r[3]=3, the substring is "ba".
For l[4]=3 and r[4]=3, the substring is "a".
For l[5]=3 and r[5]=4, the substring is "ab".
For l[6]=4 and r[6]=4, the substring is "b".
Therefore, the number of distinct substrings that can be formed is 4: {"a","ab","b","ba"}.
Sample Input 3
10 13
aacacbabac
R++
R++
L++
R++
R++
L++
L++
R++
R++
L--
L--
R--
R--
Output for the Sample Input 3
11
Problem Statement
Problem Description: We found a dictionary of the Ancient Civilization Mayo (ACM) during excavation of the ruins.
After analysis of the dictionary, we revealed they used a language that had not more than 26 letters.
So one of us mapped each letter to a different English alphabet and typed all the words in the dictionary into a computer.
How the words are ordered in the dictionary, especially whether they are ordered lexicographically, is an interesting topic to many people.
As a good programmer, you are requested to write a program to judge whether we can consider the words to be sorted in a lexicographical order.
Note:
In a lexicographical order, a word always precedes other words it is a prefix of.
For example,
ab
precedes
abc
,
abde
, and so on.
Input
The input consists of multiple datasets. Each dataset is formatted as follows:
n
string_1
...
string_n
Each dataset consists of
n+1
lines.
The first line of each dataset contains an integer that indicates
n
(
1 \leq n \leq 500
).
The
i
-th line of the following
n
lines contains
string_i
, which consists of up to 10 English lowercase letters.
The end of the input is
0
, and this should not be processed.
Output
Print either
yes
or
no
in a line for each dataset, in the order of the input.
If all words in the dataset can be considered to be ordered lexicographically, print
yes
.
Otherwise, print
no
.
Sample Input
4
cba
cab
b
a
3
bca
ab
a
5
abc
acb
b
c
c
5
abc
acb
c
b
b
0
Output for the Sample Input
yes
no
yes
no
Problem Name: Problem A: Koto Distance
Problem Statement
Problem Description: Koto is a well-known city of grid streets. The city is a rectangle of W meters in width and H meters in height. The point located x meters eastward and y meters northward from the southwest corner of the city is denoted by (x,  y). People living in this city have long cherished their own unique culture, and one of them is a peculiar distance measure called the Koto distance. The Koto distance between two points (x_1, y_1) and (x_2, y_2) is defined by min(|x_1 - x_2|,  |y_1 - y_2|).
A plan has recently been launched to make the entire city Wi-Fi accessible. In the current plan,
N
base stations are to be installed. The
i
-th base station is installed at point
(x_i,  y_i)
and provides Wi-Fi service to the area where the Koto distance is no more than
w_i
.
Determine whether it is possible to provide Wi-Fi service in the city (including its boundary) by building the base stations according to the plan.
Note that the Koto distance generally does not satisfy the triangle inequality, and the distance axiom is violated only here.
Input Format
The input is given in the following format:
N
W
H
x_1
y_1
w_1
...
x_N
y_N
w_N
Output Format
If it is possible to provide Wi-Fi service in the city (including its boundary), print “Yes”; otherwise, print “No”.
Constraints
1 ≤ N ≤ 10^5
1 ≤ W ≤ 10^5
1 ≤ H ≤ 10^5
0 ≤ x_i ≤ W
0 ≤ y_i ≤ H
1 ≤ w_i ≤ 10^5
There are no multiple base stations at the same coordinates.
Sample Input and Output
Sample Input 1
3 9 9
2 2 2
5 5 2
8 8 2
Sample Output 1
Yes
The area covered by the Wi-Fi service provided by the second base station is as follows:
Sample Input 2
2 7 7
2 2 1
6 6 1
Sample Output 2
No
Sample Input 3
3 10 20
5 10 5
2 10 1
8 10 1
Sample Output 3
Yes
Problem Name: Problem B: Evacuation Route
Problem Description
Problem Description: In Japan, disaster prevention research is actively conducted, and its importance has been increasing in recent years.
Evaluation of evacuation routes is also one of the important research topics.
This time, we will evaluate the safety of a linear corridor.
The corridor is divided into
W
units, and the units on each end are numbered
0,  1,  2,  … ,  W-1
.
Each unit on the corridor has one of three things: an entrance door, an exit door, or a fire door.
There may be multiple entrance doors, exit doors, and fire doors in the corridor.
In this problem, assume that a fire occurs at time
t = 0
.
As a result, people outside the corridor who are trying to evacuate enter the corridor through the entrance door and try to escape to the exit door to a safer place.
Each person during evacuation can move one unit per unit time or remain in the current unit.
That is, if a person is in unit
i
at time
t
, the person can select one of the three numbers
i-1,  i,   i+1
that are between
0
and
W-1
at time
t+1
and move to the unit with that number.
Units with fire doors will be completely blocked after a certain period of time, and evacuees will not be able to enter that unit.
People in that unit will also not be able to move to other units.
The goal of this problem is to calculate the maximum number of people who can reach the exit door when each door's information is given and evacuees act optimally.
The information of the corridor is given by
W
integers
a_i
.
When
a_i = 0
, it means that the
i
-th unit is an exit door.
When
a_i < 0
, it means that the
i
-th unit can no longer be entered or exited after time
|a_i|
due to the fire door.
When
a_i > 0
, one person appears at the
i
-th unit at each of the times
t=0, 1, 2, … , a_{i}-1
. People who appear at time
t
start moving from time
t+1
.
Note that multiple people may exist in a single unit.
Output the maximum number of people who can reach the exit door in one line.
Input Format
The input is given in the following format.
W
a_0
a_1
...
a_{W-1}
Output Format
Output the maximum number of people who can reach the exit door in one line.
Constraints
1 ≤ W ≤ 10^5
|a_i|   ≤ 10^4
All input values are integers.
Sample Input and Output
Sample Input 1
7
2 0 -2 3 2 -2 0
Sample Output 1
4
Unit
0,   3,   5
have entrance doors and unit
1,   6
has exit doors.
From unit
0
, two people can go to unit
1
.
From unit
3
, one person can go to unit
1
.
From unit
5
, one person can go to unit
6
.
Therefore, a total of four people can reach the exit door.
Sample Input 2
4
1 1 1 1
Sample Output 2
0
No one can escape because there is no exit door.
Sample Input 3
9
10 -10 10 -10 10 -10 10 -10 0
Sample Output 3
24
Problem Description: A wants to get to his destination by taking the Yamanote Line.

A repeatedly wakes up for a minutes and sleeps for b minutes after boarding the train. The destination is reached c minutes after boarding, and if A is awake at this time, he can get off, but if he is sleeping, he will miss the stop. Also, even if A misses the stop, he will continue to ride the same train, which takes 60 minutes to go around the Yamanote Line. Therefore, A will arrive at the destination after 60t + c minutes (t is a non-negative integer).

At what time will A arrive at his destination? If it is impossible to arrive, output -1. However, if A is at the boundary between sleeping time and waking time when he arrives at the destination, he is assumed to be able to get off.

Input:
The input is given in the following format.
a b c

The input consists of three integers a, b, and c.

a is the time for waking up, b is the time for sleeping, and c is the time it takes to get to the destination after boarding. The unit of a, b, and c is minutes.

Constraints:
0 < a, b, c < 60

Output:
If A can arrive at the destination, output the time it takes for A to reach the destination. Otherwise, output -1.

Sample Input 1:
10 10 5

Sample Output 1:
5

Explanation 1:
A can reach the destination before going to sleep.

Sample Input 2:
50 40 51

Sample Output 2:
111

Explanation 2:
A will miss the stop once.

Sample Input 3:
20 20 20

Sample Output 3:
20

Explanation 3:
A almost falls asleep, but manages to stay awake until he reaches the destination.

Sample Input 4:
30 30 40

Sample Output 4:
-1

Explanation 4:
A wakes up in the first half of the circuit, but falls asleep in the second half, so he can't reach his destination.
Problem Description: In the year 20XX, the school's magic competition was underway. With only the final event remaining, you are one of the participants. The event you are participating in is a competition to determine the time it takes to destroy all the blue objects arranged in space. The players are allowed to bring guns for the competition. Inside the space, there are multiple blue objects and an equal number of red objects, as well as several obstacles. The blue objects correspond one-to-one with the red objects, and the player must shoot the blue object by firing a bullet from the coordinates where the red object is placed. The obstacles set up in the space are spherical, and although their composition is slightly different, if a normal bullet touches an obstacle, the bullet will stop in place. The bullets used in the competition are a special type called Magic Bullet. This bullet can store magical power, and when the bullet comes into contact with an obstacle, it automatically consumes magical power, and a magic spell is activated which allows the bullet to penetrate the obstacle. Due to the differences in the composition of the obstacles, the amount of magic power required to penetrate them or to activate the magic varies. Therefore, even after a magic spell has been activated for a particular obstacle, a different magic spell must be activated to penetrate another obstacle. Also, if a bullet comes into contact with multiple obstacles at the same time, the magic spells will be activated simultaneously. The amount of magical power stored in the bullet decreases each time a magic spell is activated. The position and size of the obstacles, as well as the amount of magical power required to activate the magic to penetrate them, have already been made public. However, the positions of the red and blue objects have not been released. However, based on information from previous competitions of the same type, it is possible to predict the positions of the objects to some extent. Because
Problem Description: In spring 2014, a student passed the university entrance exam and began living alone. The problem was what to do for dinner. He decided to plan his dinner for the next N days. He wants to maximize the total happiness he can get over N days. Of course, the more delicious or favorite food he eats, the happier he will be. He has two choices for dinner: go to a nearby cafeteria or cook by himself. The happiness he can get at the cafeteria varies depending on the menu of the day. The menu changes every day, but there is only one kind of food every day, and all N menus have already been published. So he knows that if he goes to the cafeteria on the i-th day (1 ≤ i ≤ N), he can get happiness C_i. The happiness he can get by cooking himself is the product of a constant P and the "cooking power" at the start of cooking. The "cooking power" has an initial value of Q and changes every day, decreasing by 1 if he goes to the cafeteria or increasing by 1 if he cooks by himself, and changing at the end of each day's meal. Find the maximum total happiness for him.
Prison
Problem Description: There are an infinite number of prisoners. At first, the prisoners are numbered 0, 1, 2, and so on.
Perform the following operation
N
times:
Release prisoner number
0
and execute prisoners
k, 2k, 3k,
and so on.
Then, renumber the remaining prisoners starting from
0, 1, 2,
and so on, in the order of their original numbers.
Find the number assigned to the prisoner who is released in the
N
-th operation.
Constraints
1
≤
N
≤
10^5
2
≤
k
≤
10^5
The answer is less than or equal to
10^{18}
.
Input Format
The input is given in the following format from standard input:
N
k
Output Format
Output the answer on a single line.
Sample Input 1
4 2
Sample Output 1
7
Sample Input 2
1 3
Sample Output 2
0
Sample Input 3
100000 100000
Sample Output 3
99999
ABC Gene
Problem Description: There is a genetic sequence represented by the string ABC. You can rewrite this genetic sequence by performing the following operation several times:
Choose one of the characters
A
,
B
, or
C
. Let this be
x
. Replace all occurrences of
x
in the genetic sequence with
ABC
simultaneously.
Given a string
S
consisting only of
A
,
B
, and
C
, determine if you can make the genetic sequence match
S
.
Constraints
1
≤
|S|
≤
5,000
S
consists only of
A
,
B
, and
C
.
Input Format
The input is given in the following format:
S
Output Format
If you can make the genetic sequence match
S
, print
Yes
; otherwise, print
No
.
Sample Input 1
ABC
Sample Output 1
Yes
The genetic sequence is already
ABC
to begin with.
Sample Input 2
AABCC
Sample Output 2
Yes
If you choose
B
and perform the operation,
ABC
becomes
AABCC
.
Sample Input 3
AABCABC
Sample Output 3
No
For example, if you choose
C
and perform the operation,
AABCC
becomes
AABCABC
. However, replacing each instance of
C
with
ABC
simultaneously results in
AABCC
becoming
AABABCABC
.
Dark Room
Problem Description: When A-kun woke up, he found himself in a completely dark room.
Apparently, A-kun had wandered into a dungeon consisting of N rooms.
You couldn't tell which room A-kun had wandered into, but fortunately you managed to get a map of the dungeon.
Guide A-kun through the dungeon to an illuminated room.
Of the
N
rooms,
M
are completely dark, and it is known that the rooms numbered
D_1
,
D_2
, ...,
D_M
are completely dark.
In addition, exactly
K
one-way paths are arranged in order from each room, and the path leaving room
i
is connected to room
v_{i,1}
,
v_{i,2}
, ...,
v_{i,K}
.
You can guide A-kun to move along the
a_1
,
a_2
, ...,
a_l
numbered paths in order.
However, once A-kun reaches an illuminated room, he will ignore any further instructions.
Since you cannot know the information about the room A-kun is in before and after the instructions, you must give him a sequence of instructions that will lead him to an illuminated room, no matter which room he is in.

Find the shortest such sequence of instructions.
Constraints
2  ≤  N  ≤  100
1  ≤  M  ≤  min(16, N − 1)
1  ≤  K  ≤  N
1  ≤  D_i  ≤  N
D_i
are all different
1  ≤  v_{i, j}  ≤  N
Every dark room can reach at least one illuminated room.
Input Format
The input is given in the following format, read from the standard input.
N
M
K
D_1
D_2
...
D_M
v_{1,1}
v_{1,2}
...
v_{1,K}
v_{2,1}
v_{2,2}
...
v_{2,K}
...
v_{N,1}
v_{N,2}
...
v_{N,K}
Output Format
Output the length of the shortest instruction sequence on a single line.
Sample Input 1
4 2 2
1 2
2 4
3 1
4 2
1 3
Sample Output 1
2
If you give the instructions "1, 1",
If A-kun is initially in room 1, he will reach room 3 on the second move.
If A-kun is initially in room 2, he will reach room 3 on the first move.
Sample Input 2
3 2 2
1 2
2 3
1 2
2 1
Sample Output 2
3
If you give the instructions "2, 1, 2",
If A-kun is initially in room 1, he will reach room 3 on the first move.
If A-kun is initially in room 2, he will reach room 3 on the third move.
Sample Input 3
6 3 3
1 2 3
4 1 1
2 5 2
3 3 6
4 4 4
5 5 5
6 6 6
Sample Output 3
3
Be careful of cases with disconnected components, self-loops, and multiple edges.
Problem Name: A : Finger Counting
Problem Statement
Problem Description: Nikunishi-kun can increase or decrease the number of fingers he has.
In front of Nikunishi-kun are n Japanese sweets.
Nikunishi-kun is trying to count the number of Japanese sweets by folding his fingers.
Nikunishi-kun can only fold his fingers in two ways, either folded or not folded.
Nikunishi-kun understands binary numbers.
Nikunishi-kun can assign binary digits to each finger and count numbers.
Nikunishi-kun does not understand logarithms.
Find the minimum number of fingers needed to count the Japanese sweets instead of Nikunishi-kun.
Input
n
Constraints
It is an integer.
0 ≤ n ≤ 10
18
Output
Output the answer on one line and end with a newline.
Sample
Sample Input 1
0
Sample Output 1
0
Sample Input 2
4
Sample Output 2
3
Sample Input 3
31
Sample Output 3
5
Sample Input 4
36028797018963968
Sample Output 4
56
Problem Name: D: Scanner
Problem Statement
Problem Description: You have $N$ pieces of paper to scan. You want to scan them all by using $3$ scanners in parallel. 
Each piece of paper takes a certain amount of time to scan, and the time it takes to scan the $i$-th piece of paper is $T_i$. 
The order in which you scan the papers is arbitrary, but you cannot scan multiple papers at the same time with one scanner.
Determine the minimum amount of time it takes for all the papers to be scanned and for all the scanners to stop scanning.
Input
$N$
$T_1$
$T_2$
$T_3$
$\vdots$
$T_N$
Constraints
$1 \leq N \leq 50$
$1 \leq T_i \leq 50$
All input values are integers.
Output
Print the minimum amount of time it takes for all the papers to be scanned and for all the scanners to stop scanning.
Sample Input #1
4
1
1
1
1
Sample Output #1
2
Sample Input #2
9
15
20
27
4
10
7
34
30
36
Sample Output #2
61
Sample Input #3
6
20
18
46
16
9
48
Sample Output #3
55
B: Periodic Sequence
Problem
Problem Description: Dr. Period, who serves as a professor at H University, researches the property called the "period" that is said to lurk in everything. As a basic period generally known, a period lurking in a sequence could be considered. That is, if the length N sequence S = S_1, S_2, ... , S_N satisfies the following property, it is a fact that it has a period t (t \≤ N).
For
1 \≤ i \≤ N − t
,
S_i=S_{i+t}
.
Now, Dr. Period is focusing on sequences that can be described more simply using periods. For example, if a length
N
sequence has a period
t
(
\≤ N
), and it can be written as
N=kt
using an integer
k
, the sequence can be described as a length
t
sequence
S_1,
...
, S_t
that is a concatenation of
k
continuous ones. Dr. Period has decided to call such a sequence a
k
-part.
Dr. Period is interested in the largest
k
-part. Therefore, you, as an assistant, have been asked to create a program that takes a sequence as input and outputs the largest
k
when it is a
k
-part. Create a program that accurately responds to Dr. Period's request.
Input Format
N
S_1
...
S_N
The first line contains an integer
N
, which represents the length of the sequence. The second line contains integers
S_i
(
1 \≤ i \≤ N
) that represent each element of the length
N
sequence, separated by spaces. The input satisfies
1 \≤ N \≤ 200,000
and
1 \≤ S_i \≤ 100,000
(
1 \≤ i \≤ N
).
Output Format
For the given sequence, output the maximum value of
k
when it is a
k
-part on one line.
Sample Input 1
6
1 2 3 1 2 3
Sample Output 1
2
Sample Input 2
12
1 2 1 2 1 2 1 2 1 2 1 2
Sample Output 2
6
Sample Input 3
6
1 2 3 4 5 6
Sample Output 3
1