CodeEff/ECCO huggingface dataset:
Integral Rectangles
Problem Description: Let us consider rectangles whose height, h, and
width, w, are both integers. We call such rectangles 
integral rectangles. In this problem, we consider only wide
integral rectangles, i.e., those with w > h.
We define the following ordering of wide integral rectangles. Given
two wide integral rectangles,
The one shorter in its diagonal line is smaller, and
If the two have diagonal lines with the same length, the one shorter
 in its height is smaller.
Given a wide integral rectangle, find the smallest wide integral
rectangle bigger than the given one.
Input
The entire input consists of multiple datasets. The number of
 datasets is no more than 100. Each dataset describes a wide integral
 rectangle by specifying its height and width, namely
h
and
w
, separated by a space in a line, as follows.
h
w
For each dataset,
h
and
w
(>
h
) are both
integers greater than 0 and no more than 100.
The end of the input is indicated by a line of two zeros separated by a space.
Output
For each dataset, print in a line two numbers describing the
height and width, namely
h
and
w
(>
h
), of the
smallest wide integral rectangle bigger than the one described in the
dataset.  Put a space between the numbers. No other
characters are allowed in the output.
For any wide integral rectangle given in the input, the width and
height of the smallest wide integral rectangle bigger than the given
one are both known to be not greater than 150.
In addition, although
the ordering of wide integral rectangles uses the comparison of
lengths of diagonal lines, this comparison can be replaced with that
of squares (self-products) of lengths of diagonal lines, which can
avoid unnecessary troubles possibly caused by the use of floating-point
numbers.
Sample Input
1 2
1 3
2 3
1 4
2 4
5 6
1 8
4 7
98 100
99 100
0 0
Output for the Sample Input
1 3
2 3
1 4
2 4
3 4
1 8
4 7
2 8
3 140
89 109
Tax Rate Changed
Problem Description: VAT (value-added tax) is a tax imposed at a certain rate proportional to the sale price.
Our store uses the following rules to calculate the after-tax prices.
When the VAT rate is
x
%,
	for an item with the before-tax price of
p
yen,
	its after-tax price of the item is
p
(100+
x
) / 100 yen, fractions rounded off.
The total after-tax price of multiple items paid at once is
	the sum of after-tax prices of the items.
The VAT rate is changed quite often.
    Our accountant has become aware that
    "different pairs of items that had the same total after-tax price
    may have different total after-tax prices after VAT rate changes."
    For example, when the VAT rate rises from 5% to 8%,
    a pair of items that had the total after-tax prices of 105 yen before
    can now have after-tax prices either of 107, 108, or 109 yen, as shown in the table below.
Before-tax prices of two items
After-tax price with 5% VAT
After-tax price with 8% VAT
20, 80
21 + 84 = 105
21 + 86 = 107
2, 99
2 + 103 = 105
2 + 106 = 108
13, 88
13 + 92 = 105
14 + 95 = 109
Our accountant is examining effects of VAT-rate changes on after-tax prices.
    You are asked to write a program that calculates the possible maximum
    total after-tax price of two items with the new VAT rate,
    knowing their total after-tax price before the VAT rate change.
Input
The input consists of multiple datasets.
    Each dataset is in one line,
    which consists of three integers
x
,
y
, and
s
separated by a space.
x
is the VAT rate in percent
before
the VAT-rate change,
y
is the VAT rate in percent
after
the VAT-rate change,
    and
s
is the sum of after-tax prices of two items
before
the VAT-rate change.
    For these integers, 0 <
x
< 100, 0 <
y
< 100,
    10 <
s
< 1000, and
x
≠
y
hold.
    For before-tax prices of items, all possibilities of 1 yen through
s
-1 yen should be considered.
The end of the input is specified by three zeros separated by a space.
Output
For each dataset,
    output in a line the possible maximum total after-tax price when the VAT rate is changed to
y
%.
Sample Input
5 8 105
8 5 105
1 2 24
99 98 24
12 13 26
1 22 23
1 13 201
13 16 112
2 24 50
1 82 61
1 84 125
1 99 999
99 1 999
98 99 999
1 99 11
99 1 12
0 0 0
Output for the Sample Input
109
103
24
24
26
27
225
116
62
111
230
1972
508
1004
20
7
Hints
In the following table,
    an instance of a before-tax price pair that has the maximum after-tax price after the VAT-rate change
    is given for each dataset of the sample input.
