CodeEff/ECCO huggingface dataset:
Problem Name: Passcode
Problem Description: The new passcode is difficult to remember. I was told not to write it down, but I don't think I can remember it. So I decided to embed numbers in the text and make a memo of the passcode. Here, the sum of all the numbers will be the passcode.
Create a program that reads the memoized text and outputs the passcode.
Input
A positive integer is embedded in the text, given over multiple lines. Each line is a string including half-width alphanumeric characters, symbols, and spaces, or a blank line.
However, the input is guaranteed to be within 80 characters per line, and the passcode is guaranteed to be less than or equal to 10,000.
Output
Output the passcode (the sum of positive integers in the text) on one line.
Sample Input
Thereare100yenonthetable.Iam17yearsold.
Ishouldgohomeat6pm.
Output for the Sample Input
123
Problem Name: Overlap of seals
Problem Description: You stick n circular seals with radius 1 on a square origami paper of length 10. Seals can be pasted on top of each other. Create a program that reads the coordinates of where the seals are pasted and outputs the number of seals that overlap the most at the location where they overlap the most on the origami paper (even if only one seal overlaps, it is considered "overlapping").
The
x, y
coordinates are given with the origin at the lower left of the origami paper. The seals are pasted with the
x, y
coordinates as the center of the circle. The center of the circle will not go outside of the origami paper. Additionally, multiple seals will not be pasted on the same coordinate.
Input
Multiple data sets are given. Each dataset is given in the following format.
n
x
1
,
y
1
x
2
,
y
2
:
x
n
,
y
n
The number of seals
n
(0 ≤ 100) is given on the first line. The center coordinates of each seal are given on the following
n
lines.
x
i
and
y
i
represent the
x
and
y
coordinates of the center of the
i
-th seal, respectively. Each value is given as a real number with up to 6 decimal places.
The input is terminated when
n
is 0. The number of data sets is no more than 50.
Output
For each data set, output the number of seals (an integer) at the location where the most seals overlap on the origami paper.
Sample Input
15
3.14979,8.51743 
2.39506,3.84915 
2.68432,5.39095 
5.61904,9.16332 
7.85653,4.75593 
2.84021,5.41511 
1.79500,8.59211 
7.55389,8.17604 
4.70665,4.66125 
1.63470,4.42538 
7.34959,4.61981 
5.09003,8.11122 
5.24373,1.30066 
0.13517,1.83659 
7.57313,1.58150 
0
Output for the Sample Input
4
Hint
The figure below shows the seals pasted as in the sample input. The circles represent the seals, and the numbers represent the corresponding input lines.
At the point (2.3, 4.6), 4 seals from the 2nd, 3rd, 6th, and 10th lines of the input overlap.
When two circles are touching (i.e., the distance between the centers is 2), it is considered overlapping.
Problem Name: Baseball Simulation
Problem Description: Ichiro likes baseball and has decided to write a program which simulates baseball.
The program reads events in an inning and prints score in that inning. There are only three events as follows:
Single hit
put a runner on the first base.
the runner in the first base advances to the second base and the runner in the second base advances to the third base.
the runner in the third base advances to the home base (and go out of base) and a point is added to the score.
Home run
all the runners on base advance to the home base.
points are added to the score by an amount equal to the number of the runners plus one.
Out
The number of outs is increased by 1.
The runners and the score remain stationary.
The inning ends with three-out.
Ichiro decided to represent these events using "HIT", "HOMERUN" and "OUT", respectively.
Write a program which reads events in an inning and prints score in that inning. You can assume that the number of events is less than or equal to 100.
Input
The input consists of several datasets. In the first line, the number of datasets
n
is given. Each dataset consists of a list of events (strings) in an inning.
Output
For each dataset, prints the score in the corresponding inning.
Sample Input
2
HIT
OUT
HOMERUN
HIT
HIT
HOMERUN
HIT
OUT
HIT
HIT
HIT
HIT
OUT
HIT
HIT
OUT
HIT
OUT
OUT
Output for the Sample Input
7
0
Problem Name: Cryptogram
Problem Description: A problem that hides part of a mathematical formula and asks you to find the hidden numbers is called a cryptogram. This time, we will deal with an equation in which some of the digits are hidden by X. Please create a program that inputs the equation below and outputs the result.
Equation
It is a simple addition formula in the form of "number string + number string = number string" in one line.
"Number string" is a sequence of numbers 0 to 9 and the character X.
The leftmost digit of the "number string" with two or more digits is not 0.
X is included in the entire formula.
Output
This is the answer to the cryptogram. It is a value of X between 0 and 9 that satisfies the formula. There are no more than two answers.
If there is no answer, the result should be "NA".
Input
Multiple datasets are given. As each dataset, a one-line addition formula (a string of up to 126 characters without spaces) that contains X one or more times is given. The number of datasets does not exceed 150.
Output
For each dataset, output the result of the cryptogram on one line. Output a number from 0 to 9 or NA.
Sample Input
123+4X6=X79
12X+4X6=X79
XX22+89=X2XX
Output for the Sample Input
5
NA
1
Problem Name: Fill Game
Problem Description: The technology for tablet interfaces that can be operated by touching the screen with your finger is also applied in the field of games, and various types of games with new operation feelings are being created. The game being developed by AZ is one of them.
The requirements of this software (game) are as follows:
There is a 2D grid of
X
columns by
Y
rows on the screen.
The cells of the grid are painted in one of three colors: red (R), green (G), or brown (B).
There are buttons R, G, and B to change the color of the cell, and when this button is pressed, the cell at the upper left corner (0,0) is changed to that color.
When the color of the upper left cell is changed, all adjacent cells that are painted with the same color as the original cell are changed to the specified color. That is, all linked cells painted with the same color as the original cell are changed to the specified color.
The game is to fill in the grid like this and eventually make the entire grid one color. A high score is given for solving it in as few steps as possible.
You, a programmer at AZ, have been tasked with developing part of the logic for this game. First, you decided to create a program to calculate the maximum score by determining the minimum number of times you need to operate the selection button to make the grid one color in the shortest possible time.
Input
Multiple datasets are given. The end of the input is indicated by two zeros. Each dataset is given in the following format:
X
Y
c
1,1
c
2,1
...
c
X,1
c
1,2
c
2,2
...
c
X,2
:
c
1,Y
c
2,Y
...
c
X,Y
The first line contains the size of the grid: the number of columns
X
and the number of rows
Y
(2 ≤
X
,
Y
≤ 10). The colors of the cells in the
j
-th row of the
i
-th column,
c
i,j
, are given on the next line as space-separated characters.
Output
For each dataset, output the minimum number of button operations on one line.
Sample Input
3 3
R G B
G G G
G B B
2 4
R G
G G
R B
B R
4 3
G G B R
G R R G
B G G R
0 0
Sample Output
2
4
4
Problem Name: Day of Week
Problem Description: The 9th day of September 2017 is Saturday. Then, what day of the week is the X-th of September 2017?
Given a day in September 2017, write a program to report what day of the week it is.
Input
The input is given in the following format.
X
The input line specifies a day
X
(1 ≤
X
≤ 30) in September 2017.
Output
Output what day of the week it is in a line. Use the following conventions in your output: "
mon
" for Monday, "
tue
" for Tuesday, "
wed
" for Wednesday, "
thu
" for Thursday, "
fri
" for Friday, "
sat
" for Saturday, and "
sun
" for Sunday.
Sample Input 1
1
Sample Output 1
fri
Sample Input 2
9
Sample Output 2
sat
Sample Input 3
30
Sample Output 3
sat
Problem Name:
Problem Description: There are n squares of the same size. Arrange them in several rows, aligning the bottom of the paper horizontally. However, the columns adjacent to each other must be arranged so that the left side does not become lower than the right side. For example, when n = 5, it is possible to arrange in the following 7 ways.
Let us express them by the column of the number of squares arranged in each column. For example, when
n
= 5, they are expressed respectively as
(5) (4, 1) (3, 2) (3, 1, 1) (2, 2, 1) (2, 1, 1, 1) (1, 1, 1, 1, 1)
When
n
is given, create a program that outputs all of them in dictionary order.
n
≤30. However, the dictionary order means that when arranging two arrangements (
a
1
,
a
2
, ...,
a
s
) and (
b
1
,
b
2
, ...,
b
t
) in dictionary order, arrange them so that (
a
1
,
a
2
, ...,
a
s
) is output before (
b
1
,
b
2
, ...,
b
t
) if
a
1
>
b
1
or there is an integer
i
> 1 such that
a
1
=
b
1
, ...,
a
i
-1
=
b
i
-1
and
a
i
>
b
i
.
The input data consists of multiple datasets. The input ends when n = 0. The number of datasets is no more than 5.
Output
For each dataset, output them all in dictionary order.
Input example
5
5
0
Output example
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
The above problem statement and the test data used in the automatic judge are problem statements and grading test data created and made public by the Information Olympiad Japan Committee.
Problem Name: Icicles
Problem
Problem Description: JOI has noticed some splendid icicles hanging from the roof of his house in Canada. He decides to investigate the icicles. There are N (2 ≤ N ≤ 100000 = 105) icicles hanging from the roof of JOI's house. The icicles are arranged in a line, with the i-th icicle hanging at a position i cm from the left end of the roof (1 ≤ i ≤ N). The initial length of the i-th icicle is ai cm (ai is an integer greater than or equal to 1). The icicles grow in the following manner:
An icicle grows by 1 cm per hour if it is longer than both of its neighbors. However, if an icicle reaches the length L (2 ≤ L ≤ 50000) it will break off at its base (the broken icicle is then regarded as having length 0 cm).
At the beginning, the lengths of neighboring icicles are all different. If enough time passes, all the icicles will break off and have length 0 cm. JOI wants to know how long it will take for all the icicles to break off.
Write a program that, given the initial lengths of the icicles and the maximum length L, determines the time required for all the icicles to break off.
Input
The first line of the input contains two integers N and L, separated by a space, where N is the number of icicles and L is the maximum length of the icicles. The i-th of the following N lines (1 ≤ i ≤ N) contains the integer ai (1 ≤ ai < L) denoting the initial length of the i-th icicle.
For 30% of the available marks, N ≤ 500 and L ≤ 1000.
Output
The output should consist of a single line containing an integer, the time required for all the icicles to break off.
Sample Input and Output
Sample Input 1
4 6
4
2
3
5
Sample Output 1
8
For the above input, the first, second, third, and fourth icicles will break off after 2, 8, 4, and 1 hour, respectively. Therefore, all the icicles will break off after 8 hours. Hence, the output is 8.
Sample Input 2
6 10
3
4
1
9
5
1
Sample Output 2
15
The problem statement and test data used in the automatic judging system are those prepared and published by the
Information-technology Promotion Agency, Japan
.
Problem Name: Problem 3: Super Metropolis
Problem
Problem Description: JOI is planning a sightseeing tour of a city called Super Metropolis in IOI country.
Super Metropolis is divided into a grid-like pattern by W straight roads running north-south and H straight roads running east-west.
The W north-south roads are numbered 1, 2, ..., W from west to east, and the H east-west roads are numbered 1, 2, ..., H from south to north. An intersection of the i-th north-south road from the west and the j-th east-west road from the south is denoted by (i, j).
Furthermore, as shown in the figure below, there is a road from each intersection to one northeast intersection (except for the intersection on the northernmost road and the intersection on the easternmost road).
There is also a road to one southwest intersection (except for the intersection on the southernmost road and the intersection on the westernmost road).
That is, if there are intersections (i - 1, j), (i + 1, j), (i, j - 1), and (i, j + 1) at intersection (i, j), it is possible to go to those intersections using one road each. In addition, if there are intersections (i - 1, j - 1) and (i + 1, j + 1), it is possible to go to those intersections using one road each.
JOI has already decided the order in which he will visit N tourist spots as part of his tour.
The i-th (1 ≦ i ≦ N) tourist spot is located at intersection (X
i
, Y
i
).
To minimize the time required for the tour, JOI wants to use as few roads as possible that he must pass through.
Create a program that finds the minimum number of roads that must be passed through to visit the tourist spots in the predetermined order.
However, the starting point of the tour is intersection (X
1
, Y
1
), and JOI must not move outside of Super Metropolis during the tour.
Also, JOI can pass through an intersection with a tourist spot without visiting it.
Note that it is possible to pass the same road more than once during the tour. In that case, the number of times the road is passed is counted as the number of times that road is counted.
Input
The input consists of 1 + N lines.
The first line contains three integers W, H, and N (2 ≤ W ≤ 10000, 2 ≤ H ≤ 10000, 1 ≤ N ≤ 1000) separated by a space.
The i-th (1 ≤ i ≤ N) of the following N lines contains two integers X
i
and Y
i
(1 ≤ X
i
≤ W, 1 ≤ Y
i
≤ H) separated by a space. This indicates that the intersection where the i-th tourist spot is located is (X
i
, Y
i
).
Output
Output the minimum total number of roads that must be passed through to visit the tourist spots in the predetermined order on one line.
Examples
Example 1
Input:
4 3 3
1 1
3 3
4 1

