CodeEff/ECCO huggingface dataset:
Problem Name: Shuffle
Problem
Problem Description: There are n cards with numbers from 1 to n written on them. First, the cards are stacked in order, with the top card being numbered 1, the second card from the top being numbered 2, ..., and the bottom card being numbered n.
The cards are rearranged by performing an operation called "Shuffle(x,y)" on the card stack (x and y are integers satisfying 1 ≤ x < y < n).
Shuffle(x,y)
Divide the n cards into three stacks: a stack A consisting of the first x cards from the top, a stack B consisting of the x+1th to the yth card, and a stack C consisting of the (y+1)th to the nth card. Then stack B is placed on top of stack A, and stack C is placed on top of the combined stack.
For example, if you perform "Shuffle(3,5)" on 9 cards arranged in order, the numbers on the 9 cards will be arranged in order from the top as follows: 6, 7, 8, 9, 4, 5, 1, 2, 3.
Write a program that, after m shuffles of "Shuffle(x1,y1)", "Shuffle(x2,y2)", ..., "Shuffle(xm,ym)" on the initial card stack, finds the number of cards numbered r or less in the cards from the pth to qth position from the top of the card stack.
Input
The input consists of multiple datasets. Each dataset is given in the following format.
Each input consists of m+3 lines. The first line contains the number of cards n (3 ≤ n ≤ 1000000000 = 10
9
). The second line contains an integer m representing the number of shuffles (1 ≤ m ≤ 5000). The third line contains three integers p, q, and r (1 ≤ p ≤ q ≤ n, 1 ≤ r ≤ n). The i+3-th line (1 ≤ i ≤ m) contains two integers xi and yi (1 ≤ xi < yi < n) separated by a space.
The input ends with n=0. The number of datasets is no more than 5.
Output
For each dataset, output the number of cards numbered r or less in the cards from the pth to qth position from the top of the card stack after m shuffles, on one line.
Sample Input and Output
Input Sample
9
1
3 7 4
3 5
12
3
3 8 5
3 8
2 5
6 10
0
Output Sample
2
3
For the first input example, the cards are rearranged as follows by "Shuffle(3,5)": 6, 7, 8, 9, 4, 5, 1, 2, 3. There are two cards numbered 4 or less in the cards from the 3rd to the 7th position from the top.
For the second input example, the cards are rearranged as follows by "Shuffle(3,8)", "Shuffle(2,5)", and "Shuffle(6,10)", respectively: 9, 10, 3, 11, 12, 4, 5, 6, 7, 8, 1, 2. There are three cards numbered 5 or less in the cards from the 3rd to the 8th position from the top.
The problem statement and the test data used in the automatic judgment are from the
Information-technology Promotion Agency, Japan (IPA)
.
Problem Name: Bingo
Problem
Problem Description: At a programming contest, it is customary to play bingo games at the social gathering after the competition. However, the bingo card used in this bingo game is a little special and is created according to the following conditions.
The bingo card is divided into N rows and N columns of squares, and one positive integer is written in each square. All of these integers are different.
The integers written in the squares are between 1 and M, inclusive.
The sum of N×N integers written on the bingo card is S.
When looking at any column, the integers are arranged in ascending order from top to bottom.
No integer in any square is smaller than any integer to the left of that square.
The following is an example of a bingo card when N = 5, M = 50, and S = 685.
For the social gathering, we want to create as many bingo cards as possible that satisfy the above conditions. However, you must not create the same card more than two times. Create a program that outputs the maximum number of bingo cards that can be created, divided by 100000 and the remainder is the answer.
Input
The input consists of multiple datasets. Each dataset is given in the following format.
The input consists of a single line containing three positive integers separated by a space: N (1 ≤ N ≤ 7), the upper limit of the integers written in the squares M (1 ≤ M ≤ 2000), and the sum of the integers written on the bingo card S (1 ≤ S ≤ 3000). Note that for any input data given, at least one bingo card that satisfies the conditions can be created.
When N, M, and S are all 0, it indicates the end of the input. The number of datasets is no more than 5.
Output
For each dataset, output the maximum number of bingo cards that can be created divided by 100000 and the remainder is the answer, on a single line.
Sample Input and Output
Input Sample
3 9 45
3 100 50
5 50 685
0 0 0
Output Sample
1
7
74501
For the third input example, the maximum number of bingo cards that can be created is 642499974501, so the remainder divided by 100000 is 74501.
The problem statement and test data used in the automatic judgment are problem statements and scoring test data created and published by the
Information-technology Promotion Agency (IPA), Japan
.
Problem Name: IOIOI
Problem
Problem Description: For an integer n (1 ≤ n), let Pn be the string obtained by alternating I and O starting with I and having n O's and n + 1 I's. Here, I and O are uppercase letters I and O, respectively.
P
1
IOI
P
2
IOIOI
P
3
IOIOIOI
.
.
.
P
n
IOIOIO ... OI
(
O
occurs
n
times)
Figure 1-1: String
P
n
in this problem
Given integers
n
and
s
, a string consisting of I's and O's, how many times does the string
P
n
appear in
s
? Here,
n
and
s
satisfy the following conditions:
n
and the length of
s
are integers between 1 and 1,000,000 inclusive.
m
satisfies 2
n
+ 1 ≤
m
.
Create a program to output the number of times that
P
n
appears within
s
.
Example
If
n
is 1 and
s
is
OOIOIOIOIIOII
, the string
P
1
is
IOI
. It appears in the four places shown in Figure 1-2. Therefore, the output is 4.
OO
IOI
OIOIIOII
OOIO
IOI
OIIOII
OOIOIO
IOI
IOII
OOIOIOIOI
IOI
I
Figure 1-2: Example when
n
is 1 and
s
is
OOIOIOIOIIOII
If
n
is 2 and
s
is
OOIOIOIOIIOII
, the string
P
2
is
IOIOI
. It appears in the two places shown in Figure 1-3. Therefore, the output is 2.
OO
IOIOI
OIIOII
OOIO
IOIOI
IOII
Figure 1-3: Example when
n
is 2 and
s
is
OOIOIOIOIIOII
Input
The input consists of multiple data sets. Each data set is given in the following format.
The first line contains an integer
n
(1 ≤
n
≤ 1,000,000).
The second line contains an integer
m
(1 ≤
m
≤ 1,000,000), which indicates the length of
s
.
The third line contains the string
s
, which consists of I's and O's.
The input ends with
n
= 0. The number of data sets does not exceed 10.
Output
For each data set, output one integer on a line that represents the number of times that the string
P
n
appears in the string
s
. If
P
n
does not appear in
s
, output 0.
Examples
Input Example
1
13
OOIOIOIOIIOII
2
13
OOIOIOIOIIOII
0
Output Example
4
2
The problem statement and test data used in the automatic judging are the problem statement and test data created and published by the
Japan Committee for the International Olympiad in Informatics
.
Problem Name: Amidakuji
Problem
Problem Description: You are playing Amidakuji with J. Amidakuji consists of n vertical bars and m horizontal bars. The vertical bar is numbered from 1 to n from the left, and the positive integer si is written at the bottom of the vertical bar i.
Figure 3-1 Example of Amidakuji (
n
= 4,
m
= 5,
s
1
= 20,
s
2
= 80,
s
3
= 100,
s
4
= 50)
The integer written at the bottom end of vertical bar
i
is the score when following a path from the top of vertical bar
i
in order and reaching the bottom. For example, in Figure 3-1, if you choose vertical bar 1, the score is 80 points, and if you choose vertical bar 2, the score is 100 points.
Figure 3-2 Example of path
J decided to choose k consecutive vertical bars from vertical bar 1 to vertical bar
k
. The sum of the scores when choosing these k vertical bars is J's score. However, you can select one horizontal bar in the Amidakuji and remove it from the Amidakuji (you don't have to remove it). If you remove a horizontal bar, the sum of the scores obtained by choosing k consecutive vertical bars from vertical bar 1 to vertical bar
k
in the Amidakuji after removal is J's score.
Write a program that takes the shape of Amidakuji and the number of consecutive vertical bars k chosen by J as input and outputs the minimum score of J.
Input
The input consists of multiple datasets. Each dataset has the following format.
The first line contains four integers
n
,
m
,
h
, and
k
separated by spaces.
n
(2 ≤
n
≤ 1000) is the number of vertical bars,
m
(1 ≤
m
≤ 100000) is the number of horizontal bars,
h
(2 ≤
h
≤ 1000) is the length of the vertical bar, and
k
(1 ≤
k
≤ n) is the number of consecutive vertical bars chosen by J.
The next
n
lines contain the scores written at the bottom of the vertical bars. The
i
+1-th line (1 ≤
i
≤
n
) contains a positive integer
s
i
. Also,
s
1
+
s
2
+ ... +
s
n
≤ 2000000000 = 2 × 10
9
.
The next
m
lines contain the positions of the horizontal bars. The i + n + 1-th line (1 ≤
i
≤
m
) contains two space-separated integers
a
i
and
b
i
(1 ≤
a
i
≤
n
- 1, 1 ≤
b
i
≤
h
- 1) that represent the position of horizontal bar i. Horizontal bar i connects vertical bars
a
i
and
a
i
+ 1 and is
b
i
units away
Problem Name: Authentication Level
Problem
Problem Description: Have you heard of Just Odd Inventions (JOI) Corporation? The company's business is to create "just odd inventions." JOI Corporation has two offices, each of which consists of square rooms arranged in a grid of the same size. There is a door with an authentication function for identification between all adjacent rooms. As JOI Corporation handles confidential information of various levels, a positive integer called the confidential level is set for each room, and it is impossible to enter the room unless the identification level specified for the identification card is equal to or greater than the confidential level specified for each room. The entrance and exit of each office is only an elevator hall, and the confidential level of the elevator hall room is the lowest, 1. If the authentication level for the office is 0, you cannot even enter the elevator hall.
JOI Corporation has decided to conduct tours of the company for the public, following a sudden proposal by the president. You need to determine the combination of authentication levels for identification cards to give to visitors. Visitors will always open the door when they find one that can be opened (it is also possible to visit the same room multiple times). Therefore, you do not want to set the identification level for visitors higher than necessary. However, in order to make the tour attractive, it is necessary to allow visitors to visit a total of R or more rooms in two offices, including the elevator hall. If the identification level is set too low, it may not be possible to meet this condition.
JOI Corporation has two
Problem Name: Commuting Route
Problem
Problem Description: In a certain city in Canada where JOI lives, it is divided into a grid pattern by w straight roads running north and south, and h straight roads running east and west.
The w north-south roads are numbered 1, 2, ..., w in order from west to east. Similarly, the h east-west roads are numbered 1, 2, ..., h in order from south to north. An intersection where the i-th north-south road from the west and the j-th east-west road from the south intersect is represented by (i, j).
JOI lives near the intersection (1, 1) and commutes to a company near the intersection (w, h) by car. The car can only move along the roads. In order to shorten the commuting time, JOI moves only to the north or east. In this city, the following traffic rules have been established to reduce traffic accidents:
A car that turns at an intersection cannot turn at the next intersection immediately thereafter.
That is, it is not allowed to turn one block after turning at an intersection. In this case, how many commuting routes can JOI consider?
Create a program that outputs the remainder obtained by dividing the number of JOI's commuting routes by 100000 when w and h are given.
Input
The input consists of multiple datasets. Each dataset consists of one line containing two integers separated by a space, w and h (2 ≤ w ≤ 100, 2 ≤ h ≤ 100). w represents the number of north-south roads, and h represents the number of east-west roads.
When both w and h are 0, it indicates the end of the input. The number of datasets does not exceed 5.
Output
For each dataset, output the number of JOI's commuting routes divided by 100000 on one line.
Sample Input and Output
Sample Input
3 4
15 15
0 0
Sample Output
5
43688
JOI's commuting route in the first input example (5 routes)
In the first input example, JOI's commuting route can be considered in 5 ways as shown in the figure. Therefore, output 5.
In the second input example, JOI's commuting route can be considered in 143688 ways. Therefore, output 43688, which is the remainder obtained by dividing 143688 by 100000.
The problem statement and the test data used in the automatic judgment are a problem statement and a test data for scoring created and released by the
Japan Committee for the International Olympiad in Informatics
.
Problem Name: Traveler
Problem
Problem Description: You are a traveler traveling on the JOI Road. The JOI Road is a straight road that extends east and west, and there are n post towns on the JOI Road. The post towns are numbered from 1 to n in order from west to east. The westernmost post town on the JOI Road is post town 1, and the easternmost post town is post town n.
You are going to take a trip for m days starting from post town 1. Your itinerary is determined by the sequence a1, a2, ..., am, and ai is a non-zero integer that represents the method of transportation on the i-th day. If you assume that you are at post town k on the i-th day, ai means that you will move straight from post town k to post town k+ai.
Given the number n of post towns, the number m of days of travel, the distance between post towns, and the sequence a1, a2, ..., am that represents the method of transportation, create a program that calculates the remainder when the sum of your travel distance over m days is divided by 100000 = 10^5.
Figure corresponding to the input/output example
Input
The first line contains two integers n and m separated by a space. n (2 ≤ n ≤ 100000 = 10^5) is the number of post towns on the JOI Road, and m (1 ≤ m ≤ 100000 = 10^5) is the number of days of travel.
The following n-1 lines represent the distance between post towns on the JOI Road. The i+1-th line (1 ≤ i ≤ n-1) contains a positive integer si (1 ≤ si ≤ 100) that represents the distance between post town i and post town i+1.
The next m lines represent the sequence that represents the method of transportation for m days. The i+n-th line (1 ≤ i ≤ m) contains a non-zero integer ai that represents the method of transportation on the i-th day.
In the test data used for scoring, you will not move west of post town 1 or east of post town n.
In 50% of the test data used for scoring, n ≤ 100 and m ≤ 100.
Output
The output consists of one line containing the remainder obtained when the sum of your travel distance over m days is divided by 100000 = 10^5.
Input/Output Examples
Sample Input 1
7 5
2
1
1
3
2
1
2
-1
3
2
-3
Sample Output 1
18
On the first day, you move from post town 1 to post town 3. On the second day, you move from post town 3 to post town 2. Then, on the third day, you move from post town 2 to post town 5, on the fourth day, you move from post town 5 to post town 7, and on the fifth day, you move from post town 7 to post town 4. The total distance traveled in the five days of travel is 18.
The above problem statement and test data used in the automatic judge are provided by the
Information-technology Promotion Agency (IPA)
, Japan.
Problem Name: Tile
Problem
Problem Description: At JOI high school, they are going to make a wall painting using 1x1 square tiles of three colors: red, blue, and yellow. The painting is an N x N square, and the design is as follows: first, paste red tiles around the outermost frame, then paste blue tiles around the inner frame, then paste yellow tiles around the innermost frame. Repeat this until the entire N x N square is filled. The colors of the tiles used are red, blue, yellow, red, blue, yellow, and so on, in that order from the outermost frame.
One day, as the cultural festival drew near, it was discovered that K tiles had come off the wall painting. Therefore, they decided to purchase new tiles and paste them over the areas where the tiles had come off.
Write a program that takes as input the length of one side of the wall painting N, the number of tiles K that have come off, and the positions of the K tiles that have come off, and outputs the colors of the tiles that have come off.
For example, for N=11, the design of the 11 x 11 wall painting is shown below.
Also, for N=16, the design of the 16 x 16 wall painting is shown below.
Input
The input consists of 2+K lines. The first line specifies the length of one side of the wall painting N (1 ≤ N ≤ 1000000000 = 10^9), and the second line specifies the number of tiles K that have come off (1 ≤ K ≤ 1000). The i-th line after the second line (1 ≤ i ≤ K) contains two integers ai and bi (1 ≤ ai ≤ N, 1 ≤ bi ≤ N) separated by a space, indicating that the i-th tile that has come off is in the ai-th column and the bi-th row from the top.
The same tile will not appear more than once in the input from the third line to the (2+K)-th line. In 40% of the input data, N ≤ 1000 holds.
Output
The output consists of K lines. Each line contains a single integer, with the i-th integer (1 ≤ i ≤ K) indicating whether the i-th tile that came off was red (1), blue (2), or yellow (3).
Input/Output Examples
Sample Input 1
11
4
5 2
9 7
4 4
3 9
Sample Output 1
2
3
1
3
Sample Input 2
16
7
3 7
5 2
11 6
15 2
9 7
8 12
15 16
Sample Output 2
3
2
3
2
1
2
1
The problem statement and test data used in the automatic judge are provided by the
Japan Olympiad in Informatics Organizing Committee
.
Problem Name: Cheese
Problem
Problem Description: The cheese factory in JOI town has started production of cheese again this year, and the mice have come out of their nests. JOI town is divided into blocks in the north, south, east, and west, each of which is either a nest, a cheese factory, an obstacle, or an empty lot. The mouse visits all the cheese factories starting from its nest and eats one piece of cheese at a time.
There are N cheese factories in this town, and each factory produces only one type of cheese. The hardness of the cheese varies depending on the factory, and there is exactly one factory that produces cheese with a hardness of 1 to N.
The mouse's initial strength is 1, and its strength increases by 1 for each piece of cheese it eats. However, the mouse cannot eat cheese that is harder than its own strength.
The mouse can move one block to the east, west, north, or south in 1 minute, but cannot enter a block with an obstacle. It is also possible for the mouse to pass by a cheese factory without eating cheese. Write a program to find the shortest time it takes for the mouse to eat all the cheese. However, you can ignore the time it takes for the mouse to eat the cheese.
Input
There are H+1 lines of input. The first line contains three integers H, W, and N (1 ≤ H ≤ 1000, 1 ≤ W ≤ 1000, 1 ≤ N ≤ 9) separated by spaces in this order. From the second to the H+1th lines, a string of W characters consisting of 'S', '1', '2', ..., '9', 'X', and '.' is written, describing the state of each block. Let (i,j) denote the i-th row and j-th column from the west, then the j-th character of the i+1th line describes the state of block (i,j). If block (i,j) is a nest, the character is 'S', if it is an obstacle, the character is 'X', if it is an empty lot, the character is '.', and if it is a cheese factory that produces cheese with a hardness of 1, 2, ..., or 9, the character is '1', '2', ..., or '9', respectively. There is exactly one nest and one cheese factory that produces cheese with a hardness of 1 to N in the input. It is guaranteed that all other blocks are obstacles or empty lots. It is guaranteed that the mouse can eat all the cheese.
Output
Output an integer that represents the shortest time (in minutes) it takes to eat all the cheese, in one line.
Sample Input and Output
Sample Input 1
3 3 1
S..
...
..1
Sample Output 1
4
Sample Input 2
4 5 2
.X..1
....X
.XX.S
.2.X.
Sample Output 2
12
Sample Input 3
10 10 9
.X...X.S.X
6..5X..X1X
...XXXX..X
X..9X...X.
8.X2X..X3X
...XX.X4..
XX....7X..
X..X..XX..
X...X.XX..
..X.......
Sample Output 3
91
The problem statement and test data used by the automatic judging system are provided by the Information Olympiad Japan Committee.
Problem Name: Used Bookstore (Books)
Problem Description: There is a long-established used bookstore in your town called JOI Bookstore, and you often use it. Each book has a standard price, and if you go to JOI Bookstore, you can sell it at that price.
JOI Bookstore handles books of 10 genres, such as novels, manga, and magazines, sorted by genre. Each genre is assigned a number from 1 to 10. JOI Bookstore offers a service that will buy books of the same genre in bulk at a high price. Specifically, if you sell T books of the same genre, the purchase price per book for that genre will be T-1 yen higher than the standard price. For example, if you sell books of the same genre with standard prices of 100 yen, 120 yen, and 150 yen to JOI Bookstore, the purchase prices will be 102 yen, 122 yen, and 152 yen, respectively.
Now, due to personal circumstances, you have suddenly decided to move. You have N books, but it is difficult to take all of them to your new residence, so you have decided to sell K of them to JOI Bookstore.
Task
Create a program that, given the standard price and genre number of each of your N books, determines the maximum total purchase price.
Constraints
2 ≤ N ≤ 2000: The number of books you have.
1 ≤ K < N: The number of books to be sold to JOI Bookstore.
1 ≤ Ci ≤ 100000 = 10
5
: The standard price of the i-th book.
1 ≤ Gi ≤ 10: The genre number of the i-th book.
Input
The input is given from standard input in the following format:
The first line contains two integers N and K, separated by a space, representing the number of books you have and the number of books you will sell to JOI Bookstore, respectively.
Following N lines describe the books you have. The i-th line (1 ≤ i ≤ N) contains two integers Ci and Gi separated by a space, indicating that the standard price of the i-th book is Ci and the genre number of the i-th book is Gi.
Output
Print the maximum total purchase price in a single line on standard output.
Scoring Conditions
For 20% of the score, N ≤ 20.
For 20% of the score, all book genres are 1 or 2.
For 10% of the score, both of these conditions are satisfied.
For 30% of the score, at least one of these conditions is satisfied.
Examples
Input Example
7 4
14 1
13 2
12 3
14 2
8 2
16 3
11 2
Output Example
60
In this example, selling the 2nd, 4th, 6th, and 7th books will result in a purchase price that is 2 yen higher per book for genre 2, so the purchase prices for these books will be as follows:
Number
Standard Price
Genre
Purchase Price
2
4
6
7
13
14
16
11
2
2
3
2
15
16
16
13
Therefore, the total purchase price is 15 + 16 + 16 + 13 = 60 yen, which is the maximum total purchase price in this case.
The problem statement and test data used in the automatic judging system are provided by the
Japan Committee for the International Olympiad in Informatics
.