Dataset
Before-tax prices
After-tax price with
y
% VAT
5 8 105
13, 88
14 + 95 = 109
8 5 105
12, 87
12 + 91 = 103
1 2 24
1, 23
1 + 23 =  24
99 98 24
1, 12
1 + 23 =  24
12 13 26
1, 23
1 + 25 =  26
1 22 23
1, 22
1 + 26 =  27
1 13 201
1,199
1 +224 = 225
13 16 112
25, 75
29 + 87 = 116
2 24 50
25, 25
31 + 31 =  62
1 82 61
11, 50
20 + 91 = 111
1 84 125
50, 75
92 +138 = 230
1 99 999
92,899
183+1789 =1972
99 1 999
1,502
1 +507 = 508
98 99 999
5,500
9 +995 =1004
1 99 11
1, 10
1 + 19 =  20
99 1 12
1,  6
1 +  6 =   7
Bridge Removal
Problem Description: ICPC islands once had been a popular tourist destination.
For nature preservation, however, the government decided to prohibit entrance to the islands,
and to remove all the man-made structures there.
The hardest part of the project is to remove all the bridges connecting the islands.
There are
n
islands and
n
-1 bridges.
The bridges are built so that all the islands are reachable from all the other islands by
crossing one or more bridges.
The bridge removal team can choose any island as the starting point, and can repeat either of the
following steps.
Move to another island by crossing a bridge that is connected to the current island.
Remove one bridge that is connected to the current island, and stay at the same island after the removal.
Of course, a bridge, once removed, cannot be crossed in either direction.
Crossing or removing a bridge both takes time proportional to the length of the bridge.
Your task is to compute the shortest time necessary for removing all the bridges.
Note that the island where the team starts can differ from where the team finishes the work.
Input
The input consists of at most 100 datasets.
Each dataset is formatted as follows.
n
p
2
p
3
...
p
n
d
2
d
3
...
d
n
The first integer
n
(3 ≤
n
≤ 800) is the number of the islands.
The islands are numbered from 1 to
n
.
The second line contains
n
-1 island numbers
p
i
(1 ≤
p
i
<
i
), and tells that for each
i
from 2 to
n
the island
i
and the island
p
i
are connected by a bridge.
The third line contains
n
-1 integers
d
i
(1 ≤
d
i
≤ 100,000)
each denoting the length of the corresponding bridge.
That is, the length of the bridge connecting the island
i
and
p
i
is
d
i
. It takes
d
i
units of time to cross the bridge, and
also the same units of time to remove it.

