CodeEff/ECCO huggingface dataset:
Problem Name: Number of Days
Problem Description: Write a program that takes two dates as input and outputs the number of days between those two dates. Date 1 (y1, m1, d1) is the same as or earlier than date 2 (y2, m2, d2), and date 1 is included in the count, but date 2 is not. Please calculate taking leap years into consideration. The conditions for leap years are as follows:
The year is divisible by 4.
However, years divisible by 100 are not leap years.
Years divisible by 400 are leap years.
Input
Multiple datasets will be given. The format for each dataset is as follows:
y
1
m
1
d
1
y
2
m
2
d
2
If any of
y
1
,
m
1
,
d
1
,
y
2
,
m
2
, or
d
2
is a negative number, the input will end.
The number of datasets will not exceed 50.
Output
For each dataset, output the number of days on one line.
Sample Input
2006 9 2 2006 9 3
2006 9 2 2006 11 11
2004 1 1 2005 1 1
2000 1 1 2006 1 1
2000 1 1 2101 1 1
-1 -1 -1 -1 -1 -1
Output for the Sample Input
1
70
366
2192
36890
Problem Name: Party

Problem
Problem Description: You decided to invite your school friends and your friends' friends to a Christmas party.
The number of students at your school is n, and each student is assigned a number from 1 to n.
Your number is 1.
You have a list that shows who is friends with whom.
Based on this list, create a program to determine the number of students you will invite to the Christmas party.
Input
The input consists of multiple datasets. Each dataset is given in the following format.
The first line of the dataset contains the number of students in the school, n (2 ≤ n ≤ 500), and the second line contains the length of the list, m (1 ≤ m ≤ 10000).
The input consists of 2+m lines in total. The 2+i-th line (1 ≤ i ≤ m) contains two integers a
i
and b
i
(1 ≤ a
i
< b
i
≤ n) separated by a space, indicating that the students with numbers a
i
and b
i
are friends.
The same line indicating the same friendship relationship will not appear twice.
Input ends when n and m are both 0. The number of datasets does not exceed 5.
Output
For each dataset, output the number of students you will invite to the Christmas party on one line.
Sample Input and Output
Input Example
6
5
1 2
1 3
3 4
2 3
4 5
6
5
2 3
3 4
4 5
5 6
2 5
0
0
Output Example
3
0
In the first input example, you have two friends, students with numbers 2 and 3.
Also, since the students numbered 3 and 4 are friends,
student number 4 is a friend of your friend.
The students numbered 5 and 6 are neither your friends nor your friends' friends.
Therefore, you will invite three students, numbers 2, 3, and 4, to the Christmas party.
In the second input example, you have no friends.
Therefore, the number of students you will invite to the Christmas party is 0.
The above problem statement and test data used by the automatic judge are provided by the
Japan Olympiad in Informatics
.
Space Coconut Crab
Problem Description: Ken Marine Blue is a space hunter who travels throughout the galaxy in search of the space coconut crab. It is said that the space coconut crab grows to a length of over 400 meters and spans over 1,000 meters when it spreads its legs. Many people have witnessed the space coconut crab, but no one has been able to catch it.
After a long investigation, Ken finally revealed important facts about the ecology of the space coconut crab. Surprisingly, the space coconut crab lives by performing the same warp technology called phase transition navigation while moving between normal space and hyperspace. Furthermore, it was found that it takes a long time for the space coconut crab to warp from hyperspace to normal space, and it cannot move in hyperspace for a while after warping.
Therefore, Ken decided to capture the space coconut crab. The strategy is as follows. First, observe the energy when the space coconut crab enters hyperspace from normal space. When the energy is
e
, the coordinates (
x
,
y
,
z
) where the space coconut crab warps out of hyperspace are known to satisfy the following conditions.
x
,
y
, and
z
are non-negative integers.
x
+
y
2
+
z
3
=
e
.
x
+
y
+
z
is minimized under the above conditions.
These conditions alone do not determine the coordinates uniquely, but it is certain that the coordinates where the warp-out occurs are on the plane where
x
+
y
+
z
=
m
. Here,
m
is the minimum value of
x
+
y
+
z
. Therefore, a barrier of sufficient size is set up on this plane. By doing so, the space coconut crab warps out to the location where the barrier is. The space coconut crab affected by the barrier cannot move.
Problem Name: Problem E: Powerful Cards
Problem Statement
Problem Description: In the card game Daihugou, cards with rank $2$ and $8$ are powerful. 
Thus, we call an integer consisting only of the digits $2$ and $8$ in its decimal notation a good number. 
We list good numbers in ascending order: $2, 8, 22, 28, 82, 88, \cdots$.
Let $n$ be a positive integer. 
Find the maximum number of factors that $n$ can have, where each factor is a good number. 
If $n$ cannot be represented as a product of good numbers, output $-1$.
Input
A single integer $n$.
Constraints
$1 \leq n \leq 10^{18}$
Output
Output the maximum number of factors that $n$ can have as a product of good numbers.
If $n$ cannot be represented as a product of good numbers, output $-1$.
Sample Input and Output
Sample Input 1
1
Sample Output 1
-1
Sample Input 2
2
Sample Output 2
1
Sample Input 3
88
Sample Output 3
3
$n$ can be expressed as $2 \times 2 \times 22$.
Sample Input 4
100
Sample Output 4
-1
Sample Input 5
173553147234869248
Sample Output 5
11
$n$ can be expressed as $2^6 \times 28 \times 2222^3 \times 8828$.
Problem Name: Connected Components
Problem Description: Write a program which reads relations in a SNS (Social Network Service), and judges that given pairs of users are reachable each other through the network.
Input
In the first line, two integer $n$ and $m$ are given. $n$ is the number of users in the SNS and $m$ is the number of relations in the SNS. The users in the SNS are identified by IDs $0, 1, ..., n-1$.
In the following $m$ lines, the relations are given. Each relation is given by two integers $s$ and $t$ that represents $s$ and $t$ are friends (and reachable each other).
In the next line, the number of queries $q$ is given. In the following $q$ lines, $q$ queries are given respectively. Each query consists of two integers $s$ and $t$ separated by a space character.
Output
For each query, print "yes" if $t$ is reachable from $s$ through the social network, "no" otherwise.
Constraints
$2 \leq n \leq 100,000$
$0 \leq m \leq 100,000$
$1 \leq q \leq 10,000$
Sample Input
10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3
Sample Output
yes
yes
no
Areas on the Cross-Section Diagram
Problem Description: Your task is to simulate a flood damage.
For a given cross-section diagram, reports areas of flooded sections.
Assume that rain is falling endlessly in the region and the water overflowing from the region is falling in the sea at the both sides.
For example, for the above cross-section diagram, the rain will create floods which have areas of 4, 2, 1, 19 and 9 respectively.
Input
A string, which represents slopes and flatlands by '
/
', '
\
' and '
_
' respectively, is given in a line. For example, the region of the above example is given by a string "
\\///\_/\/\\\\/_/\\///__\\\_\\/_\/_/\
".
output
Report the areas of floods in the following format:
$A$
$k$ $L_1$ $L_2$ ... $L_k$
In the first line, print the total area $A$ of created floods.
In the second line, print the number of floods $k$ and areas $L_i (i = 1, 2, ..., k)$ for each flood from the left side of the cross-section diagram. Print a space character before $L_i$.
Constraints
$1 \leq$ length of the string $\leq 20,000$
Sample Input 1
\\//
Sample Output 1
4
1 4
Sample Input 2
\\///\_/\/\\\\/_/\\///__\\\_\\/_\/_/\
Sample Output 2
35
5 4 2 1 19 9
Problem Name: Merge Sort
Problem Description: Write a program of a Merge Sort algorithm implemented by the following pseudocode. You should also report the number of comparisons in the Merge function.
Merge(A, left, mid, right)
  n1 = mid - left;
  n2 = right - mid;
  create array L[0...n1], R[0...n2]
  for i = 0 to n1-1
    do L[i] = A[left + i]
  for i = 0 to n2-1
    do R[i] = A[mid + i]
  L[n1] = SENTINEL
  R[n2] = SENTINEL
  i = 0;
  j = 0;
  for k = left to right-1
    if L[i] <= R[j]
      then A[k] = L[i]
           i = i + 1
      else A[k] = R[j]
           j = j + 1

