CodeEff/ECCO huggingface dataset:
Problem Name: Sorting Cards
Problem
Problem Description: There are 2n cards with numbers from 1 to 2n written on them, stacked in order from the top as 1, 2, 3, ..., 2n.
Sort these cards by using the following methods several times.
Cut with an integer k
After dividing the stack of cards from the top into a stack A of k cards and a stack B of the remaining cards, place stack B on top of stack A.
Riffle Shuffle
Divide the stack of cards from the top into two stacks, one of n cards from the top and the other of the remaining cards, so that the order becomes A1, B1, A2, B2, ..., An, Bn, and make it one stack.
Create a program that outputs the card numbers in order from the top after sorting the cards according to the instructions in the input file.
Input
The first line contains n (1 ≦ n ≦ 100), indicating that there are 2n cards.
The second line contains the number of operations m (1 ≦ m ≦ 1000).
The next m lines, from the third to the m+2th lines, specify the sorting method in order.
If k = 0, perform a Riffle Shuffle.
If 1 ≦ k ≦ 2n-1, perform a cut at k.
Output
The output consists of 2n lines. The first line contains the number of the top card after sorting, the second line contains the number of the second card from the top after sorting, and so on, with the i-th line containing the number of the i-th card from the top.
Examples
Example Input 1
2
2
1
0
Example Output 1
2
4
3
1
Example Input 2
3
4
2
4
0
0
Example Output 2
1
5
4
3
2
6
The above problem statement and test data for automatic judgment were created by the Information Olympiad Japan Committee and are publicly available.
Problem Name: Quality Inspection
Problem
Problem Description: You are responsible for quality control at a factory that produces a certain machine. This machine requires a power supply, a motor, and a cable as parts. There are a total of a power supplies, b motors, and c cables in the factory, each numbered from 1 to a, from a+1 to a+b, and from a+b+1 to a+b+c, respectively. Unfortunately, some of these parts might be defective. The factory wants to know which parts are defective and which parts are not.
To determine which parts are defective, the factory performs the following inspection: each power supply, motor, and cable is connected one at a time and the machine is operated. If all three parts are working properly, the machine will operate correctly and the inspection result is "pass". If at least one of the three parts is defective, the machine will not operate correctly and the inspection result is "fail". (The machines produced in the factory are very precise, so there is no chance that a machine will operate correctly despite having a defective part mixed in.)
You are given a list of inspection results. Each line of the list contains the numbers of the power supply, motor, and cable used in the inspection, as well as whether the inspection passed or failed.
Given the list of inspection results, write a program that classifies each part as definitely defective, definitely not defective, or indeterminate (i.e., it cannot be determined from the inspection results whether the part is defective or not).
Input
The input consists of multiple datasets, each in the following format. The input ends with a line containing three zeros.
The first line contains three integers a, b, and c, separated by spaces, representing the number of power supplies, motors, and cables, respectively.
The second line contains a single integer N, the number of inspections in the list.
Each of the following N lines represents an inspection. Each line contains four integers i, j, k, and r separated by a single space. The integers i, j, and k represent the numbers of the power supply, motor, and cable used in the inspection, respectively, and r is 1 if the inspection passed and 0 if it failed.
The values of a, b, c, and N satisfy 1 ≤ a, b, c ≤ 100 and 1 ≤ N ≤ 1000.
There are at most 5 datasets.
Output
For each dataset, output in the following format. The output consists of a+b+c lines.
For line i (1 ≤ i ≤ a+b+c):
If it is determined from the inspection results that part i is defective, output 0.
If it is determined from the inspection results that part i is not defective, output 1.
If it cannot be determined from the inspection results whether part i is defective or not, output 2.
Sample Input and Output
Sample Input
2 2 2
4
2 4 5 0
2 3 6 0
1 4 5 0
2 3 5 1
0 0 0
Sample Output
2
1
1
0
1
0
The problem statement and test data used by the automatic judging system for this problem were created and made available by the
Japanese Olympiad in Informatics
.
Problem Name: Route to School
Problem
Problem Description: JOI City, where Taro lives, has a grid-like structure with a total of a north-south roads and b east-west roads that run straight. The a north-south roads are numbered from 1 to a starting from the west, and the b east-west roads are numbered from 1 to b starting from the south. The intersection at which the i-th north-south road from the west and the j-th east-west road from the south intersect is denoted by (i, j).
Taro lives near the intersection (1, 1), and commutes to JOI High School near the intersection (a, b) by bicycle. The bicycle can only move along the roads. In order to shorten his commuting time, Taro moves only to the east or north.
Currently, there are n intersections (x
1
, y
1
), (x
2
, y
2
), ..., (x
n
, y
n
) where construction is being carried out in JOI City. Taro cannot pass through an intersection that is under construction.
How many routes are there for Taro to commute to school from intersection (1, 1) to intersection (a, b) while avoiding the intersections under construction, moving only to the east or north? Write a program to find the number of routes m of Taro's commuting route.
Input
The input consists of multiple datasets. Each dataset is given in the following format. The input will be terminated by a line containing two zeros.
The first line contains two integers a and b separated by a space, which represent the number of north-south roads and the number of east-west roads, respectively. a and b satisfy 1 ≤ a, b ≤ 16.
The second line contains an integer n, which represents the number of intersections under construction. n satisfies 1 ≤ n ≤ 40.
The following n lines (from the third line to the n+2-th line) indicate the positions of the intersections under construction. The i-th line contains two integers x
i
and y
i
separated by a space, which indicate that the intersection (x
i
, y
i
) is under construction. x
i
and y
i
satisfy 1 ≤ x
i
, y
i
≤ 16.
The number of datasets does not exceed 5.
Output
For each dataset, output the number of Taro's commuting routes m on one line.
Sample Input
5 4
3
2 2
2 3
4 2
5 4
3
2 2
2 3
4 2
0 0
Sample Output
5
5
The figure below shows the case of a = 5, b = 4, and n = 3, where the intersections under construction are (2,2), (2,3), and (4,2).
In this case, there are m=5 commuting routes for Taro. When all 5 commuting routes are drawn, they are as follows:
The problem statement and test cases are based on problems provided by the
Information-technology Promotion Agency (IPA)
of Japan.
Problem Name: Maximum Sum
Problem
Problem Description: Given a sequence a1, a2, ..., an of n integers and a positive integer k (1 ≤ k ≤ n), find the maximum sum of a contiguous subsequence of k integers in the sequence. In other words, find the maximum value of Si = ai + ai+1 + ... + ai+k-1 for all 1 ≤ i ≤ n - k + 1.
Input
The input consists of multiple datasets. Each dataset is given in the following format, and the input ends with two zeros on a line.
The first line of each dataset contains two integers
n
(1 ≤
n
≤ 100000) and
k
(1 ≤
k
≤
n
), separated by a space. The
i
-th line of the next
n
lines contains the integer
a
i
(-10000 ≤
a
i
≤ 10000), which is the
i
-th element of the sequence.
Of the test cases for scoring, 60% satisfy
n
≤ 5000 and
k
≤ 1000.
There are no more than 5 datasets.
Output
For each dataset, output a single integer, which is the maximum value of
S
i
for all 1 ≤
i
≤
n
-
k
+ 1.
Sample Input and Output
Sample Input
5 3
2
5
-4
10
3
0 0
Sample Output
11
The problem statement and test data used for automatic judging are provided by
the Japan Committee for the International Olympiad in Informatics
.
Problem Name: Longest Staircase
Problem
Problem Description: There are n cards, each with an integer from 1 to n written on it, and one blank card. Among the n+1 cards, k cards are given, where 1 ≤ k ≤ n. The blank card can be filled in with an integer from 1 to n. We want to create the longest possible sequence of consecutive integers using only the given cards.
Write a program that, given the given cards, outputs the maximum length of a consecutive integer sequence that can be created using those cards.
Example 1
Let
n
= 7 and
k
= 5. Suppose we are given the cards 6, 2, 4, 7, and 1. The longest consecutive integer sequence that can be formed using these cards is 1, 2, which has a length of 2.
Example 2
Let
n
= 7 and
k
= 5. Suppose we are given the cards 6, 2, 4, 7, and a blank card. The longest consecutive integer sequence that can be formed using these cards is 4, 5, 6, 7, which can be created by writing 5 on the blank card. This sequence has a length of 4.
Input
The input consists of multiple datasets. Each dataset is given in the following format. The input ends with two zeroes.
The first line contains two integers
n
(1 ≤
n
≤ 100000) and
k
(1 ≤
k
≤
n
) separated by a single space. The next
k
lines each contain one integer, which represents the integer written on one of the given cards. A blank card is represented by 0.
40% of the test cases have 1 ≤
n
≤ 1000 and 1 ≤
k
≤ 500, 20% of the test cases have 1 ≤
n
≤ 60000 and 1 ≤
k
≤ 50000, and 40% of the test cases have 1 ≤
n
≤ 100000 and 1 ≤
k
≤ 100000.
There are no more than 5 datasets.
Output
For each dataset, output the maximum length of a consecutive integer sequence that can be created using the given cards on a single line.
Sample Input and Output
Input
7 5
6
2
4
7
1
7 5
6
2
0
4
7
0 0
Output
2
4
The above problem statement and test data used by the automatic judge are problems and test data created and released by the
Japanese Information Olympiad Committee
.
Problem Name: The Oldest Site
Problem
Problem Description: In the past, there was a village where many people lived. People built buildings of various shapes and sizes. However, those buildings are already lost, and only documents and pillars found in the ruins were a clue to the location of the buildings.
There is a description of the temple in the document. The temple is a square when viewed from above, and there were pillars at the four corners. It is not known which direction the temple was facing. Also, it is not known whether there were pillars on the sides or inside. Archaeologists believed that among the pillars found in the ruins, the one with the largest area that is square must be the temple.
Given the coordinates of the pillars, write a program that finds the square made up of four pillars with the largest area and outputs its area. Note that the sides of the square are not necessarily parallel to the coordinate axis.
Example
In the example of the figure below, there are ten pillars, and the four at coordinates (4, 2), (5, 2), (5, 3), and (4, 3) make a square, and the four at coordinates (1, 1), (4, 0), (5, 3), and (2, 4) also make a square. The latter square has the largest area of 10.
Input
The input consists of multiple datasets. Each dataset is given in the following format. The input is terminated by a line containing a single zero.
The first line contains the number of pillars n found in the ruins.
From the second line to the n + 1-th line, each of the n lines contains the x and y coordinates of a pillar separated by a space.
Each pillar appears only once or never.
n is an integer satisfying 1 ≤ n ≤ 3000, and the x and y coordinates of the pillars are integers between 0 and 5000 inclusive.
30% of the score is for datasets where 1 ≤   n ≤ 100, and 60% of the score is for datasets where 1 ≤ n ≤ 500.
There are no more than 10 datasets.
Output
For each dataset, output one integer. If there is a square made up of four pillars, output the area of the largest such square, and if there is no such square, output 0.
Sample Input
10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2
10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2
0
Sample Output
10
10
The problem statement and test data used in the automated judge are provided by
Information-technology Promotion Agency
, Japan.
Problem Name: Change
Problem
Problem Description: Taro often shops at JOI Miscellaneous Goods Store. The store has enough coins of 500 yen, 100 yen, 50 yen, 10 yen, 5 yen, and 1 yen, and always pays the change in such a way that the number of coins is the smallest. Write a program that calculates the number of coins included in the change when Taro shops at JOI Miscellaneous Goods Store and pays with a 1000 yen bill.
For example, in the case of input example 1, 4 should be output as shown in the figure below.
Input
The input consists of multiple datasets. Each dataset consists of a single line, which contains the amount of money that Taro will pay (an integer between 1 and 999). The input data ends with a single 0 line.
The number of datasets is no more than 5.
Output
For each dataset, output the number of coins included in the change in one line.
Input/Output Examples
Input Example
380
1
0
Output Example
4
15
The problem statement and test data used in the automatic judgment are the problem statement and test data created and disclosed by the
Japan Information Olympiad Committee
.
Problem Name: Constellation
Problem
Problem Description: You are searching for a constellation from a photo of the night sky. The photo always includes exactly one figure of the same shape, orientation, and size as the constellation you are looking for. However, the photo may contain extra stars that are not part of the constellation.
For example, the constellation in Figure 1 is included in the photo in Figure 2 (indicated by the enclosed circle). When the coordinates of the stars in the given constellation are moved parallel to the x-axis by 2 and parallel to the y-axis by −3, they match the position in the photo.
Write a program that, given the shape of the constellation you are looking for and the positions of the stars in the photo, finds the amount by which to move the constellation in order to match the positions in the photo.
Figure 1: Constellation you are looking for
Figure 2: Photo of the night sky
Input
The input consists of multiple datasets. Each dataset is given in the following format.
The first line of the input contains the number of stars
m
that make up the constellation you are looking for. The following
m
lines contain integers separated by a space that indicate the x and y coordinates of the
m
stars that make up the constellation you are looking for. The (
m
+2)-th line contains the number of stars
n
in the photo. The following
n
lines contain integers separated by a space that indicate the x and y coordinates of the
n
stars in the photo.
All
m
stars that make up the constellation are at different positions. All
n
stars in the photo are at different positions. 1 ≤
m
≤ 200, 1 ≤
n
≤ 1000. The x and y coordinates of the stars are all between 0 and 1000000.
If
m
is 0, it indicates the end of the input. There will be no more than 5 datasets.
Output
For each dataset, write a single line of output consisting of two integers separated by a space. The first integer indicates the amount by which to move the constellation parallel to the x-axis, and the second integer indicates the amount by which to move the constellation parallel to the y-axis in order to match the positions in the photo.
Sample Input
5
8 5
6 4
4 3
7 10
0 10
10
10 5
2 7
9 7
8 10
10 2
1 2
8 1
6 7
6 0
0 9
5
904207 809784
845370 244806
499091 59863
638406 182509
435076 362268
10
757559 866424
114810 239537
519926 989458
461089 424480
674361 448440
81851 150384
459107 795405
299682 6700
254125 362183
50795 541942
0
Sample Output
2 -3
-384281 179674
Sample Input 1 corresponds to the figure above.
The problem statement and test data are provided by
the Information Olympiad Japan Committee
.
Problem Name: Go Stones Arrangement
Problem
Problem Description: Play by arranging white and black Go stones on a table. First, place a Go stone on the left end of the table. Next, place a Go stone in the second position from the left. Repeat this n times to arrange n Go stones in a row. However, when placing a new i-th Go stone, replace the Go stones on the table according to the following rules.
If i is odd: Do not replace the Go stone placed on the table, and place a new Go stone in the i-th position from the left.
If i is even: If the color of the Go stone placed in i-th position from the left is the same as the color of the Go stone on the right end of the table, do not replace the Go stone on the table and place a new Go stone in the i-th position from the left. Otherwise, if the color of the new Go stone placed in the i-th position from the left is different from the color of the Go stone on the right end of the table, remove all the continuous Go stones of the same color on the right end of the table and replace them with the same color Go stone as the i-th Go stone. Then, place the i-th Go stone at the right end of the table.
For example, suppose the Go stones are arranged as follows after placing the first seven Go stones,
○○●●○○○
(where ○ represents a white Go stone and ● represents a black Go stone.)
If the eighth Go stone is white (○), it is the same color as the right end Go stone, so it is placed as it is. Therefore, the Go stones on the table are
○○●●○○○○
If the eighth Go stone is black (●), the color is different from the right end Go stone (○), so first remove the three continuous white Go stones (○) at the right end of the table and replace them with black Go stone (●). Then place the eighth Go stone at the right end of the table. Therefore, the Go stones on the table are
○○●●●●●●
Create a program that, given the order in which the Go stones are placed as input, finds the number of white Go stones on the table after n Go stones have been arranged.
Input
The input consists of multiple data sets. Each data set is given in the following format.
The first line contains a positive integer n (1 ≤ n ≤ 100000). The i + 1-th line (1 ≤ i ≤ n) after the second line contains an integer c
i
representing the color of the Go stone to be placed in the i-th position, with 0 indicating that the color of the Go stone to be placed in the i-th position is white and 1 indicating that the color of the Go stone to be placed in the i-th position is black.
For 50% of test cases, n ≤ 10000.
When n is 0, it indicates the end of the input. The number of data sets is no more than 10.
Output
The output should contain a single integer on a line for each data set, indicating the number of white Go stones on the table after n Go stones have been arranged.
Example Input/Output
Sample Input
8
1
0
1
1
0
0
0
0
8
1
0
1
1
0
0
0
1
0
Sample Output
6
2
The problem statement above and the test data used by the automatic judge are provided by the Information-technology Promotion Agency, Japan (IPA).
Problem Name: Darts
Problem
Problem Description: You are going to play a dart game with the following rules.
You can throw up to 4 darts at the target. You do not have to throw all 4 darts, and it is okay not to throw any darts. The target is divided into N sections, and each section has a score written on it, P
1
, ..., P
N
. The sum of the scores where the darts hit, S, is the basis of your score. If S is less than or equal to a certain score M that has been predetermined, then S is your score. However, if S exceeds M, your score is 0.
Given the scores written on the target and the value of M, create a program that calculates the maximum score you can obtain.
Input
The input consists of multiple data sets in the following format:
The first line contains two integers N (1 ≤ N ≤ 1000) and M (1 ≤ M ≤ 200000000 = 2 × 10
8
). On the i-th line (1 ≤ i ≤ N) after the second line, P
i
(1 ≤ P
i
≤ 100000000 = 10
8
) is written.
Among the test data for grading, 20% of the points have N ≤ 100, and 50% of the points have N ≤ 300.
The end of the input is indicated by N = M = 0. There are no more than 10 data sets.
Output
For each data set, output the maximum score you can obtain on one line.
Sample Input
4 50
3
14
15
9
3 21
16
11
2
0 0
Sample Output
48
20
In the first example, your score is maximized when three darts hit the 15-point section and one dart hits the 3-point section, resulting in a score of 48 points.

