CodeEff/ECCO huggingface dataset:
Problem Name: Shopping in JOI Kingdom
Problem Description: There are N towns in the JOI Kingdom, and they are connected by M bidirectional roads. There are shopping malls in K of the towns, and citizens go shopping by traveling through the roads. Depending on the location of the house, it may be necessary to travel a long distance to go shopping, which is very inconvenient. To understand this situation, the king decided to investigate how much longer the shortest distance from a town with a shopping mall can be depending on the location of the house. Since houses may be built along the road (see Example 1), this investigation is very difficult. Therefore, the king asked you, an excellent programmer, to create a program to conduct the investigation.
Task
Create a program that, given information about the roads and towns with shopping malls, finds the distance to the farthest point (including endpoints) on the road from the town with a shopping mall. The distance to move within the town can be ignored.
Constraints
2 ≤
N
≤ 3000: the number of towns in the JOI Kingdom.
1 ≤
M
≤ 100000 = 10
5
: the number of roads in the JOI Kingdom.
1 ≤
K
≤
N
: the number of towns with shopping malls.
1 ≤
l
i
≤ 1000: the length of the
i
-th road.
Input
Read the following from standard input:
The first line contains three integers
N
,
M
, and
K
separated by a space.
N
represents the number of towns in the JOI Kingdom,
M
represents the number of roads in the JOI Kingdom, and
K
represents the number of towns with shopping malls. Towns are numbered from 1 to
N
.
The next
M
lines represent road information. The
i
+1-th line (1 ≤
i
≤
M
) contains three integers
a
i
,
b
i
, and
l
i
separated by a space (1 ≤
a
i
,
b
i
≤
N
, 1 ≤
l
i
≤ 1000). This indicates that the
i
-th road connects towns
a
i
and
b
i
and has a length of
l
i
. The ends of the road are not in the same town. For any two towns
p
and
q
, there are no more than two roads that connect them. Any town can be reached by following some roads from any other town.
The next
K
lines represent shopping mall information. The (
i
+
M
+1)-th line (1 ≤
i
≤
K
) contains a single integer
s
i
(1 ≤
s
i
≤
N
) indicating that there is a shopping mall in town
s
i
.
s
1
, ...,
s
K
are all different.
Output
Output a single integer, the rounded-down distance to the town with a shopping mall that is farthest from the point on the road.
Scoring
For 40% of the test cases,
K
= 1.
Examples
Example 1
3 3 1
1 2 1
2 3 1
3 1 1
1
Output 1
2
The towns are shown in the following figure. All roads have length 1. There is only one shopping mall in town 1.
The farthest point from the town with a shopping mall is the point on the road that connects towns 2 and 3, which is 0.5 units from town 2. The distance to the town with a shopping mall is thus 1.5, which rounds down to 2. Therefore, the output is 2.
Example 2
4 5 2
1 2 4
1 3 1
2 3 2
2 4 2
3 4 1
2
4
Output 2
3
Problem Name: Pasta
Problem
Problem Description: You love pasta and eat it for dinner every day. You can make three types of pasta: tomato sauce, cream sauce, and basil sauce.
You decided to plan dinner for N days. Choose one of the three types of pasta each day. However, if you choose the same pasta for three or more consecutive days, you will get bored. Also, K days of pasta are already decided among N days.
Given the value of N and pasta information for K days as input, create a program to find the number of plans that satisfy the conditions and output the remainder when divided by 10000.
Input
The input consists of K + 1 lines.
The first line contains two integers N and K (3 ≦ N ≦ 100, 1 ≦ K ≦ N) separated by a space.
On the (i+1)-th line (1 ≦ i ≦ K), two integers A
i
and B
i
(1 ≦ A
i
≦ N, 1 ≦ B
i
≦ 3) are written separated by a space. This indicates that the pasta for the A
i
-th day has already been decided, and if B
i
= 1, it is tomato sauce, if B
i
= 2, it is cream sauce and if B
i
= 3, it is basil sauce. A
i
(1 ≦ i ≦ K) are all different. It is guaranteed that there is at least one plan that satisfies the conditions in the input data given.
Output
Output the number of plans that satisfy the conditions, divided by 10000 and output the remainder in one line.
Input and Output Examples
Input Example 1
5 3
3 1
1 1
4 2
Output Example 1
6
In Example 1, you plan dinner for 5 days. The pasta for the 1st and 3rd days is tomato sauce, and the pasta for the 4th day is cream sauce. You cannot choose the same pasta for three or more consecutive days. There are 6 plans that satisfy these conditions.
Day 1
Day 2
Day 3
Day 4
Day 5
Plan 1
1
2
1
2
1
Plan 2
1
2
1
2
2
Plan 3
1
2
1
2
3
Plan 4
1
3
1
2
1
Plan 5
1
3
1
2
2
Plan 6
1
3
1
2
3
In this table, 1 represents tomato sauce, 2 represents cream sauce, and 3 represents basil sauce.
Input Example 2
20 5
10 2
4 3
12 1
13 2
9 1
Output Example 2
2640
In Example 2, there are 4112640 plans that satisfy the conditions. The remainder when divided by 10000 is 2640, which is outputted.
Problem Name: Fun Card Game
Problem Description: There are many cards with integers from 1 to 1000 written on them. Anna and Bruno play a game using these cards as follows.
Anna has a pile of
A
cards, and Bruno has a pile of
B
cards. Anna creates a new pile by discarding any number of cards from her
A
cards (she can discard zero cards as well). Bruno creates a new pile from his
B
cards by discarding some cards from the top (he can discard zero cards as well) and some cards from the bottom (he can also discard zero cards). However, the order of the remaining cards is not changed when they're discarded. If the two piles created in this way are the same, the score of both players is equal to the number of cards in one of the piles. Here, the two piles are said to match if they have the same number of cards
n
and the integers written on the
i
-th card from the top (1 ≤
i
≤
n
) are all the same.
For example, suppose Anna has a pile of 5 cards with the integers 1, 2, 3, 4, and 5 written from the top, and Bruno has a pile of 4 cards with the integers 3, 1, 4, and 1 written from the top. In this case, if Anna discards the cards 2, 3, and 5 and Bruno discards the card 3 from the top and the card 1 from the bottom, the two piles match. There are two cards remaining in one of the piles, so both players score 2 points.
Your task is to find the maximum score that the two players can get.
Constraints
1 ≤
A
≤ 5000
1 ≤
B
≤ 5000
The integers written on the cards are between 1 and 1000, inclusive.
Input
The input is given in the following format:
In the first line, two integers
A
and
B
are given separated by a space.
In the second line,
A
integers are given separated by a space. The
i
-th integer (1 ≤
i
≤
A
) represents the integer written on the
i
-th card from the top of Anna's pile.
In the third line,
B
integers are given separated by a space. The
j
-th integer (1 ≤
j
≤
B
) represents the integer written on the
j
-th card from the top of Bruno's pile.
Output
Print the maximum score that both players can get in a line.
Scoring
For 10% of the test cases,
A
and
B
satisfy
A
≤ 10 and
B
≤ 10.
For 50% of the test cases,
A
≤ 100 and
B
≤ 100.
Sample Input and Output
Sample Input 1
5 4
1 2 3 4 5
3 1 4 1
Sample Output 1
2
This input corresponds to the example in the problem statement.
Sample Input 2
6 5
4 1 5 2 3 4
4 5 4 2 3
Sample Output 2
3
In this input, there are two ways for the two players to get a score of 3. If Anna discards the cards 1, 2, and 3 and Bruno discards the cards 4 and 5 from the top, the two piles of cards become 4, 4, 3, which results in a score of 3. Another way is that Anna discards the cards 1, 5, and 4 and Bruno discards the cards 4 and 2 from the top, which results in the same score of 3.
The problem statement and test data are based on those of
International Olympiad in Informatics Japan
.
Problem Name: Number Guessing Game (Unique number)
Problem
Problem Description: JOI and his friends decided to play a game. N players participate in this game. The rules of the game are as follows:
Each player writes any integer between 1 and 100 on a card and submits it. If a player writes a unique number, the player earns the same number of points as the number written on the card. If more than one player writes the same number, no points are awarded.
JOI and his friends played this game three times. Write a program to find the total score earned by each player in all three games when the numbers written by each player in all three games are given.
Input
The input consists of N + 1 lines.
The first line contains an integer N (2 ≦ N ≦ 200) that represents the number of players.
The i-th line (1 ≦ i ≦ N) among the following N lines contains three integers separated by a space, which represent the numbers written by the i-th player in the first, second, and third games, respectively.
Output
The output consists of N lines.
The i-th line (1 ≦ i ≦ N) should contain an integer representing the total score earned by the i-th player in all three games.
Sample Input and Output
Sample Input 1
5
100 99 98
100 97 92
63 89 63
99 99 99
89 97 98
Sample Output 1
0
92
215
198
89
In Sample Input 1, the total scores of each player are as follows:
Player 1:   0 +   0 +   0 =   0
Player 2:   0 +   0 +  92 =  92
Player 3:  63 +  89 +  63 = 215
Player 4:  99 +   0 +  99 = 198
Player 5:  89 +   0 +   0 =  89
Sample Input 2
3
89 92 77
89 92 63
89 63 77
Sample Output 2
0
63
63
The problem statement and the test data used in the automatic judging system are provided by the
Japan Committee for the International Olympiad in Informatics
.
Problem Name: Signboard
Problem
Problem Description: JOI decided to create a signboard for his store.
There are N old signboards with characters written at equal intervals. JOI wants to create a signboard by erasing some characters from the old signboard. The remaining character string becomes the name of the store, and the remaining characters should be arranged at equal intervals. Only one old signboard can be used to create a signboard, and the old signboard must not be cut or connected.
Given the name of the store and information about N old signboards, create a program to determine the number of signboards that JOI can create. If multiple signboards can be created from a single old signboard, consider only one signboard can be created.
Input
The input consists of 2 + N lines.
The first line contains an integer N
(1 &leqq; N &leqq; 100)
, which represents the number of old signboards.
The second line contains a string consisting of 3 or more and 25 or fewer lowercase alphabet letters, which represents the name of the store.
Of the next N lines, the i-th line
(1 &leqq; i &leqq; N)
contains a string consisting of 1 or more and 100 or fewer lowercase alphabet letters, which represents the character string written on the i-th old signboard.
Output
Output an integer that represents the number of signboards that JOI can create.
Sample Input and Output
Input Example
4
bar
abracadabra
bear
bar
baraxbara
Output Example
3
The name of the store is bar.
On the first old signboard, the string abracadabra is written. A signboard can be created by erasing all characters except for the 2nd, 6th, and 10th characters.
On the second old signboard, if the 2nd character is erased, the string bar can be created, but the remaining characters are not arranged at equal intervals.
On the third old signboard, a signboard can be created without erasing any characters.
From the fourth old signboard, there are two ways to create a signboard. One way is to erase all characters except for the 1st, 2nd, and 3rd characters. The other way is to erase all characters except for the 6th, 7th, and 8th characters.
Therefore, JOI can create signboards from the first, third, and fourth old signboards, so the output is 3.
The problem statement and test data for the automatic judge are provided by the
Japan Committee for the International Olympiad in Informatics (JOI)
.
Problem Name: Problem 3
Problem Description: The first line of the input file contains a positive integer n (n≧3),
and the following n lines contain different positive integers a1, ..., an, each one at a time.
Arrange the permutations made by selecting two different numbers from a1, ..., an in ascending order (as numbers),
and output the third one.
However,
even if a
1
= 1 and a
4
= 11, a
1
a
4
and a
4
a
1
are considered to be different permutations.
Also,
1≦a
i
≦10000 (i=1, ..., n) and 3≦n≦10
4
.
Put a line break at the end of the output file.
Input/Output Examples
Input Example 1
3
2
7
5
Output Example 1
52
Input Example 2
4
17
888
1
71
Output Example 2
171
The problem statement and test data used in the automatic judgment are the problem statement and test data created and published by the Japan Information Olympiad Committee.
Problem Name: Problem 4
Problem Description: Given n points P1, ..., Pn on the plane, find the two points that are closest to each other.
The first line of the input file contains an integer n.
From the second line to the n+1-th line, there are two positive integers x and y on each line, separated by a single space.
The x and y on the i+1-th line represent the x-coordinate and y-coordinate of P
i
, respectively.
Find the two points that are closest to each other among these n points, and output the square of the distance between them.
However,
2≤n≤500000, -10000≤x≤10000, -10000≤y≤10000,
and in three of the five input files, n≤100.
It is also assumed that all coordinates are different in any input file.
Make sure to include a line break code at the end of the output file.
Examples
Example 1
2
0 0
1 1
Output Example 1
2
Example 2
3
5 5
0 0
-3 -4
Output Example 2
25
The problem statement and test data used in the automatic judge are problem statements and scoring test data created and published by the Japan Information Olympiad Committee.
Problem Name: Problem 1
Problem Description: Data has been collected counting the number of cars that pass through the entrance and exit of a tunnel every minute for n minutes. The data consists of n+2 lines, and each line contains the following information:
The first line contains the positive integer n, indicating that the survey lasted n minutes.
The second line contains the positive integer m, indicating that there were m cars in the tunnel at the beginning of the survey.
The (2+i)th line (i = 1, 2, ... , n) contains the number of cars that passed through the entrance and exit during the minute starting from i-1 minutes after the start of the survey, separated by a single space.
Let S
j
be the number of cars in the tunnel j minutes after the start of the survey ( j=0, 1, 2, ... , n ). Output the maximum value of S
j
. If S
j
becomes negative at any point, output 0, indicating an error. It is guaranteed that n is at most 10000, and the number of cars passing through the entrance and exit of the tunnel per minute is at most 100.
Remember to include a line break at the end of the output file.
Sample Input and Output
Sample Input 1
3
2
2 3
2 3
4 1
Sample Output 1
3
Sample Input 2
3
2
2 3
2 4
4 1
Sample Output 2
0
Sample Input 3
3
2
2 3
2 3
1 0
Sample Output 3
2
The problem statement and test data used in the automatic judging system are provided by the
Japan Olympiad in Informatics
.
Problem Name: Problem 5
Problem Description: IOI Jewelry Store is planning to sell necklaces made of beads.
There are n different colors of beads,
and they want to make a necklace of r beads by selecting at least m of each color,
and then put the beads into a jewelry box for sale.
They want to offer every possible combination of colors, but the store owner is worried that they may need an impractical number of jewelry boxes.
Write a program to output the number of jewelry boxes needed instead of the store owner.
n, m, and r are integers, and 0 ≦ m ＜ n ≦ r ≦ 10000.
The input file contains one line with n, m, and r separated by spaces.
In three of the five input files, n ≦ 10.
In the output file, make sure to include a newline character at the end of the output.
Input/Output Examples
Input Example 1
2 0 3
Output Example 1
4
Input Example 2
3 1 4
Output Example 2
3
Input Example 3
4 2 5
Output Example 3
0
The problem statement and test data for the automatic judging system are provided by the
Information-technology Promotion Agency, Japan
.
Problem Name: Problem 1: Average Score
Problem
Problem Description: Five students, Taro, Jiro, Saburo, Shiro, and Hanako, participated in the classes at JOI High School.
In this class, a final exam was conducted, which all five students took. Students who got 40 or more points in the final exam got the same score as the final exam score. All students who scored less than 40 points in the final exam took supplementary classes and got their score increased to 40.
Write a program that calculates the average score of the five students when the scores of the five students' final exams are given.
Input
The input consists of five lines, with one integer written on each line.
The score of Taro's final exam is written on the 1st line.
The score of Jiro's final exam is written on the 2nd line.
The score of Saburo's final exam is written on the 3rd line.
The score of Shiro's final exam is written on the 4th line.
The score of Hanako's final exam is written on the 5th line.
The score of the final exam is an integer between 0 and 100, inclusive.
The score of the final exam is a multiple of 5.
The average score of the five students is always an integer.
Output
Output an integer representing the average score of the five students on a single line.
Input and Output Examples
Sample Input 1
10
65
100
30
95
Sample Output 1
68
In Sample Input 1, since the final exam scores of Taro and Shiro are less than 40 points, their scores are 40 points. Jiro, Saburo and Hanako scored 65, 100 and 95 points respectively. The total score of the five students is 340, so the average score is 68.
Sample Input 2
40
95
0
95
50
Sample Output 2
64
The problem statement and test data used in the automatic judging system are created and published by the
Information-technology Promotion Agency, Japan
.
Problem Name: Problem 2: Vote
Problem
Problem Description: It has been decided that a global sports event will be held in Tokyo in 20XX. Programming contests are enjoyed worldwide as a sport, and there is a possibility that they will be adopted as a competition. It was found out that in order to determine the adopted competition, a screening committee was created. The following is what was found out about the screening committee.
For the screening committee, a list of N candidate competitions arranged in order of interest was created. The i-th most interesting competition is written on the i-th line from the top of the list. Let's call it competition i. The cost A
i
required to hold competition i is also written.
In addition, the screening committee is composed of M members from member 1 to member M. Member j has his own screening criterion B
j
, and he votes for the most interesting competition among the competitions that require cost less than or equal to B
j
.
For any member's screening criteria, there was at least one competition whose required cost was less than or equal to the screening criteria. Therefore, all members voted once.
Only one competition gained the most votes.
Create a program that finds the number of the competition that received the most votes when given a list of competitions and information about the members.
Input
The input consists of 1 + N + M lines.
The first line contains integers N and M (1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000), which represent the number of competitions and number of members, respectively.
Among the following N lines, the i-th line (1 ≤ i ≤ N) contains an integer A
i
(1 ≤ A
i
≤ 1000), which represents the cost required to hold competition i.
Among the following M lines, the j-th line (1 ≤ j ≤ M) contains an integer B
j
(1 ≤ B
j
≤ 1000), which represents the screening criterion for member j.
In the input data provided, it is guaranteed that all members voted once and only one competition gained the most votes.
Output
Output the number of the competition that received the most votes on a line.
Examples
Sample Input 1
4 3
5
3
1
4
4
3
2
Sample Output 1
2
In Example 1, there are four competitions and three members. The cost for each of the four competitions is 5, 3, 1, and 4, respectively.
Member 1's screening criterion is 4. The most interesting competition among the competitions that cost 4 or less is competition 2.
Member 2's screening criterion is 3. The most interesting competition among the competitions that cost 3 or less is competition 2.
Member 3's screening criterion is 2. The most interesting competition among the competitions that cost 2 or less is competition 3.
Therefore, competition 2 received 2 votes and competition 3 received 1 vote. The competition that received the most votes is competition 2, so 2 is outputted.
Sample Input 2
6 6
3
1
4
1
5
9
2
6
5
3
5
9
Sample Output 2
1
In Example 2, competition 1 received 5 votes and competition 2 received 1 vote. The competition that received the most votes is competition 1, so 1 is outputted.
The problem statement and test data for the automatic judge are provided by the
Information-technology Promotion Agency, Japan
.
Problem Name: Baumkuchen
Problem Description: JOI, Joh, and Mii are about to have a snack. Today's snack is Baumkuchen, which is the favorite snack of all three.
Baumkuchen is a cylindrical pastry as shown below. To divide it among the three of them, JOI needs to make three cuts along the radius and divide it into three pieces. However, since this Baumkuchen is as hard as real wood, it is not easy to cut with a knife. Therefore, this Baumkuchen already has $N$ pre-cut marks, and JOI can only cut it at the marked positions. When the cuts are numbered clockwise from 1 to $N$, the size of the portion between the $i$-th and the $(i+1)$-th cuts $(1 \leq i \leq N-1)$ is $A_i$, and the size of the portion between the $N$-th cut and the 1st cut is $A_N$.
Figure 1: Example of Baumkuchen where $N = 6, A_1 = 1, A_2 = 5, A_3 = 4, A_4 = 5, A_5 = 2$, and $A_6 = 4$
Problem
Given the number of pre-cut marks $N$ and the sizes of the portions $A_1, A_2, ..., A_N$, create a program that outputs the maximum size of the smallest piece when the Baumkuchen is divided into three pieces.
Input
The following data should be read from standard input:
The first line contains an integer $N$, which represents the number of pre-cut marks on the Baumkuchen.
Each of the following $N$ lines contains an integer $A_i$ $(1 \leq i \leq N)$ which represents the size of the portion between the $i$-th and the $(i+1)$-th cuts. When $i=N$, $A_i$ represents the size of the portion between the $N$-th cut and the 1st cut.
Output
Output an integer that represents the maximum size of the smallest piece when the Baumkuchen is divided into three pieces.
Constraints
All input data satisfy the following conditions:
$3 \leq N \leq 100000$
$1 \leq A_i \leq 1000000000 \ (1 \leq i \leq N)$
Examples
Example 1
Input:
6
1
5
4
5
2
4

Output:
6
Figure 2: The best way to cut the Baumkuchen is to cut it at the 1st, 3rd, and 5th pre-cut marks.
Example 2
Input:
30
1
34
44
13
30
1
9
3
7
7
20
12
2
44
6
9
44
31
17
20
33
18
48
23
19
31
24
50
43
15

Output:
213
The problem statement and test data are provided by
the Information-technology Promotion Agency (IPA), Japan
.