Merge-Sort(A, left, right){
  if left+1 < right
    then mid = (left + right)/2;
         call Merge-Sort(A, left, mid)
         call Merge-Sort(A, mid, right)
         call Merge(A, left, mid, right)
Input
In the first line
n
is given. In the second line,
n
integers are given.
Output
In the first line, print the sequence S. Two consequtive elements should be separated by a space character.
In the second line, print the number of comparisons.
Constraints
n ≤ 500000
0 ≤ an element in S ≤ 10
9
Sample Input 1
10
8 5 9 2 6 3 7 1 10 4
Sample Output 1
1 2 3 4 5 6 7 8 9 10
34
Notes
Problem Name: Grading
Problem Description: Write a program which reads a list of student test scores and evaluates the performance for each student.
The test scores for a student include scores of the midterm examination
m
(out of 50), the final examination
f
(out of 50) and the makeup examination
r
(out of 100). If the student does not take the examination, the score is indicated by -1.
The final performance of a student is evaluated by the following procedure:
If the student does not take the midterm or final examination, the student's grade shall be F.
If the total score of the midterm and final examination is greater than or equal to 80, the student's grade shall be A.
If the total score of the midterm and final examination is greater than or equal to 65 and less than 80, the student's grade shall be B.
If the total score of the midterm and final examination is greater than or equal to 50 and less than 65, the student's grade shall be C.
If the total score of the midterm and final examination is greater than or equal to 30 and less than 50, the student's grade shall be D. However, if the score of the makeup examination is greater than or equal to 50, the grade shall be C.
If the total score of the midterm and final examination is less than 30, the student's grade shall be F.
Input
The input consists of multiple datasets. For each dataset, three integers
m
,
f
and
r
are given in a line.
The input ends with three -1 for
m
,
f
and
r
respectively. Your program should not process for the terminal symbols.
The number of datasets (the number of students) does not exceed 50.
Output
For each dataset, print the grade (
A
,
B
,
C
,
D
or
F
) in a line.
Sample Input
40 42 -1
20 30 -1
0 2 -1
-1 -1 -1
Sample Output
A
C
F
Problem Description: Score : 100 points
Problem Statement
You are given an array
a_0, a_1, ..., a_{N-1}
of length
N
. Process
Q
queries of the following types.
The type of
i
-th query is represented by
T_i
.
T_i=1
: You are given two integers
X_i,V_i
. Replace the value of
A_{X_i}
with
V_i
.
T_i=2
: You are given two integers
L_i,R_i
. Calculate the maximum value among
A_{L_i},A_{L_i+1},\cdots,A_{R_i}
.
T_i=3
: You are given two integers
X_i,V_i
. Calculate the minimum
j
such that
X_i \leq j \leq N, V_i \leq A_j
. If there is no such
j
, answer
j=N+1
instead.
Constraints
1 \leq N \leq 2 \times 10^5
0 \leq A_i \leq 10^9
1 \leq Q \leq 2 \times 10^5
1 \leq T_i \leq 3
1 \leq X_i \leq N
,
0 \leq V_i \leq 10^9
(
T_i=1,3
)
1 \leq L_i \leq R_i \leq N
(
T_i=2
)
All values in Input are integer.
Input
Input is given from Standard Input in the following format:
N
Q
A_1
A_2
\cdots
A_N
First query
Second query
\vdots
Q
-th query
Each query is given in the following format:
If
T_i=1,3
,
T_i
X_i
V_i
If
T_i=2
,
T_i
L_i
R_i
Output
For each query with
T_i=2, 3
, print the answer.
Sample Input 1
5 5
1 2 3 2 1
2 1 5
3 2 3
1 3 1
2 2 4
3 1 3
Sample Output 1
3
3
2
6
First query: Print
3
, which is the maximum of
(A_1,A_2,A_3,A_4,A_5)=(1,2,3,2,1)
.
Second query: Since
3>A_2
,
j=2
does not satisfy the condition．Since
3 \leq A_3
, print
j=3
.
Third query: Replace the value of
A_3
with
1
. It becomes
A=(1,2,1,2,1)
.
Fourth query: Print
2
, which is the maximum of
(A_2,A_3,A_4)=(2,1,2)
.
Fifth query: Since there is no
j
that satisfies the condition, print
j=N+1=6
.
Problem Description: Score : 400 points
Problem Statement
There are
N
persons called Person
1
through Person
N
.
You are given
M
facts that "Person
A_i
and Person
B_i
are friends." The same fact may be given multiple times.
If
X
and
Y
are friends, and
Y
and
Z
are friends, then
X
and
Z
are also friends. There is no friendship that cannot be derived from the
M
given facts.
Takahashi the evil wants to divide the
N
persons into some number of groups so that every person has no friend in his/her group.
At least how many groups does he need to make?
Constraints
2 \leq N \leq 2\times 10^5
0 \leq M \leq 2\times 10^5
1\leq A_i,B_i\leq N
A_i \neq B_i
Input
Input is given from Standard Input in the following format:
N
M
A_1
B_1
\vdots
A_M
B_M
Output
Print the answer.
Sample Input 1
5 3
1 2
3 4
5 1
Sample Output 1
3
Dividing them into three groups such as
\{1,3\}
,
\{2,4\}
, and
\{5\}
achieves the goal.
Sample Input 2
4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4
Sample Output 2
4
Sample Input 3
10 4
3 1
4 1
5 9
2 6
Sample Output 3
3
Problem Description: Score : 400 points
Problem Statement
For a positive integer
X
, let
f(X)
be the number of positive divisors of
X
.
Given a positive integer
N
, find
\sum_{K=1}^N K\times f(K)
.
Constraints
1 \leq N \leq 10^7
Input
Input is given from Standard Input in the following format:
N
Output
Print the value
\sum_{K=1}^N K\times f(K)
.
Sample Input 1
4
Sample Output 1
23
We have
f(1)=1
,
f(2)=2
,
f(3)=2
, and
f(4)=3
, so the answer is
1\times 1 + 2\times 2 + 3\times 2 + 4\times 3 =23
.
Sample Input 2
100
Sample Output 2
26879
Sample Input 3
10000000
Sample Output 3
838627288460105
Watch out for overflows.
Problem Description: Score : 400 points
Problem Statement
Given is a string
S
consisting of digits from
1
through
9
.
Find the number of pairs of integers
(i,j)
(
1 ≤ i ≤ j ≤ |S|
) that satisfy the following condition:
Condition: In base ten, the
i
-th through
j
-th characters of
S
form an integer that is a multiple of
2019
.
Constraints
1 ≤ |S| ≤ 200000
S
is a string consisting of digits from
1
through
9
.
Input
Input is given from Standard Input in the following format:
S
Output
Print the number of pairs of integers
(i,j)
(
1 ≤ i ≤ j ≤ |S|
) that satisfy the condition.
Sample Input 1
1817181712114
Sample Output 1
3
Three pairs -
(1,5)
,
(5,9)
, and
(9,13)
- satisfy the condition.
Sample Input 2
14282668646
Sample Output 2
2
Sample Input 3
2119
Sample Output 3
0
No pairs satisfy the condition.
Problem Description: Score : 600 points
Problem Statement
We have a tree with
N
vertices numbered
1
to
N
. The
i
-th edge in this tree connects Vertex
a_i
and
b_i
.
Additionally, each vertex is painted in a color, and the color of Vertex
i
is
c_i
. Here, the color of each vertex is represented by an integer between
1
and
N
(inclusive). The same integer corresponds to the same color; different integers correspond to different colors.
For each
k=1, 2, ..., N
, solve the following problem:
Find the number of simple paths that visit a vertex painted in the color
k
one or more times.
Note:
The simple paths from Vertex
u
to
v
and from
v
to
u
are not distinguished.
Constraints
1 \leq N \leq 2 \times 10^5
1 \leq c_i \leq N
1 \leq a_i,b_i \leq N
The given graph is a tree.
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
c_1
c_2
...
c_N
a_1
b_1
:
a_{N-1}
b_{N-1}
Output
Print the answers for
k = 1, 2, ..., N
in order, each in its own line.
Sample Input 1
3
1 2 1
1 2
2 3
Sample Output 1
5
4
0
Let
P_{i,j}
denote the simple path connecting Vertex
i
and
j
.
There are
5
simple paths that visit a vertex painted in the color
1
one or more times:
P_{1,1}\,,\,
P_{1,2}\,,\,
P_{1,3}\,,\,
P_{2,3}\,,\,
P_{3,3}
There are
4
simple paths that visit a vertex painted in the color
2
one or more times:
P_{1,2}\,,\,
P_{1,3}\,,\,
P_{2,2}\,,\,
P_{2,3}
There are no simple paths that visit a vertex painted in the color
3
one or more times.
Sample Input 2
1
1
Sample Output 2
1
Sample Input 3
2
1 2
1 2
Sample Output 3
2
2
Sample Input 4
5
1 2 3 4 5
1 2
2 3
3 4
3 5
Sample Output 4
5
8
10
5
5
Sample Input 5
8
2 7 2 5 4 1 7 5
3 1
1 2
2 7
4 5
5 6
6 8
7 8
Sample Output 5
18
15
0
14
23
0
23
0
Problem Description: Score : 600 points
Problem Statement
Given are a sequence of
N
integers
A_1
,
A_2
,
\ldots
,
A_N
and a positive integer
S
.
For a pair of integers
(L, R)
such that
1\leq L \leq R \leq N
, let us define
f(L, R)
as follows:
f(L, R)
is the number of sequences of integers
(x_1, x_2, \ldots , x_k)
such that
L \leq x_1 < x_2 < \cdots < x_k \leq R
and
A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S
.
Find the sum of
f(L, R)
over all pairs of integers
(L, R)
such that
1\leq L \leq R\leq N
. Since this sum can be enormous, print it modulo
998244353
.
Constraints
All values in input are integers.
1 \leq N \leq 3000
1 \leq S \leq 3000
1 \leq A_i \leq 3000
Input
Input is given from Standard Input in the following format:
N
S
A_1
A_2
...
A_N
Output
Print the sum of
f(L, R)
, modulo
998244353
.
Sample Input 1
3 4
2 2 4
Sample Output 1
5
The value of
f(L, R)
for each pair is as follows, for a total of
5
.
f(1,1) = 0
f(1,2) = 1
(for the sequence
(1, 2)
)
f(1,3) = 2
(for
(1, 2)
and
(3)
)
f(2,2) = 0
f(2,3) = 1
(for
(3)
)
f(3,3) = 1
(for
(3)
)
Sample Input 2
5 8
9 9 9 9 9
Sample Output 2
0
Sample Input 3
10 10
3 1 4 1 5 9 2 6 5 3
Sample Output 3
152
Problem Description: Score : 300 points
Problem Statement
Fennec is fighting with
N
monsters.
The
health
of the
i
-th monster is
H_i
.
Fennec can do the following two actions:
Attack: Fennec chooses one monster. That monster's health will decrease by
1
.
Special Move: Fennec chooses one monster. That monster's health will become
0
.
There is no way other than Attack and Special Move to decrease the monsters' health.
Fennec wins when all the monsters' healths become
0
or below.
Find the minimum number of times Fennec needs to do Attack (not counting Special Move) before winning when she can use Special Move at most
K
times.
Constraints
1 \leq N \leq 2 \times 10^5
0 \leq K \leq 2 \times 10^5
1 \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_N
Output
Print the minimum number of times Fennec needs to do Attack (not counting Special Move) before winning.
Sample Input 1
3 1
4 1 5
Sample Output 1
5
By using Special Move on the third monster, and doing Attack four times on the first monster and once on the second monster, Fennec can win with five Attacks.
Sample Input 2
8 9
7 9 3 2 3 8 4 6
Sample Output 2
0
She can use Special Move on all the monsters.
Sample Input 3
3 0
1000000000 1000000000 1000000000
Sample Output 3
3000000000
Watch out for overflow.
Problem Description: Score : 700 points
Problem Statement
We have
N
cards numbered
1, 2, ..., N
.
Card
i
(
1 \leq i \leq N
) has an integer
A_i
written in red ink on one side and an integer
B_i
written in blue ink on the other side.
Initially, these cards are arranged from left to right in the order from Card
1
to Card
N
, with the red numbers facing up.
Determine whether it is possible to have a non-decreasing sequence facing up from left to right (that is, for each
i
(
1 \leq i \leq N - 1
), the integer facing up on the
(i+1)
-th card from the left is not less than the integer facing up on the
i
-th card from the left) by repeating the operation below. If the answer is yes, find the minimum number of operations required to achieve it.
Choose an integer
i
(
1 \leq i \leq N - 1
).
Swap the
i
-th and
(i+1)
-th cards from the left, then flip these two cards.
Constraints
1 \leq N \leq 18
1 \leq A_i, B_i \leq 50
(
1 \leq i \leq N
)
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1
A_2
...
A_N
B_1
B_2
...
B_N
Output
If it is impossible to have a non-decreasing sequence, print
-1
.
If it is possible, print the minimum number of operations required to achieve it.
Sample Input 1
3
3 4 3
3 2 3
Sample Output 1
1
By doing the operation once with
i = 1
, we have a sequence
[2, 3, 3]
facing up, which is non-decreasing.
Sample Input 2
2
2 1
1 2
Sample Output 2
-1
After any number of operations, we have the sequence
[2, 1]
facing up, which is not non-decreasing.
Sample Input 3
4
1 2 3 4
5 6 7 8
Sample Output 3
0
No operation may be required.
Sample Input 4
5
28 15 22 43 31
20 22 43 33 32
Sample Output 4
-1
Sample Input 5
5
4 46 6 38 43
33 15 18 27 37
Sample Output 5
3
Problem Description: Score : 400 points
Problem Statement
At an arcade, Takahashi is playing a game called
RPS Battle
, which is played as follows:
The player plays
N
rounds of Rock Paper Scissors against the machine. (See Notes for the description of Rock Paper Scissors. A draw also counts as a round.)
Each time the player wins a round, depending on which hand he/she uses, he/she earns the following score (no points for a draw or a loss):
R
points for winning with Rock;
S
points for winning with Scissors;
P
points for winning with Paper.
However, in the
i
-th round, the player cannot use the hand he/she used in the
(i-K)
-th round. (In the first
K
rounds, the player can use any hand.)
Before the start of the game, the machine decides the hand it will play in each round. With supernatural power, Takahashi managed to read all of those hands.
The information Takahashi obtained is given as a string
T
. If the
i
-th character of
T
(1 \leq i \leq N)
is
r
, the machine will play Rock in the
i
-th round. Similarly,
p
and
s
stand for Paper and Scissors, respectively.
What is the maximum total score earned in the game by adequately choosing the hand to play in each round?
Notes
In this problem, Rock Paper Scissors can be thought of as a two-player game, in which each player simultaneously forms Rock, Paper, or Scissors with a hand.
If a player chooses Rock and the other chooses Scissors, the player choosing Rock wins;
if a player chooses Scissors and the other chooses Paper, the player choosing Scissors wins;
if a player chooses Paper and the other chooses Rock, the player choosing Paper wins;
if both players play the same hand, it is a draw.
Constraints
2 \leq N \leq 10^5
1 \leq K \leq N-1
1 \leq R,S,P \leq 10^4
N,K,R,S,
and
P
are all integers.
|T| = N
T
consists of
r
,
p
, and
s
.
Input
Input is given from Standard Input in the following format:
N
K
R
S
P
T
Output
Print the maximum total score earned in the game.
Sample Input 1
5 2
8 7 6
rsrpr
Sample Output 1
27
The machine will play {Rock, Scissors, Rock, Paper, Rock}.
We can, for example, play {Paper, Rock, Rock, Scissors, Paper} against it to earn
27
points.
We cannot earn more points, so the answer is
27
.
Sample Input 2
7 1
100 10 1
ssssppr
Sample Output 2
211
Sample Input 3
30 5
325 234 123
rspsspspsrpspsppprpsprpssprpsr
Sample Output 3
4996