In the second example, your score is maximized when one dart hits the 16-point section and two darts hit the 2-point section, resulting in a score of 20 points.
The original problem statement and test data for the automatic judge were provided by the
Japanese Olympiad in Informatics Committee
.
Problem Name: Paint Colors
Problem
Problem Description: For the promotion of the Information Olympiad (IOI), we want to create a signboard by painting a rectangular plywood board. We plan to use a different color for each region separated by masking tape applied in advance to the plywood board where we do not want to paint. For example, in the case of Figure 5-1, we use 5 colors of paint.
Write a program that, given the position where the masking tape is applied as input, determines the number of colors of paint used. However, the entire plywood board is not covered with masking tape, and all the edges of the masking tape are parallel to the edges of the plywood board.
Input
Multiple datasets are given as input. Each dataset is given in the following format.
On the first line, the width w (an integer satisfying 1 ≤ w ≤ 1000000) and the height h (an integer satisfying 1 ≤ h ≤ 1000000) of the plywood board are written in this order, separated by a space.
On the second line, the number of masking tapes n (an integer satisfying 1 ≤ n ≤ 1000) is written.
From the 3rd line onwards, for each i-th masking tape to be pasted, the coordinates of the lower-left corner (x
1
, y
1
) and the upper-right corner (x
2
, y
2
) are written in order, separated by a space.
However, the coordinate of the lower-left corner of the plywood board is (0,0), and that of the upper-right corner is (w,h). Of the grading data, 30% of the points require w ≤ 100, h ≤ 100, and n ≤ 100.
The input ends when both h and w are 0. The number of datasets is less than or equal to 20.
Output
For each dataset, output the number of colors of paint used on a single line.
Sample Input and Output
The following is the case of Figure 5-1.
Input Example
15 6
10
1 4 5 6
2 1 4 5
1 0 5 1
6 1 7 5
7 5 9 6
7 0 9 2
9 1 10 5
11 0 14 1
12 1 13 5
11 5 14 6
0 0
Output Example
5
The problem statement and the test data used for the automatic judgment are provided by the
Japan Committee for the International Olympiad in Informatics
.
Problem Name: Skating on Thin Ice
Problem
Problem Description: JOI Taro wants to play by breaking the thin ice on a square-shaped plaza, consisting of m rows and n columns. Some sections of the plaza have thin ice, while others have no ice. JOI Taro can begin breaking ice from any section on which there is ice. He can move