CodeEff/ECCO huggingface dataset:
Problem Name: Tetris
Problem Description: Tetris is a game where you arrange falling blocks on a board and clear them. Let's consider a slightly modified version of that game here.
The size of the board in this game is just enough to accommodate the appearing blocks, with 5 squares arranged side by side and sufficient height. The falling blocks are linear, with two types: horizontal and vertical, and there are five types of length ranging from 1 to 5.
The figures from steps (i) to (ho) below represent the process of blocks falling and disappearing. The game progresses from step (i) to step (ha).
When the block is dropped and collides with the blocks stacked below, as in step (i), it stops at that position. Also, if a horizontal square on the board is completely filled with blocks after the block falls, the row of blocks is erased (see step (ni)). Then, the blocks above the erased row sink down one position to their original shape (step (ho)).
Assuming that up to 1000 blocks fall in a single game, if the lengths of the falling blocks are 4 squares horizontally, 3 squares horizontally, 2 squares vertically, and 3 squares vertically, and they fall in the first, first, fourth, and fifth positions from the left, respectively, they fall as shown in steps (i) to (to) below. The remaining blocks become 2 squares.
Create a program that accepts the order in which the blocks fall as input and outputs the number of squares occupied when all the blocks have fallen.
Input
The input is a sequence of multiple datasets. The end of the input is indicated by a line containing 0. Each dataset is provided in the following format.
n
d
1
p
1
q
1
d
2
p
2
q
2
:
d
n
p
n
q
n
The first line gives the number of blocks
n
(1 ≤
n
≤ 1000). The
i
-th line that follows gives the direction
d
i
(1 or 2) of the
i
-th block, the length
p
i
of the block (1 ≤
p
i
≤ 5), and the position
q
i
of the block. The direction of the block
d
i
can be 1 or 2.
Problem Name: Demolition of Bridges
Problem Description: There are n cities in the Waterdebun country. Each city is surrounded by water and is like an island. There are m bridges in Waterdebun, and all cities can be visited by using these bridges for transportation between the cities.
Recently, due to a review of road-specific financial resources, a reduction in the maintenance costs of bridges was decided. It became impossible to maintain all bridges, and some of them were demolished. Therefore, the task of Waterdebun is to minimize the maintenance cost of the bridges while ensuring that all cities can be visited using the bridges that remain.
Create a program that takes as input the number of cities, the number of bridges, and the maintenance cost of each bridge, and outputs the minimum maintenance cost when some bridges are demolished while ensuring that all cities can be visited using the bridges. It is assumed that there is no cost to demolish the bridges. However, each city is numbered from 0 to
n
- 1 in order.
Input
A sequence of multiple data sets is given as input. The end of the input is indicated by two lines of zero. Each dataset is given in the following format.
n
m
a
1
b
1
cost
1
a
2
b
2
cost
2
:
a
m
b
m
cost
m
The first line contains the number of cities
n
(2 ≤
n
≤ 100) and the number of bridges
m
(1 ≤
m
≤ 500). The following
m
lines provide information on the
i
-th bridge.
a
i
,
b
i
are the numbers of the cities connected by the bridge, and
cost
i
(1 ≤
cost
i
≤ 1000) is the maintenance cost of the bridge.
Output
For each dataset, output the total maintenance cost of the bridges on a single line.
Sample Input
5 6
0 2 1
2 1 3
2 3 8
1 3 2
3 4 5
1 4 4
3 3
1 2 3
2 0 3
0 1 3
0 0
Output for the Sample Input
10
6
Problem Name: Bookshelf
Problem Description: Taro-kun is addicted to a certain novel. The novel has a total of n volumes, and the thickness of each volume is different. Taro-kun likes this novel very much, so he is thinking of buying a bookshelf dedicated to this novel. However, if a large bookshelf is placed in the room, it will become quite narrow, so it is necessary to devise a way to make the width of the bookshelf as small as possible. It was found that a bookshelf of m stages can be placed when measuring the height from the floor to the ceiling. So, how can we divide the n volumes of the novel to make the width of the m stage bookshelf as small as possible?
Taro-kun has a particular preference, and the novels stored in each stage must be arranged in order of volume number.
Write a program that takes the number of stages of the bookshelf, the number of volumes of the novel, and the thickness of each book as input, and outputs the width of the smallest bookshelf that can hold all volumes from 1 to
n
. However, the size of the bookshelf frame is not included in the width.
Input
The input consists of a sequence of multiple datasets. The end of the input is indicated by two consecutive zeros. Each dataset is given in the following format.
m
n
w
1
w
2
:
w
n
The first line contains the number of stages of the bookshelf that can be placed in the room
m
(1 ≤
m
≤ 20) and the number of volumes of the novel
n
(1 ≤
n
≤ 100). The following
n
lines give the thickness of the
i
-th volume as an integer
w
i
(1 ≤
w
i
≤ 1,000,000).
However, the width of the bookshelf should not exceed 1,500,000.
There are no more than 50 datasets.
Output
For each dataset, output the minimum width of the bookshelf in a single line.
Sample Input
3 9
500
300
800
200
100
600
900
700
400
4 3
1000
1000
1000
0 0
Output for the Sample Input
1800
1000
Problem Name: Convenience Store
Problem Description: To expand its business, the convenience store Seven-Eleven is considering opening its first store in Wakamatsu City. Since there are already many other convenience stores in Wakamatsu City, the location of the new store is likely to be the key to success. Under the premise of "customers will use the convenience store closest to their home area," Seven-Eleven plans to open a store at a location where "many customers are likely to use it."
Seven-Eleven divided the map of Wakamatsu City into congruent regular hexagons ("blocks") to understand the range covered by each existing convenience store. At this time, the city was divided into blocks so that at most one existing convenience store could be included in each block. Based on the number of blocks that need to be traversed to reach a convenience store from each block, the distance between the convenience store and each block is determined. Each block is considered to be covered by the convenience store that covers it with the shortest distance. The problem is to find the "blocks for which there are no existing convenience stores that cover as many blocks as possible" based on this map.
You are a programmer at Seven-Eleven, and you have been tasked with developing a program to calculate the maximum number of blocks that can be covered from all candidate locations based on the map divided into blocks and information about the candidate location of the new store.
The map divided into blocks of
m × n
is represented as shown in Figure 1. Blocks of hexagons are arranged horizontally in
m
rows and vertically in
n
columns, each represented by a coordinate (
x, y
). The left edge of odd-numbered rows is located just below the left edge of the row above it, and the left edge of even-numbered rows is located just below the left edge of the row above it. For example, coordinate (1, 1) represents the top-left block in Figure 1. Coordinate (1, 2) is located just below coordinate (1, 1), and coordinate (1, 3) is located just below coordinate (1, 2).
Figure 2 shows an example where there are six existing convenience stores, divided into a 6 × 6 map. Each convenience store is numbered in order from 1. When the blocks covered by each convenience store are colored by number, they are divided as shown in Figure 3. Blocks that are not colored, such as block (1, 4) and (2, 5), have two or more convenience stores that are closest, and cannot be determined which convenience store covers the block. For example, in the case of block (1, 4), the distance to convenience stores 4 and 5 is equal, and it is assumed that there is no convenience store that covers this block. The number of blocks covered by convenience store 4 is 5.
Suppose Seven-Eleven is considering locations (1, 3) and (5, 3) as candidate locations for the new store. If a store is located at (1, 3), it can cover three blocks (Figure 4). On the other hand, if a store is located at (5, 3), it can cover four blocks (Figure 5). Therefore, the maximum number of blocks that can be covered is 4.
The input consists of multiple datasets. The end of the input is indicated by
Problem Name: One-way Ticket to Youth
Problem Description: Taro-kun is planning a long trip by train during the summer vacation. However, as a high school student, Taro-kun only has a one-month summer vacation, so in order to travel as far away as possible, he needs to find the cheapest and fastest way to travel. Let's create a program to help Taro-kun plan his trip so he can enjoy a wonderful journey.
Given information about the railway and the number of stations, create a program that will output the minimum cost or shortest time in response to a query.
Input
The input is a sequence of multiple datasets. The end of the input is indicated by two consecutive zeros. Each dataset is given in the following format.
n
m
a
1
b
1
cost
1
time
1
a
2
b
2
cost
2
time
2
:
a
n
b
n
cost
n
time
n
k
p
1
q
1
r
1
p
2
q
2
r
2
:
p
k
q
k
r
k
The first line contains the number of railway information
n
(1 ≤
n
≤ 3000) and the number of stations
m
(1 ≤
m
≤ 100).
For each of the following
n
lines, information about the i-th line is given. For each line, the numbers of the two stations connected by the line,
a
i
and
b
i
(1 ≤
a
i
,
b
i
≤
m
), and the cost
cost
i
(1 ≤
cost
i
≤ 1000) and travel time
time
i
(1 ≤
time
i
≤ 1000) are given. If
a
i
and
b
i
are connected by a line, both movements from
a
i
to
b
i
and from
b
i
to
a
i
are possible at the same cost and travel time.
The next line contains the number of queries
k
(1 ≤
k
≤ 200). For the following
k
lines, the i-th query is given. For each query, the departure station
p
i
, arrival station
q
i
, and type of value to output
r
i
(0 or 1) are given. Note that there is always a route for each query.
The number of datasets does not exceed 50.
Output
For each dataset, output the minimum cost or shortest time on one line. If
r
i
is 0, output the minimum cost; if
r
i
is 1, output the shortest time.
Sample Input
6 5
1 2 200 10
1 4 400 15
1 3 250 25
2 4 100 10
4 5 150 20
3 5 300 20
2
1 5 0
1 5 1
0 0
Output for the Sample Input
450
35
Problem Name: Alchemy Master
Problem Description: You have finally obtained the magic cauldron, the alchemy cauldron. When you put multiple items in the alchemy cauldron, you can create a new item. The newly created item can also be put into the alchemy cauldron to create other items. We will call the list of items required to create an item the alchemy recipe. The following are three examples of alchemy recipes.
A racket can be made from wood and string.
Onigiri can be made from rice and water.
A guitar can be made from a racket, a microphone, and onigiri.
Items can also be obtained by purchasing them with money, but it may be cheaper to create them using the alchemy cauldron. For example, suppose the purchase price of each item is given as follows.
Item Name
Purchase Price (yen)
Wood
3,000
String
800
Rice
36
Water
0
Racket
5,000
Microphone
Problem Name: Rock-Paper-Scissors
Problem Description: Five friends decided to play rock-paper-scissors. In this game, there are three possible moves: rock, paper, and scissors. Rock beats scissors, scissors beats paper, and paper beats rock. If two players make the same move, the game is a tie.
Write a program that takes as input the five moves of each player and outputs the result of each player's game. Rock is represented by the number 1, scissors by the number 2, and paper by the number 3. A win is represented by the number 1, a loss by the number 2, and a tie by the number 3. The program should output the results in the order in which the input was given.
Input
The input consists of multiple datasets. The input ends with a line containing a single zero.
Each dataset is given in the following format:
h
1
h
2
h
3
h
4
h
5
The
i
-th line contains the move of the
i
-th player, which is an integer
h
i
(1, 2, or 3).
There will be at most 200 datasets.
Output
For each dataset, output the results of the five players' games. The
i
-th line should contain the result of the
i
-th player's game (1, 2, or 3).
Sample Input
1
2
3
2
1
1
2
2
2
1
0
Output for the Sample Input
3
3
3
3
3
1
2
2
2
1
Problem Name: What is the scenery in the picture?
Problem Description: Mr. A came to Aizu for sightseeing. From the window of the hotel where he stayed, he could see the Aizu Basin at a glance. While looking at the scenery, he noticed that a piece of a photograph was lying on the floor. It seemed to have taken a picture of the outside scenery from the window. "I wonder where I took it," Mr. A began to look for the place where the photograph and the outside scenery matched, holding the photograph so that it was the same size as the outside scenery seen from the window.
Now let's do what Mr. A is doing with a computer. Divide the outside scenery visible from the window into an
n × n
square (
n
is referred to as the size of the scenery). Each square has a non-negative integer that represents the image information of that square. The position of each square is represented by coordinates (
x, y
). The coordinates of each square are as follows:
The piece of the photograph is represented by a square of
m × m
squares (referred to as the size of the piece of the photograph) . In this square, the squares that are part of the piece of the photograph have image information, and the squares that are not included in the piece of the photograph have -1 written on them. For example, in the figure below, the colored part represents the shape of the actual photograph piece. There may be holes in the piece of the photograph, but it is always connected. (When a square with a value of 0 or more is only adjacent to the vertex, it is regarded as not connected.) Also, a value of -1 does not line up in a row or column from end to end.
Search for the area in the scenery that matches one of the 0, 90, 180, or 270 degree rotated pieces of the photograph visible from the window. For example, when the scenery is represented as shown in the figure below, rotating the piece of the photograph counterclockwise 90 degrees matches the colored area.
Given the information of the scenery visible from the window and the piece of the photograph, create a program that outputs the coordinates of the square closest to the top and left of the area that matches the piece of the photograph rotated by 0, 90, 180, or 270 degrees in the scenery. If there are multiple matching areas, output the coordinates of the square closest to the top and left among the squares in those areas. If there is no matching area, output NA.
Input
The input is a sequence of multiple data sets. The end of the input is indicated by two consecutive zeros. Each data set is given in the following format.
n
m
w
11
w
12
...
w
1n
w
21
w
22
...
w
2n
:
w
n1
w
n2
...
w
nn
p
11
p
12
...
p
1m
p
21
p
22
...
p
2m
:
p
m1
p
m2
...
p
mm
The first line contains
n, m
(1 ≤
n
≤ 100, 1 ≤
m
≤ 50,
m
≤
n
) .
The following
n
lines give the information of the scenery visible from the window
w
ij
(0 ≤
w
ij
≤ 15), and the following
m
lines give the data of the photograph piece
p
ij
(-1 ≤
p
ij
≤ 15).
There are no more than 100 data sets.
Output
For each input data set, output the coordinates of the square or NA on one line.
Sample Input
8 4
2 1 3 1 1 5 1 3
2 3 2 4 1 0 2 1
0 3 1 2 1 1 4 2
1 2 3 2 1 1 5 4
0 2 0
Problem Name: Class Assignment
Problem Description: At Aizu Juku, students take a proficiency test when they enter the cram school and are divided into classes. The test covers three subjects: math, English, and Japanese, and the students are divided into classes A, B, and C. Class A has the highest level, followed by B and C in order.
The classification is based on the following table.
Conditions
Class
There is a 100 point subject.
A
The average score for math and English is 90 points or higher.
A
The average score for all three subjects is 80 points or higher.
A
The average score for all three subjects is 70 points or higher.
B
The average score for all three subjects is 50 points or higher and the score for math or English is 80 points or higher.
B
Does not meet the above conditions.
C
If a student meets multiple conditions, they will be assigned to the higher level class.
Write a program that takes as input the number of students
n
(1 ≤
n
≤ 10000), the math scores
pm
i
(0 ≤
pm
i
≤ 100), the English scores
pe
i
(0 ≤
pe
i
≤ 100), and the Japanese scores
pj
i
(0 ≤
pj
i
≤ 100) for each student, and outputs the class (in uppercase letters) of each student.
Input
The input consists of multiple datasets. The end of the input is indicated by a single line with a zero.
Each dataset is given in the following format.
n
pm
1
pe
1
pj
1
pm
2
pe
2
pj
2
:
pm
n
pe
n
pj
n
All input is given as integers. There are no more than 1000 datasets.
Output
For each input dataset, output the class of each student in order.
Sample Input
4
100 70 20
98 86 55
80 34 36
65 79 65
2
99 81 20
66 72 90
0
Output for the Sample Input
A
A
B
C
A
B
Problem Name: Histogram
Problem Description: There is an ice cream shop named Tenai Ice Cream that always has 10 types of ice cream on display. The shop manager creates a graph every day to represent the sales of each ice cream flavor, as a reference for product development.
For the shop manager, you are asked to create a program that displays the sales of each ice cream flavor in a graph.
The input will consist of multiple data sets. The end of the input is indicated by a single line containing a 0. Each data set will be given in the following format:
n
c
1
c
2
:
c
n
The first line of each data set will contain the total number of ice creams sold in one day
n
(1 ≤
n
≤ 10000). The following
n
lines will contain the ice cream flavors sold, represented by integers from 0 to 9 inclusive.
There will be no more than 20 data sets.
For each data set, output the sales of each ice cream flavor in the order of their flavor number.
Sample Input
15
2
6
7
0
1
9
8
7
3
8
9
4
8
2
2
3
9
1
5
0
Output for the Sample Input
*
*
***
*
*
-
*
**
***
**
-
*
-
-
-
*
-
-
-
*
Problem Name: Quadruplet Primes
Problem Description: A set of four prime numbers arranged in the form (a, a+2, a+6, a+8) is called a quadruplet prime. Among the four prime numbers that make up the quadruplet prime, the largest number is called the size of the quadruplet prime. For example, the smallest quadruplet prime of size 13 is the set (5, 7, 11, 13), and the next largest quadruplet prime of size 19 is the set (11, 13, 17, 19).
Write a program that takes an integer
n
(13 ≤
n
≤ 10,000,000) as input and outputs the size of the largest quadruplet prime whose size is less than or equal to
n
.
Input
The input consists of multiple datasets. The end of input is indicated by a line containing a single zero.
For each dataset, a single integer
n
is given on a line.
The number of datasets is no more than 2000.
Output
For each input dataset, output the size of the largest quadruplet prime on a single line.
Sample Input
13
14
15
16
17
18
19
20
10000
0
Output for the Sample Input
13
13
13
13
13
13
19
19
9439
Problem Name: Lost Twins
Problem Description: Takayuki and Kazuyuki are twins who get along well, but their behavior is completely opposite. For example, if Takayuki goes west, Kazuyuki will go east, and if Kazuyuki goes north, Takayuki will go south. Currently, the two of them are in a department store and are in separate locations. How can they meet as soon as possible despite moving in opposite directions?
The department store is represented by a grid consisting of
W
columns and
H
rows, and the two can move one square to the east, west, north, or south per unit time. However, they cannot move outside the grid or to a square with an obstacle.
The position of each square in the grid is indicated by the coordinate (
x
,
y
) as shown in the figure below.
Given the grid information and the initial positions of the two people as input, create a program to output the shortest time it will take for the two to meet. If they cannot meet or it takes 100 or more units of time to meet, output NA. The grid information is given as numbers in
H
rows and
W
columns, and the positions of the two people are given as coordinates.
If one of Takayuki or Kazuyuki is stuck in an obstacle or outside the grid after moving, he cannot move, so the one who is stuck will return to his original location, but the other can move without returning to his original location.
Meeting of the two means that they stop on the same square after moving. Even if they pass by each other, they are not considered to have met.
Input
The input consists of multiple datasets. The end of input is indicated by two zeros on a line. Each dataset is given in the following format.
W
H
tx
ty
kx
ky
d
11
d
21
...
d
W1
d
12
d
22
...
d
W2
:
d
1H
d
2H
...
d
WH
The first line contains the size of the department store
W
and
H
(1 ≤
W
,
H
≤ 50). The second line contains Takayuki's initial position
tx, ty
, and the third line contains Kazuyuki's initial position
kx, ky
.
The next
H
lines give the information for the department store.
d
i,j
represents the type of square (
i, j
), and represents a movable square when it is 0 and represents a square with an obstacle when it is 1.
There are no more than 100 datasets.
Output
For each input dataset, output the shortest time in one line.
Sample Input
6 6
2 4
6 2
0 0 0 0 1 0
0 1 0 0 0 0
0 1 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 1
0 0 0 0 0 0
3 3
1 1
3 3
0 0 0
0 1 0
0 0 0
0 0
Sample Output
3
NA
Problem Name: Hit and Blow
Problem Description: Taro and Hanako decided to play Hit and Blow. The rules of Hit and Blow are as follows:
The game is played between a questioner and an answerer.
The questioner decides a 4-digit number (the correct answer) that does not include any duplicate digits.
The answerer tries to guess the 4-digit number (the guess).
The questioner gives hints in the form of the number of hits and blows.
A hit is when a digit in the guess is in the same position as the corresponding digit in the correct answer. A blow is when a digit in the guess matches a digit that is in the correct answer but in a different position. For example, if the correct answer is 1234 and the guess is 1354, the questioner gives the hint "2 hits, 1 blow", and the game continues until the correct answer is guessed.
The game is played with the questioner and the answerer taking turns, and the winner is the person who guesses the correct answer with the fewest number of guesses.
Taro and Hanako find it a bit tedious to judge the number of hits and blows each time. Let's create a program that can determine the number of hits and blows instantly for them.
Write a program that takes the correct answer
r
and the guess
a
as input and outputs the number of hits and blows.
r
and
a
are both sequences of 4 digits from 0 to 9.
Input
The input consists of multiple datasets. The end of the input is indicated by two consecutive zeros. For each dataset,
r
and
a
are given on one line separated by a space.
There are no more than 12,000 datasets.
Output
For each dataset, output the number of hits and blows on a single line.
Sample Input
1234 5678
1234 1354
1234 1234
1230 1023
0123 1234
0 0
Output for the Sample Input
0 0
2 1
4 0
1 3
0 3