Output:
5
In Example 1, it is sufficient to visit the intersections in the following order: (1, 1), (2, 2), (3, 3), (3, 2), (4, 2), and (4, 1).
Example 2
Input:
4 3 5
1 3
4 3
2 2
2 2
1 3

Output:
7
In Example 2, the same intersection may be visited multiple times.
The problem statement and test data are based on those provided by Information-technology Promotion Agency, Japan (IPA).
Problem Name: Problem B: Perfect Numbers
Problem Description: For a given integer N, let S be the sum of its
    divisors excluding itself.
    If N = S, N is called a
    perfect number. If N < S, N is
    called a deficient number. If N > S,
    N is called an abundant number.
    Write a program that determines whether a given integer is a perfect,
    deficient or abundant number.
Be careful not to exceed the time limit for your program.
Input
The input consists of multiple datasets.
    There are at most 100 datasets.
Each dataset consists of a single integer
N
(0 <
N
≤ 100000000).
The end of the input is indicated by a line containing a single zero.
Output
For each dataset, output one line containing either “
perfect number
”
    if the integer is perfect, “
deficient number
”
    if the integer is deficient, or “
abundant number
”
    if the integer is abundant.
Sample Input
1
2
3
4
6
12
16
28
33550336
99999998
99999999
100000000
0
Output for the Sample Input
deficient number
deficient number
deficient number
deficient number
perfect number
abundant number
deficient number
perfect number
perfect number
deficient number
deficient number
abundant number
Problem Name: B : RUPC
Problem Statement
Problem Description: A programming contest is held in the Russian Federation. There are N problems in the contest, and M participants participate. Each problem i has a score of a_i, and it is known that the strength of participant j is b_j. For each problem i and participant j, when a_i ≤ b_j, that participant can solve problem i if and only if. The participant's score for the contest is the sum of the scores of the problems that he/she can solve. Also, participant j sets a target score c_j for this contest.
Determine whether each participant can score at least the target score.
Input
The input is given in the following format.
N
a_{0}
a_{1}
a_{2}
…
a_{N−1}
M
b_{0}
b_{1}
b_{2}
…
b_{M−1}
c_{0}
c_{1}
c_{2}
…
c_{M−1}
Constraints
All inputs are integers.
1 \≤ N \≤ 300,000
1 \≤ M \≤ 300,000
0 \≤ a_{i} \≤ 1,000,000
0 \≤ b_{i} \≤ 1,000,000
0 \≤ c_{i} \≤ ∑a_k
Output
Output the answer on
M
lines. If participant
i-1
can score at least the target score, output
Yes
; otherwise, output
No
.
Samples
Sample Input 1
6
1 2 1 3 4 5
7
1 3 4 5 3 1 0
2 4 5 3 4 5 3
Sample Output 1
Yes
Yes
Yes
Yes
Yes
No
No
The score of each participant is as follows.
Participant 0:
1+1=2
Participant 1:
1+2+1+3=7
Participant 2:
1+2+1+3+4=11
Participant 3:
1+2+1+3+4+5=16
Participant 4:
1+2+1+3=7
Participant 5:
1+1=2
Participant 6:
0
Sample Input 2
8
1 1 2 3 3 4 6 100
4
1 3 4 99
1 10 15 120
Sample Output 2
Yes
Yes
No
No
Problem Name: Bubble Sort
Problem Description: Write a program of the Bubble Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:
BubbleSort(A)
1 for i = 0 to A.length-1
2     for j = A.length-1 downto i+1
3         if A[j] < A[j-1]
4             swap A[j] and A[j-1]
Note that, indices for array elements are based on 0-origin.
Your program should also print the number of swap operations defined in line 4 of the pseudocode.
Input
The first line of the input includes an integer
N
, the number of elements in the sequence.
In the second line,
N
elements of the sequence are given separated by spaces characters.
Output
The output consists of 2 lines.
In the first line, please print the sorted sequence. Two contiguous elements of the sequence should be separated by a space character.
In the second line, please print the number of swap operations.
Constraints
1 ≤
N
≤ 100
Sample Input 1
5
5 3 2 4 1
Sample Output 1
1 2 3 4 5
8
Sample Input 2
6
5 2 4 6 1 3
Sample Output 2
1 2 3 4 5 6
9
Problem Name: Tree Walk
Problem Description: Binary trees are defined recursively. A binary tree T is a structure defined on a finite set of nodes that either
contains no nodes, or
is composed of three disjoint sets of nodes:
- a root node.
- a binary tree called its left subtree.
- a binary tree called its right subtree.
Your task is to write a program which perform tree walks (systematically traverse all nodes in a tree) based on the following algorithms:
Print the root, the left subtree and right subtree (preorder).
Print the left subtree, the root and right subtree (inorder).
Print the left subtree, right subtree and the root (postorder).
Here, the given binary tree consists of
n
nodes and evey node has a unique ID from 0 to
n
-1.
Input
The first line of the input includes an integer
n
, the number of nodes of the tree.
In the next
n
linen, the information of each node is given in the following format:
id left right
id
is the node ID,
left
is ID of the left child and
right
is ID of the right child. If the node does not have the left (right) child, the
left
(
right
) is indicated by
-1
Output
In the 1st line, print "
Preorder
", and in the 2nd line print a list of node IDs obtained by the preorder tree walk.
In the 3rd line, print "
Inorder
", and in the 4th line print a list of node IDs obtained by the inorder tree walk.
In the 5th line, print "
Postorder
", and in the 6th line print a list of node IDs obtained by the postorder tree walk.
Print a space character before each node ID.
Constraints
1 ≤
n
≤ 25
Sample Input 1
9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1
Sample Output 1
Preorder
 0 1 2 3 4 5 6 7 8
