CodeEff/ECCO huggingface dataset:
Problem Name: Dangerous Bridge
Problem Description: In Aizufurukamatsumura, which is located much further north than Aizuwakamatsu City, the "Yabashi" bridge is the only way to move to the surrounding villages. Despite the large number of pedestrians crossing the bridge, it has become so old that it seems to collapse at any moment.
Yabashi has a strength that can withstand up to 150 [kg]. For example, an 80 [kg] person and a 50 [kg] person can cross it at the same time, but if a 90 [kg] person starts to cross while an 80 [kg] person is crossing, Yabashi will collapse.
If Yabashi collapses, the people of Aizufurukamatsumura will lose their means of moving to the surrounding villages. Therefore, you, the only programmer in the village, have decided to create a program that determines whether or not the bridge will collapse from the way people cross the bridge in order to protect the villagers' lives.
The program should take an input of the number of pedestrians crossing the bridge
n
(1 ≤
n
≤ 100), the weight of each pedestrian
m
i
(1 ≤
m
i
≤ 100), the time
a
i
when they start crossing, and the time
b
i
when they finish crossing (0 ≤
a
i
,
b
i
< 2
31
). If the bridge does not collapse, output "OK". If it collapses, output "NG". Note that if the total weight of pedestrians on the bridge exceeds 150 [kg], Yabashi will collapse. Also, pedestrians are on the bridge at time
a
i
, but not on the bridge at time
b
i
.
Input
A sequence of multiple data sets is given as input. The end of the input is indicated by a single zero. Each data set is given in the following format.
n
m
1
a
1
b
1
m
2
a
2
b
2
:
m
n
a
n
b
n
The number of data sets does not exceed 1200.
Output
For each input data set, output whether the bridge will collapse or not on one line.
Sample Input
3
80 0 30
50 5 25
90 27 50
3
80 0 30
70 5 25
71 30 50
0
Output for the Sample Input
NG
OK
Problem Name: Game of Life
Problem Description: Taro went to a toy shop to buy a "Game of Life" made by Aizu Hobby. You play the game using a board with squares and a roulette. The board has a start and end square, which are connected by a continuous sequence of squares as shown in the figure. First, a game piece is placed on the starting square, and then the roulette is spun to determine how many squares to move forward. Some squares award or deduct money or cause events that change the position of the game piece. The final winner is determined by the amount of money the player has when they reach the finish line.
The interesting thing about the "Game of Life" by this company is that the size of the roulette's sections, the number of squares to the finish line, and the placement of event squares are different for each package. This information is written on the package, so you can check it by reading it. Taro wants to choose the "Game of Life" that will earn him the most money, so he wants to buy the one with the highest expected value of money earned. Therefore, you have decided to help Taro choose his game.
The roulette has
X
sections, each with a value
V
1
,
V
2
, ...,
V
X
written on it. The board has squares numbered 0, 1, ...,
Y
, which are connected in order. There are
Z
special squares on the board called "event squares," which trigger special actions when landed on. The numbers of the event squares are given as
N
i
. There are three types of event squares (
E
i
) that trigger the following actions, respectively, depending on the value
A
i
.
Type (
E
Problem Name: Hot Spring Trip
Problem Description: Takeshi, who loves hot springs, is planning a trip to a certain hot spring resort during his next long vacation. He plans to travel by long-distance bus, and wants to get to his destination as cheaply as possible. Even though he has savings, Takeshi, who is not confident in his finances, decided to consult his grandfather. Impressed by the plan, his grandfather gave him a special ticket.
The ticket allows him to take two consecutive long-distance buses for free once. Depending on how it is used, it can greatly reduce the travel expenses, but to maximize its effectiveness, it is necessary to carefully plan the trip.
The total number of departure points, destinations, and transit points is
n
, and there are
m
routes that connect two points. Each location is assigned a number from 1 to
n
. The departure point is 1 and the destination is
n
. Route information is represented by the two points
a
and
b
that the route connects, and the fare
c
. Due to the effectiveness of the special ticket, you can pass two consecutive routes at zero cost from any point. However, even if you pass through the destination on the way, you will not have arrived at the destination yet.
Create a program that takes the total number of departure points, destinations, and transit points
n
, the number of routes
m
, and the information of each route as input, and outputs the minimum fare. It is assumed that there is a route to reach the destination from the departure point.
Input
Multiple datasets are given. The end of the input is indicated by two zeros. Each dataset is given in the following format.
n
m
a
1
b
1
c
1
a
2
b
2
c
2
:
a
m
b
m
c
m
The first line gives the total number of departure points, destinations, and transit points
n
(2 ≤
n
≤ 100) and the number of routes
m
(1 ≤
m
≤ 300). The following
m
lines give the information for each route,
a
i
,
b
i
, and
c
i
(1 ≤
c
i
≤ 1000).
The number of datasets is no more than 40.
Output
For each dataset, output the minimum fare on one line.
Sample Input
2 1
1 2 5
3 2
1 2 5
2 3 5
6 9
1 2 7
1 3 9
1 5 14
2 3 10
2 4 15
3 4 11
3 5 2
4 5 9
4 6 8
0 0
Sample Output
5
0
7
Problem Name: Magic Circle
Problem Description: In the depths of a remote forest lived a witch named Marie. As a witch, she used magic to provide for her daily needs such as food, water, and fuel.
Her magic is activated by drawing a magic circle using several stones imbued with magical power and a rope. The magic circle is drawn by placing the stones and connecting pairs of stones with the rope. However, the rope must not be slack and no rope, except for the ends, should touch other stones or ropes. Of course, you cannot place multiple stones in the same place as long as these constraints are observed. There are no restrictions on the position of the stones or the length of the rope, except for the restrictions on the relationship between the stones and the ropes. In addition, she does not necessarily connect the same pair of stones with more than two ropes, nor does she connect both ends of a single rope to the same stone.
At first, Marie drew magic circles by sticking the stones to the flat walls of her house. However, she eventually realized that there were some magic circles that she could not make at all. After a while, she came up with a way to determine whether a magic circle could be drawn on a flat wall, that is, a two-dimensional plane. A magic circle that includes the following parts cannot be drawn on a two-dimensional plane only in this case.
Figure 1: Complete graph with 5 vertices
Figure 2: Complete bipartite graph with 3 vertices each
To draw such a magic circle, she came up with a magic spell that fixes the stone in the air. In three-dimensional space, these magic circles can also be drawn. Moreover, she found out that any magic circle could be drawn in three-dimensional space.
Now, here is the problem. One day, Marie decided to make a magic circle for a foot lamp at the entrance of her house. However, she had already installed various magic circles in the narrow entrance, so she had to draw the magic circle for the foot lamp on a one-dimensional line, which was the only remaining space. For several foot lamp magic circles she designed, create a program that determines whether they can be drawn on a line and outputs
yes
if they can be drawn or
no
if they cannot.
A magic circle is given by the number of stones
n
, the number of ropes
m
, and information about
m
ropes. Ropes are represented by the numbers
u
and
v
of the stones at both ends. Stones are given numbers from 1 to
n
, where
n
is between 1 and 100,000, and
m
is between 0 and 1,000,000.
Input
The input consists of a sequence of multiple datasets. The end of the input is indicated by two zeros. Each dataset is as follows:
1st line: Number of stones
n
, Number of ropes
m
(Integers separated by a half-width space)
2nd line: Information on the 1st rope
u
v
(Integers separated by a half-width space)
3rd line: Information on the 2nd rope
:
m+1
line: Information on the
m
th rope
The number of datasets does not exceed 20.
Output
For each input dataset, output "yes" or "no" on one line.
Sample Input
5 4
1 2
2 3
3 4
4 5
4 6
1 2
1 3
1 4
2 3
2 4
3 4
5 0
0 0
Sample Output
yes
no
yes
Problem Name:
Problem Description: I decided to plant vegetables in my home garden. I had n seeds, so I planted one seed per day for n days. All the seeds sprouted and are growing well. I can't wait for harvest time.
One day, while watering the seedlings as usual, I noticed something strange. There was one more vegetable plant than there should be. Weeds have grown up. I want to pull them out immediately, but the problem is that all the seedlings look alike, and I can't tell the difference between the vegetables and the weeds.
The clue is the growth rate of the vegetables. This vegetable continues to grow at a fixed length per day since the seed was sown. However, I don't know how many centimeters this "fixed length" is. Also, I forgot when I planted the first seed. The seedlings are lined up in a row, but the only thing I remember is that I planted one seed from right to left every day when I planted them.
Create a program that inputs n+1 plant lengths and outputs the length of the weed.
Input:
The input consists of multiple datasets. The end of the input is indicated by a single zero. The input is given in the following format.
n
h
1
h
2
h
3
... h
n+1
The first line contains an integer n (4 ≤ n ≤ 100) which represents the number of vegetable plants. The second line contains n+1 integers separated by a single space, h
i
(1 ≤ h
i
≤ 10
9
), representing the length of each plant, from left to right.
Inputs that form an arithmetic sequence, such as h
1
h
2
... h
n+1
, will not be given.
There are no more than 500 datasets.
Output:
For each dataset, output the length of the weed.
Input Example:
5
1 2 3 6 4 5
6
1 3 6 9 12 15 18
4
5 7 9 11 12
0
Output Example:
6
1
12
Problem Name: All Numbers Lead to 6174
Problem Description: Perform the following operation on a four-digit number N consisting of digits 0 to 9.
Arrange the numbers in each digit of N in descending order, and let L be the resulting number.
Arrange the numbers in each digit of N in ascending order, and let S be the resulting number.
Set the difference L-S as the new N (one operation completed)
Repeat from 1. for the new N
In this case, it is known that every four-digit number eventually becomes 6174 except for numbers where all digits are the same (such as 0000, 1111, etc.). For example, when N = 2012,
1st operation (N = 2012): L = 2210, S = 0122, L-S = 2088
2nd operation (N = 2088): L = 8820, S = 0288, L-S = 8532
3rd operation (N = 8532): L = 8532, S = 2358, L-S = 6174
and 6174 is reached in three operations.
Write a program that calculates the number of operations required to reach 6174 from a four-digit number consisting of digits 0 to 9.
Input
The input consists of multiple datasets. The end of input is indicated by a line containing only 0000. Each dataset is given in the following format.
N
The dataset consists of one line, and N (1 ≤ N ≤ 9999) represents a four-digit number. If N < 1000, the upper digits are filled with 0s.
The number of datasets does not exceed 10,000.
Output
For each dataset, output the number of operations required to reach 6174 on one line. However, if a number is given as input where all digits are the same, output NA.
Sample Input
6174
2012
3333
0000
Sample Output
0
3
NA
Problem Name: Beat Panel
Problem Description: Yuta is addicted to the popular game "Beat Panel" at the nearby game center. This game consists of 16 panel-shaped buttons arranged in a grid as shown in the figure, 4 × 4 in total.
As shown in the figure, buttons 1, button 2, ..., button 16 are arranged from the upper left to the lower right. At a certain interval, a beat sound is played and finally an end sound is played. Multiple buttons light up at the same time as the beat sound. There may be no buttons that light up. Players can use both fingers to press multiple buttons at the same time only once from immediately after the beat sound until the next sound is played. It is also possible to do nothing. The game ends at the same time as the end sound is played.
Yuta has learned c ways to press buttons, and each time a beat sound is played, he decides one of them and presses the button. If the pressed button is lit, the light of those buttons disappears, and the number of disappeared buttons is added to the player's score. In addition, once a button lights up, its light will not go out until the button is pressed.
Given the way the buttons light up and the c ways Yuta has learned to press the buttons when the beat sound is played n times, create a program that outputs the maximum score Yuta can get.
Input
The input consists of multiple data sets. Two zeros indicate the end of the input. Each data set is given in the following format.
n c
a
1,1
a
1,2
... a
1,16
a
2,1
a
2,2
... a
2,16
...
a
n,1
a
n,2
... a
n,16
b
1,1
b
1,2
... b
1,16
b
2,1
b
2,2
... b
2,16
...
b
c,1
b
c,2
... b
c,16
The first line consists of two integers separated by a single space. n (1 ≤ n ≤ 30) indicates the number of beat sounds, and c (1 ≤ c ≤ 30) indicates the number of button presses learned. The next n+c lines indicate how the buttons light up and how the buttons are pressed. The delimiter of input items in the line is a single space. a
k,i
represents whether button i lights up when the k-th beat sound is played and b
j,i
represents whether button i is pressed by the j-th method out of c methods. The value of a
k,i
represents 0 for "not light up" and 1 for "light up". The value of b
j,i
represents 0 for "not press" and 1 for "press".
The number of data sets is no more than 20.
Output
For each data set, output the maximum score on one line.
Input Examples
2 2
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
2 2
0 0 1 0 1 1 1 1 0 0 1 0 0 0 1 0
0 1 0 1 0 1 1 1 0 1 0 1 0 0 0 0
0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0
0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0
5 3
0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0
Output Examples
8
7
16
Problem Name: Modulo Query
Problem Description: You are given N cards, each containing a different natural number (1 to 300000). When you are asked a question, you should answer the maximum remainder obtained when dividing the number on the card you have by the number I said.
For example, suppose you have three cards with numbers 9, 3, and 8. If I say "4", find the remainder when you divide 9, 3, and 8 by 4. The remainders are 1, 3, and 0, respectively, but the largest remainder is 3, so the correct answer is 3.
Now, let's get started. What? It's difficult if there are too many cards? Well, that's true. Then, let's use a computer to find the maximum remainder. Please create a program that finds the largest remainder among the remainders obtained by dividing the numbers on the cards by the number asked. Note that questions can be asked multiple times, but the same number will not be asked twice.
Input
The input consists of a single data set in the following format:
N Q
c
1
c
2
... c
N
q
1
q
2
:
q
Q
The first line contains the number of cards N (2 ≤ N ≤ 300000) and the number of questions Q (2 ≤ Q ≤ 100000) separated by a single space. The second line contains the numbers c
i
(1 ≤ c
i
≤ 300000) written on the cards separated by a single space. The next Q lines contain the numbers q
i
(1 ≤ q
i
≤ 300000) asked as questions.
Output
Output the maximum remainder for each question on a separate line.
Sample Input
3 3
9 3 8
4
6
5
Sample Output
3
3
4
Problem Name: Temperature difference
Problem Description: Hello athletes, welcome to the PC contest. To participate in the event, it's important to manage your health. In the season where the temperature changes greatly, it is said that your body is under stress and you are more likely to catch a cold. The day you have to be most careful is when the difference between the highest and lowest temperatures is the largest. When the highest and lowest temperatures for each day are given for 7 days, create a program that outputs the value obtained by subtracting the lowest temperature from the highest temperature for each day.
Input
The input data is given in the following format.
a
1
b
1
a
2
b
2
:
a
7
b
7
The input consists of 7 lines, and the i-th line gives an integer representing the highest temperature
a
i
(-40 ≤
a
i
≤ 40) and the lowest temperature
b
i
(-40 ≤
b
i
≤ 40) for the i-th day. For all days, the highest temperature
a
i
is always equal to or greater than the lowest temperature
b
i
.
Output
Output the temperature difference for 7 days on 7 lines.
Sample Input
30 19
39 20
19 18
25 20
22 21
23 10
10 -10
Sample Output
11
19
1
5
1
13
20
Problem Name: Ending of Bōzu Mekuri
Problem Description: One of the games played using the Hyakunin Isshu cards is called "Bōzu Mekuri". It is widely enjoyed since it is a simple game that uses only picture cards. There are various derivative types of the game, but here we consider Bōzu Mekuri played by N participants with the following rules:
A total of 100 cards are used, consisting of 64 "men", 15 "bōzu," and 21 "hime".
The cards are mixed well with their backs facing up to create a "card pile" so that the pictures cannot be seen.
The participants draw one card from the pile in order, starting from the first person. After the N-th person, the game starts again from the first person.
If the drawn card is a "man," the person who drew it gains the card.
If the drawn card is a "bōzu," the person who drew it places all the cards they have, including the card they drew, on the "field".
If the drawn card is a "hime," the person who drew it gains all the cards on the field, including the card they drew.
When there are no more cards in the pile, the game ends, and the person with the most cards wins.
Given the number of participants and the order of cards in the card pile, create a program that outputs the number of cards held by each participant at the end of the game in ascending order and the number of cards remaining in the field.
Input
The input consists of multiple datasets. The end of the input is indicated by a single zero. Each dataset is given in the following format:
N
c
1
c
2
... c
100
Each dataset consists of two lines. The first line contains an integer N (2 ≤ N ≤ 10) indicating the number of participants. The second line contains a string indicating the order of cards in the card pile. The character c
i
represents the i-th card drawn, where "M" represents a "man" card, "S" represents a "bōzu" card, and "L" represents a "hime" card. There are no spaces between the characters.
The number of datasets does not exceed 100.
Output
For each dataset, output the number of cards held by each participant in the order of cards at the end of the game on a single line. The number of cards held by each participant should be arranged in ascending order, followed by the number of cards left in the field. Separate each number with a single space. Do not output any spaces at the end of the line.
Sample Input
2
SSSSSSSSSSSSSSSLLLLLLLLLLLLLLLLLLLLLMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
2
SSSSSSSSSSSSSSLLLLLLLLLLLLLLLLLLLLMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMSL
5
MMMMMMSLSLLMMMSMMSLMMMLMMMMLSLLLLMLSMMLMMLLMSSSLMMMMLMLSMLMSMMMMMMMSMMMMMMLMMMMMSMMMLMMLMMMMMMMMMSSM
0
Sample Output
42 58 0
0 100 0
0 0 3 10 59 28
Problem Name: Formation
Problem Description: At Akabe High School, a programmer training school, the roles of competitive programmers in team matches are divided into the following three types:
C:
Coder
Skilled in programming languages and performs coding.
A:
Algorithmist
Good at logical thinking and considers algorithms.
N:
Navigator
Good at reading comprehension and analyzes/debugs problems.
In this school, teams of three are formed in one of the following formations:
CCA:
Well-balanced and stable type
CCC:
Fast break type with high risk
CAN:
Cautious type that accurately solves problems
As the coach of the competitive programming team, you carefully consider how to combine these members to form as many teams as possible. Therefore, create a program that accepts the number of coders, algorithmists, and navigators as input, and outputs the maximum number of teams that can be formed.
Input
The input consists of a single dataset. The input data is given in the following format.
Q
c
1
a
1
n
1
c
2
a
2
n
2
:
c
Q
a
Q
n
Q
The first line contains the number of years (
Q
) for which you want to find the number of teams. For each of the following
Q
lines, the number of personnel for each role is given for each year. Each line contains the number of coders (
c
i
) (0 ≤
c
i
≤ 1000), the number of algorithmists (
a
i
) (0 ≤
a
i
≤ 1000), and the number of navigators (
n
i
) (0 ≤
n
i
≤ 1000).
Output
For each year, output the maximum number of teams that can be created on one line.
Sample Input
4
3 0 0
1 1 1
9 4 1
0 1 2
Sample Output
1
1
4
0
Problem Name: Programming Contest
Problem Description: Every year, a programming contest is held at Byakko University. When the number of teams is N, each team is assigned a team ID from 1 to N. The contest starts with all team scores at 0, and lasts for L seconds continuously.
This year's contest will be broadcast on television. Only the team with the highest score at that time will be shown on TV during the contest. However, if there are multiple teams that meet the criteria, the team with the smallest team ID will be shown. When the team to be shown changes, the camera switches instantly.
You have obtained the contest log. The log contains records of when a team's score changed. Each record is given in the form "Team
d
scored
x
points at
t
seconds after the start of the contest". Note that the current score may be less than 0 because points may be deducted.
Create a program that takes the contest log as input and reports the ID of the team that was shown on TV for the longest time from the start to the end of the contest.
Input
The input consists of a single dataset in the following format.
N
R
L
d
1
t
1
x
1
d
2
t
2
x
2
:
d
R
t
R
x
R
The first line contains three integers.
N
(2 ≤
N
≤ 100000) is the number of teams,
R
(0 ≤
R
≤ 1000000) is the number of records included in the log, and
L
(1 ≤
L
≤ 1000000) is the length of the contest. Following this, information on each record is given for
R
lines. Each record indicates that team
d
i
(1 ≤
d
i
≤
N
) scored or was deducted
x
i
points at
t
i
seconds after the start of the contest (0 <
t
i
<
L
). Here,
t
i
and
x
i
are integers, and
t
i-1
≤
t
i
.
Output
Output the ID of the team that was shown on TV for the longest time from the start to the end of the contest on one line. However, if there are multiple teams that meet the criteria, output the team with the smallest team ID.
Sample Input 1
3 4 600
3 100 5
1 200 10
2 400 20
3 500 20
Sample Output 1
1
Sample Input 2
3 5 600
3 100 5
1 200 10
2 300 30
1 400 -8
2 400 -27
Sample Output 2
3