Note that, with this input format, it is assured that all the islands are reachable each other by
crossing one or more bridges.
The input ends with a line with a single zero.
Output
For each dataset, print the minimum time units required to remove all the bridges in a single line.
Each line should not have any character other than this number.
Sample Input
4
1 2 3
10 20 30
10
1 2 2 1 5 5 1 8 8
10 1 1 20 1 1 30 1 1
3
1 1
1 1
0
Output for the Sample Input
80
136
2
Problem Name: Problem G: Concert Hall Scheduling
Problem Description: You are appointed director of a famous concert hall, to save it from bankruptcy. The hall is very
popular, and receives many requests to use its two fine rooms, but unfortunately the previous
director was not very efficient, and it has been losing money for many years. The two rooms are
of the same size and arrangement. Therefore, each applicant wishing to hold a concert asks for
a room without specifying which. Each room can be used for only one concert per day.
In order to make more money, you have decided to abandon the previous fixed price policy, and
rather let applicants specify the price they are ready to pay. Each application shall specify a
period [
i
,
j
] and an asking price
w
, where
i
and
j
are respectively the first and last days of the
period (1 ≤
i
≤
j
≤ 365), and
w
is a positive integer in yen, indicating the amount the applicant
is willing to pay to use a room for the whole period.
You have received applications for the next year, and you should now choose the applications
you will accept. Each application should be either accepted for its whole period or completely
rejected. Each concert should use the same room during the whole applied period.
Considering the dire economic situation of the concert hall, artistic quality is to be ignored,
and you should just try to maximize the total income for the whole year by accepting the most
profitable applications.
Input
The input has multiple data sets, each starting with a line consisting of a single integer n, the
number of applications in the data set. Then, it is followed by
n
lines, each of which represents
one application with a period [
i
,
j
] and an asking price
w
yen in the following format.
i j w
A line containing a single zero indicates the end of the input.
The maximum number of applications in a data set is one thousand, and the maximum asking
price is one million yen.
Output
For each data set, print a single line containing an integer, the maximum total income in yen
for the data set.
Sample Input
4
1 2 10
2 3 10
3 3 10
1 3 10
6
1 20 1000
3 25 10000
5 15 5000
22 300 5500
10 295 9000
7 7 6000
8
32 251 2261
123 281 1339
211 235 5641
162 217 7273
22 139 7851
194 198 9190
119 274 878
122 173 8640
0
Output for the Sample Input
30
25500
38595
Problem Name: Problem B: Prime Gap
Problem Description: The sequence of n - 1 consecutive composite numbers (positive integers that are not prime and
not equal to 1) lying between two successive prime numbers p and p + n is called a prime gap of length n. For example, (24, 25, 26, 27, 28) between 23 and 29 is a prime gap of length 6.
Your mission is to write a program to calculate, for a given positive integer
k
, the length of the prime gap that contains
k
. For convenience, the length is considered 0 in case no prime gap
contains
k
.
Input
The input is a sequence of lines each of which contains a single positive integer. Each positive
integer is greater than 1 and less than or equal to the 100000th prime number, which is 1299709.
The end of the input is indicated by a line containing a single zero.
Output
The output should be composed of lines each of which contains a single non-negative integer. It
is the length of the prime gap that contains the corresponding positive integer in the input if it
is a composite number, or 0 otherwise. No other characters should occur in the output.
Sample Input
10
11
27
2
492170
0
Output for the Sample Input
4
0
6
0
114
Problem Name: Problem C: Minimal Backgammon
Problem Description: Here is a very simple variation of the game backgammon, named “Minimal Backgammon”. The game is played by only one player, using only one of the dice and only one checker (the token used by the player).
The game board is a line of (
N
+ 1) squares labeled as 0 (the start) to
N
(the goal). At the beginning, the checker is placed on the start (square 0). The aim of the game is to bring the checker to the goal (square
N
). The checker proceeds as many squares as the roll of the dice. The dice generates six integers from 1 to 6 with equal probability.
The checker should not go beyond the goal. If the roll of the dice would bring the checker beyond the goal, the checker retreats from the goal as many squares as the excess. For example, if the checker is placed at the square (
N
- 3), the roll "5" brings the checker to the square (
N
- 2), because the excess beyond the goal is 2. At the next turn, the checker proceeds toward the goal
as usual.
Each square, except the start and the goal, may be given one of the following two special instructions.
Lose one turn (labeled "
L
" in Figure 2) If the checker stops here, you cannot move the checker in the next turn.
Go back to the start (labeled "
B
" in Figure 2)
If the checker stops here, the checker is brought back to the start.
Figure 2: An example game
Given a game board configuration (the size
N
, and the placement of the special instructions), you are requested to compute the probability with which the game succeeds within a given number of turns.
Input
The input consists of multiple datasets, each containing integers in the following format.
N T L B
Lose
1
...
Lose
L
Back
1
...
Back
B
N
is the index of the goal, which satisfies 5 ≤
N
≤ 100.
T
is the number of turns. You are requested to compute the probability of success within
T
turns.
T
satisfies 1 ≤
T
≤ 100.
L
is the number of squares marked “Lose one turn”, which satisfies 0 ≤
L
≤
N
- 1.
B
is the number of squares marked “Go back to the start”, which satisfies 0 ≤
B
≤
N
- 1. They are separated by a space.
Lose
i
's are the indexes of the squares marked “Lose one turn”, which satisfy 1 ≤
Lose
i
≤
N
- 1. All
Lose
i
's are distinct, and sorted in ascending order.
Back
i
's are the indexes of the squares marked “Go back to the start”, which satisfy 1 ≤
Back
i
≤
N
- 1. All
Back
i
's are distinct, and sorted in ascending order. No numbers occur both in
Lose
i
's and
Back
i
's.
The end of the input is indicated by a line containing four zeros separated by a space.
Output
For each dataset, you should answer the probability with which the game succeeds within the
given number of turns. The output should not contain an error greater than 0.00001.
Sample Input
6 1 0 0
7 1 0 0
7 2 0 0
6 6 1 1
2
5
7 10 0 6
1
2
3
4
5
6
0 0 0 0
Output for the Sample Input
0.166667
0.000000
0.166667
0.619642
0.000000
Problem Name: Problem H: Bug Hunt
Problem Description: In this problem, we consider a simple programming language that has only declarations of one-
dimensional integer arrays and assignment statements. The problem is to find a bug in the given
program.
The syntax of this language is given in BNF as follows:
where
<
new line
>
denotes a new line character (LF).
Characters used in a program are alphabetical letters, decimal digits,
=
,
[
,
]
and new line characters. No other characters appear in a program.
A declaration declares an array and specifies its length. Valid indices of an array of length
n
are integers between 0 and
n
- 1, inclusive. Note that the array names are case sensitive, i.e.
array
a
and array
A
are different arrays. The initial value of each element in the declared array is undefined.
For example, array
a
of length 10 and array
b
of length 5 are declared respectively as follows.
a[10]
b[5]
An expression evaluates to a non-negative integer. A
<
number
>
is interpreted as a decimal
integer. An
<
array_name
>
[<
expression
>]
evaluates to the value of the
<
expression
>
-th element of
the array. An assignment assigns the value denoted by the right hand side to the array element
specified by the left hand side.
Examples of assignments are as follows.
a[0]=3
a[1]=0
a[2]=a[a[1]]
a[a[0]]=a[1]
A program is executed from the first line, line by line. You can assume that an array is declared once and only once before any of its element is assigned or referred to.
Given a program, you are requested to find the following bugs.
An index of an array is invalid.
An array element that has not been assigned before is referred to in an assignment as an index of array or as the value to be assigned.
You can assume that other bugs, such as syntax errors, do not appear. You can also assume
that integers represented by
<
number
>
s are between 0 and 2
31
- 1 (= 2147483647), inclusive.
Input
The input consists of multiple datasets followed by a line which contains only a single '
.
' (period).
Each dataset consists of a program also followed by a line which contains only a single '
.
' (period).
A program does not exceed 1000 lines. Any line does not exceed 80 characters excluding a new
line character.
Output
For each program in the input, you should answer the line number of the assignment in which
the first bug appears. The line numbers start with 1 for each program. If the program does not
have a bug, you should answer zero. The output should not contain extra characters such as
spaces.
Sample Input
a[3]
a[0]=a[1]
.
x[1]
x[0]=x[0]
.
a[0]
a[0]=1
.
b[2]
b[0]=2
b[1]=b[b[0]]
b[0]=b[1]
.
g[2]
G[10]
g[0]=0
g[1]=G[0]
.
a[2147483647]
a[0]=1
B[2]
B[a[0]]=2
a[B[a[0]]]=3
a[2147483646]=a[2]
.
.
Output for the Sample Input
2
2
2
3
4
0
Problem Name: Problem A:  Ginkgo Numbers
Problem Description: We will define Ginkgo numbers and multiplication on Ginkgo numbers.
A
Ginkgo number
is a pair <
m
,
n
> where
m
and
n
are integers. For example, <1, 1>, <-2, 1> and <-3,-1> are Ginkgo numbers.
The multiplication on Ginkgo numbers is defined by <
m
,
n
> · <
x
,
y
> = <
mx
−
ny
,
my
+
nx
>. For example, <1, 1> · <-2, 1> = <-3,-1>.
A Ginkgo number <
m
,
n
> is called a divisor of a Ginkgo number <
p
,
q
> if there exists a Ginkgo number <
x
,
y
> such that <
m
,
n
> · <
x
,
y
> = <
p
,
q
>.
For any Ginkgo number <
m
,
n
>, Ginkgo numbers <1, 0>, <0, 1>, <-1, 0>, <0,-1>, <
m
,
n
>, <-
n
,
m
>, <-
m
,-
n
> and <
n
,-
m
> are divisors of <
m
,
n
>. If
m
2
+
n
2
> 1, these Ginkgo numbers are distinct. In other words, any Ginkgo number such that
m
2
+
n
2
> 1 has at least eight divisors.
A Ginkgo number <
m
,
n
> is called a prime if
m
2
+
n
2
> 1 and it has exactly eight divisors. Your mission is to check whether a given Ginkgo number is a prime or not.
The following two facts might be useful to check whether a Ginkgo number is a divisor of another Ginkgo number.
Suppose
m
2
+
n
2
> 0. Then, <
m
,
n
> is a divisor of <
p
,
q
> if and only if the integer
m
2
+
n
2
is a common divisor of
mp
+
nq
and
mq
−
np
.
If <
m
,
n
> · <
x
,
y
> = <
p
,
q
>, then (
m
2
+
n
2
)(
x
2
+
y
2
) =
p
2
+
q
2
.
Input
The first line of the input contains a single integer, which is the number of datasets.
The rest of the input is a sequence of datasets. Each dataset is a line containing two integers
m
and
n
, separated by a space. They designate the Ginkgo number <
m
,
n
>. You can assume 1 <
m
2
+
n
2
< 20000.
Output
For each dataset, output a character '
P
' in a line if the Ginkgo number is a prime. Output a character '
C
' in a line otherwise.
Sample Input
8
10 0
0 2
-3 0
4 2
0 -13
-4 1
-2 -1
3 -1
Output for the Sample Input
C
C
P
C
C
P
P
C
Problem Name: Problem F: Never Wait for Weights
Problem Description: In a laboratory, an assistant, Nathan Wada, is measuring weight differences between sample pieces pair by pair. He is using a balance because it can more precisely measure the weight difference between two samples than a spring scale when the samples have nearly the same weight.
He is occasionally asked the weight differences between pairs of samples. He can or cannot answer based on measurement results already obtained.
Since he is accumulating a massive amount of measurement data, it is now not easy for him to promptly tell the weight differences. Nathan asks you to develop a program that records measurement results and automatically tells the weight differences.
Input
The input consists of multiple datasets. The first line of a dataset contains two integers
N
and
M
.
N
denotes the number of sample pieces (2 ≤
N
≤ 100,000). Each sample is assigned a unique number from 1 to
N
as an identifier. The rest of the dataset consists of
M
lines (1 ≤
M
≤ 100,000), each of which corresponds to either a measurement result or an inquiry. They are given in chronological order.
A measurement result has the format,
!
a b w
which represents the sample piece numbered
b
is heavier than one numbered
a
by
w
micrograms (
a
≠
b
). That is,
w
=
w
b
−
w
a
, where
w
a
and
w
b
are the weights of
a
and
b
, respectively. Here,
w
is a non-negative integer not exceeding 1,000,000.
You may assume that all measurements are exact and consistent.
An inquiry has the format,
?
a b
which asks the weight difference between the sample pieces numbered
a
and
b
(
a
≠
b
).
The last dataset is followed by a line consisting of two zeros separated by a space.
Output
For each inquiry, ?
a
b
, print the weight difference in micrograms between the sample pieces numbered
a
and
b
,
w
b
−
w
a
, followed by a newline if the weight difference can be computed based on the measurement results prior to the inquiry. The difference can be zero, or negative as well as positive. You can assume that its absolute value is at most 1,000,000. If the difference cannot be computed based on the measurement results prior to the inquiry, print
UNKNOWN
followed by a newline.
Sample Input
2 2
! 1 2 1
? 1 2
2 2
! 1 2 1
? 2 1
4 7
! 1 2 100
? 2 3
! 2 3 100
? 2 3
? 1 3
! 4 3 150
? 4 1
0 0
Output for the Sample Input
1
-1
UNKNOWN
100
200
-50
Problem Name: Problem A: Equal Sum Sets
Problem Description: Let us consider sets of positive integers less than or equal to n. Note that all elements of a set are different. Also note that the order of elements doesn't matter, that is, both {3, 5, 9} and {5, 9, 3} mean the same set.
Specifying the number of set elements and their sum to be
k
and
s
, respectively, sets satisfying the conditions are limited. When
n
= 9,
k
= 3 and
s
= 23, {6, 8, 9} is the only such set. There may be more than one such set, in general, however. When
n
= 9,
k
= 3 and
s
= 22, both {5, 8, 9} and {6, 7, 9} are possible.
You have to write a program that calculates the number of the sets that satisfy the given conditions.
Input
The input consists of multiple datasets. The number of datasets does not exceed 100.
Each of the datasets has three integers
n
,
k
and
s
in one line, separated by a space. You may assume 1 ≤
n
≤ 20, 1 ≤
k
≤ 10 and 1 ≤
s
≤ 155.
The end of the input is indicated by a line containing three zeros.
Output
The output for each dataset should be a line containing a single integer that gives the number of the sets that satisfy the conditions. No other characters should appear in the output.
You can assume that the number of sets does not exceed 2
31
- 1.
Sample Input
9 3 23
9 3 22
10 3 28
16 10 107
20 8 102
20 10 105
20 10 155
3 4 3
4 2 11
0 0 0
Output for the Sample Input
1
2
0
20
1542
5448
1
0
0