Inorder
 2 1 3 0 6 5 7 4 8
Postorder
 2 3 1 6 7 5 8 4 0
Reference
Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.
Problem Name: Projection
Problem Description: For given three points p1, p2, p, find the projection point x of p onto p1p2.
Input
x
p1
y
p1
x
p2
y
p2
q
x
p
0
y
p
0
x
p
1
y
p
1
...
x
p
q−1
y
p
q−1
In the first line, integer coordinates of
p1
and
p2
are given. Then,
q
queries are given for integer coordinates of
p
.
Output
For each query, print the coordinate of the projection point
x
. The output values should be in a decimal fraction with an error less than 0.00000001.
Constraints
1 ≤ q ≤ 1000
-10000 ≤ x
i
, y
i
≤ 10000
p1
and
p2
are not identical.
Sample Input 1
0 0 2 0
3
-1 1
0 1
1 1
Sample Output 1
-1.0000000000 0.0000000000
0.0000000000 0.0000000000
1.0000000000 0.0000000000
Sample Input 2
0 0 3 4
1
2 5
Sample Output 2
3.1200000000 4.1600000000
Problem Name: Sliding Minimum Element
Problem Description: For a given array $a_1, a_2, a_3, ... , a_N$ of $N$ elements and an integer $L$, find the minimum of each possible sub-arrays with size $L$ and print them from the beginning. For example, for an array $\{1, 7, 7, 4, 8, 1, 6\}$ and $L = 3$, the possible sub-arrays with size $L = 3$ includes $\{1, 7, 7\}$, $\{7, 7, 4\}$, $\{7, 4, 8\}$, $\{4, 8, 1\}$, $\{8, 1, 6\}$ and the minimum of each sub-array is 1, 4, 4, 1, 1 respectively.
Constraints
$1 \leq N \leq 10^6$
$1 \leq L \leq 10^6$
$1 \leq a_i \leq 10^9$
$L \leq N$
Input
The input is given in the following format.
$N$ $L$
$a_1$ $a_2$ ... $a_N$
Output
Print a sequence of the minimum in a line. Print a space character between adjacent elements.
Sample Input 1
7 3
1 7 7 4 8 1 6
Sample Output 1
1 4 4 1 1
Problem Name: All Pairs Shortest Path
Input
Problem Description: An edge-weighted graph G (V, E).
|
V
| |
E
|
s
0
t
0
d
0
s
1
t
1
d
1
:
s
|E|-1
t
|E|-1
d
|E|-1
|V|
is the number of vertices and
|E|
is the number of edges in
G
. The graph vertices are named with the numbers 0, 1,...,
|V|-1
respectively.
s
i
and
t
i
represent source and target vertices of
i
-th edge (directed) and
d
i
represents the cost of the
i
-th edge.
Output
If the graph contains a negative cycle (a cycle whose sum of edge costs is a negative value), print
NEGATIVE CYCLE
in a line.
Otherwise, print
D
0,0
D
0,1
...
D
0,|V|-1
D
1,0
D
1,1
...
D
1,|V|-1
:
D
|V|-1,0
D
1,1
...
D
|V|-1,|V|-1
The output consists of
|V|
lines. For each
i
th line, print the cost of the shortest path from vertex
i
to each vertex
j
(
j = 0, 1, ... |V|-1
) respectively. If there is no path from vertex
i
to vertex
j
, print "
INF
". Print a space between the costs.
Constraints
1 ≤
|V|
≤ 100
0 ≤
|E|
≤ 9900
-2 &times 10
7
≤
d
i
≤ 2 &times 10
7
There are no parallel edges
There are no self-loops
Sample Input 1
4 6
0 1 1
0 2 5
1 2 2
1 3 4
2 3 1
3 2 7
Sample Output 1
0 1 3 4
INF 0 2 3
INF INF 0 1
INF INF 7 0
Sample Input 2
4 6
0 1 1
0 2 -5
1 2 2
1 3 4
2 3 1
3 2 7
Sample Output 2
0 1 -5 -4
INF 0 2 3
INF INF 0 1
INF INF 7 0
Sample Input 3
4 6
0 1 1
0 2 5
1 2 2
1 3 4
2 3 1
3 2 -7
Sample Output 3
NEGATIVE CYCLE
Problem Name: LCA: Lowest Common Ancestor
Problem Description: For a rooted tree, find the lowest common ancestor of two nodes u and v.
The given tree consists of
n
nodes and every node has a unique ID from 0 to
n
-1 where 0 is the root.
Input
n
k
0
c
1
c
2
...
c
k
0
k
1
c
1
c
2
...
c
k
1
:
k
n-1
c
1
c
2
...
c
k
n-1
q
u
1
v
1
u
2
v
2
:
u
q
v
q
The first line of the input includes an integer
n
, the number of nodes of the tree.
In the next
n
lines, the information of node
i
is given.
k
i
is the number of children of node
i
, and
c
1
, ...
c
k
i
are node IDs of 1st, ...
k
th child of node
i
.
In the next line, the number of queryies
q
is given. In the next
q
lines, pairs of
u
and
v
are given as the queries.
Output
For each query, print the LCA of
u
and
v
in a line.
Constraints
1 ≤ n ≤ 100000
1 ≤ q ≤ 100000
Sample Input 1
8
3 1 2 3
2 4 5
0
0
0
2 6 7
0
0
4
4 6
4 7
4 3
5 2
Sample Output 1
1
1
0
0
Problem Name: X Cubic
Problem Description: Write a program which calculates the cube of a given integer x.
Input
An integer
x
is given in a line.
Output
Print the cube of
x
in a line.
Constraints
1 ≤
x
≤ 100
Sample Input 1
2
Sample Output 1
8
Sample Input 2
3
Sample Output 2
27