CodeEff/ECCO huggingface dataset:
Illumination
Problem Description: Every year at the JOI high school festival, the corridors are decorated with illuminations. The illuminations consist of N light bulbs and the bulbs are arranged in a row from west to east. Each bulb is either on or off.
In the JOI high school warehouse, there is a machine that controls the light bulbs. When the machine is given a continuous sequence of light bulbs in the illumination, it changes all the light bulbs that are on to off and all the light bulbs that are off to on in the specified sequence. However, the machine can only be used once because of its aging.
The students of JOI high school like a sequence of light bulbs in which the light bulbs that are on and the light bulbs that are off are arranged alternately. Therefore, they decided to use the machine once if necessary and create an illumination that includes the longest alternating sequence possible.
Example
For example, suppose the illumination is arranged from west to east as follows:
where ○ represents a light bulb that is on and ● represents a light bulb that is off. When the machine is operated for the four light bulbs from the fourth to the seventh, the illumination becomes as follows:
and the light bulbs from the second to the eighth form a sequence of alternating length 7.
When the machine is operated only for the eighth light bulb, the illumination becomes as follows:
and the light bulbs from the fourth to the tenth form a sequence of alternating length 7.
The maximum length of an alternating sequence that can be created by using the machine only once is 8 or less.
Task
When given the information about the illumination, create a program to calculate the maximum possible length of an alternating sequence that can be included in the light bulb array obtained by using the machine once.
Constraints
2 ≤
N
≤ 100,000: the number of light bulbs that make up the illumination
Input
The following data is read from standard input:
The first line contains the integer
N
.
The second line contains
N
0s or 1s separated by spaces. Each integer represents the state of a light bulb before the machine is operated. The integer represents whether the light bulb is on (1) or off (0), and the integer at position
i
(1 ≤
i
≤
N
) represents the state of the
i
th light bulb from the west.
Output
Print a single integer on a line, which represents the maximum possible length of an alternating sequence that can be created by using the machine once.
Sample Input and Output
Sample Input 1
10
1 1 0 0 1 0 1 1 1 0
Sample Output 1
7
This is the example given in the problem statement.
Sample Input 2
10
1 0 0 0 0 1 0 1 0 1
Sample Output 2
8
When the machine is operated only for the fourth light bulb from the west, a sequence of alternating length 8 can be obtained.
Sample Input 3
5
1 1 0 1 1
Sample Output 3
5
When the machine is operated only for the second to fourth light bulbs from the west, a sequence of alternating length 5 can be obtained.
Sample Input 4
3
0 1 0
Sample Output 4
3
Note that it is possible that the machine is not used.
The problem statement and test data are provided by
the Information Olympiad Japan (IOI)
.
Bubble Sort
Problem Description: Bubble Sort is an algorithm for sorting an array. Suppose you want to sort a sequence A of length N in ascending order. Bubble Sort exchanges adjacent two numbers if their order is broken. This is done while scanning the sequence from the beginning. That is, if Ai > Ai+1, then the two numbers are exchanged. This is repeated N - 1 times to sort the sequence in ascending order.
The number of exchanges by Bubble Sort for a sequence
A
is the number of times integers are exchanged when applying the above algorithm to the sequence
A
. (There may be slight differences in the order, range, and termination conditions of loops in the algorithm and its implementation known as Bubble Sort. However, it is known that the number of integer exchanges when applying the same algorithm to the same sequence does not change due to these differences.)
For example, the following program is a C function that sorts an integer array
a
of length
n
by Bubble Sort.
void bubble_sort(int *a, int n) {
  int i, j;
  for (i = 0; i < n - 1; ++i) {
    for (j = 0; j < n - 1; ++j) {
      if (a[j] > a[j + 1]) {
        /* The following three lines correspond to one integer exchange. */
        int x = a[j];
        a[j] = a[j + 1];
        a[j + 1] = x;
      }
    }
 }
}
Problem
You are given a sequence
A
of length
N
. Let
A'
be a sequence obtained by swapping two integers at any position in
A
exactly once. Write a program to find the minimum number of exchanges performed by Bubble Sort to sort
A'
. (Note that the first two integers to be swapped do not necessarily have to be adjacent.)
Constraints
1 ≤
N
≤ 100,000: the length of the sequence
A
1 ≤
A
i
≤ 1,000,000,000: the size of the integers in the sequence
A
Input
The following data is read from standard input:
In the first line, an integer
N
is written, which represents the length of the sequence
A
.
The i-th line of the following
N
lines (1 ≤
i
≤
N
) contains an integer
A
i
, which represents the i-th integer of the sequence
A
.
Output
Print one integer, the minimum number of exchanges performed by Bubble Sort to sort
A'
, on a single line of standard output.
Scoring
For 10% of the available score,
N
≤ 1,000 and for all
i, j
(1 ≤
i
<
j
≤
N
),
A
i
≠
A
j
.
For 30% of the available score,
N
≤ 5,000 and for all
i, j
(1 ≤
i
<
j
≤
N
),
A
i
≠
A
j
.
For 80% of the available score, for all
i, j
(1 ≤
i
Silk Road
Problem
Problem Description: In the area that is now Kazakhstan, there was an ancient trade route called the "Silk Road". On the Silk Road, there are N + 1 cities, numbered from city 0 to city N from west to east. The distance between city i-1 and city i (1 ≤ i ≤ N) is Di.
JOI will carry silk from city 0 to city N, passing through the cities in order. He must arrive at city N within M days. For each day of the trip, JOI can either move or wait. On a moving day, JOI can move from the current city to the next city to the east in one day. If he is in city i-1 (1 ≤ i ≤ N), he can move to city i. On a waiting day, JOI does not move, and his fatigue does not increase.
Moving is hard work, and JOI gets more and more tired every time he moves. The weather changes every day on the Silk Road, and the worse the weather is, the harder it is to travel. JOI knows that the weather will be C
j
on the j-th day (1 ≤ j ≤ M). If he moves from city i-1 to city i (1 ≤ i ≤ N) on the j-th day, his fatigue will increase by D
i
× C
j
. If he waits, his fatigue will not increase.
JOI wants to move in such a way that he minimizes his fatigue. Find the minimum total fatigue that JOI will accumulate from the start of the trip to the end of the trip, if he reaches city N within M days.
Input
The input consists of 1 + N + M lines.
The first line contains two integers N and M (1 ≤ N ≤ M ≤ 1000), indicating that the Silk Road consists of N + 1 cities and that JOI must carry silk from city 0 to city N within M days.
The i-th line among the following N lines (1 ≤ i ≤ N) contains an integer D
i
(1 ≤ D
i
≤ 1000), indicating that the distance between city i-1 and city i is D
i
.
The j-th line among the following M lines (1 ≤ j ≤ M) contains an integer C
j
(1 ≤ C
j
≤ 1000), indicating that the weather will be bad with C
j
on the j-th day.
Output
Print the minimum total fatigue that JOI will accumulate from the start of the trip to the end of the trip, if he reaches city N within M days, in one line.
Sample Input and Output
Input Example 1
3 5
10
25
15
50
30
15
40
30
Output Example 1
1125
When JOI moves as follows, the total fatigue he accumulates is minimized.
Wait on day 1.
Move from city 0 to city 1 on day 2. The fatigue accumulated on this day is 10 × 30 = 300.
Move from city 1 to city 2 on day 3. The fatigue accumulated on this day is 25 × 15 = 375.
Wait on day 4.
Move from city 2 to city 3 on day 5. The fatigue accumulated on this day is 15 × 30 = 450.
The total fatigue accumulated by JOI is 300 + 375 + 450 = 1125, which is the minimum.
This problem statement and test data are provided by
Japan Olympiad in Informatics
.
Cake 2
Problem Description: JOI-kun and IOI-chan are twins. JOI-kun has been interested in making sweets recently, and today he wanted to bake a cake. However, IOI-chan who noticed the smell came when it was baked, so they decided to share the cake between the two of them.
The cake is circular. Radiant cuts are made from a certain point to cut the cake into
N
pieces, and the pieces are numbered counterclockwise from 1 to
N
. That is, for 1 ≤
i
≤
N
, the
i
-th piece is adjacent to the (
i
-1)-th and (
i
+1)-th pieces (however, the 0-th piece is regarded as the
N
-th piece, and the (
N
+1)-th piece is regarded as the 1st). The size of the
i
-th piece was
A
i
, but since the cutting was very poor,
A
i
became all different values.
Figure 1: Example of a cake (
N
= 5,
A
1
= 2,
A
2
= 8,
A
3
= 1,
A
4
= 10,
A
5
= 9)
JOI-kun and IOI-chan decided to divide these
N
pieces between them. The division is as follows:
First, JOI-kun selects one of the
N
pieces that he likes.
Then, starting from IOI-chan, IOI-chan and JOI-kun take the remaining pieces one by one alternately. However, they can only take pieces that have at least one of the adjacent pieces taken, and when there are multiple pieces that can be taken, IOI-chan takes the largest one and JOI-kun can take any one of them.
JOI-kun wants to maximize the sum of the sizes of the pieces he eventually takes.
Task
Given the number
N
of pieces of cake and information on the sizes of
N
pieces, create a program to find the maximum value of the sum of the sizes of the pieces that JOI-kun can take.
Input
The following input is given in the standard input:
On the first line, an integer
N
is written, indicating that the cake is divided into
N
pieces.
Among the following
N
lines, an integer
A
i
is written on the
i
-th line (1 ≤
i
≤
N
), indicating that the size of the
i
-th piece is
A
i
.
Output
Print an integer on a line in the standard output that represents the maximum value of the sum of the sizes of the pieces that JOI-kun can take.
Constraints
All input data satisfy the following conditions:
1 ≤
N
≤ 2 000.
1 ≤
A
i
≤ 1 000 000 000.
A
i
are all different.
Input and Output Examples
Input Example 1
5
2
8
1
10
9
Output Example 1
18
JOI-kun takes the pieces as follows:
JOI-kun takes the 2nd piece. The size of this piece is 8.
IOI-chan takes the 1st piece. The size of this piece is 2.
JOI-kun takes the 5th piece. The size of this piece is 9.
IOI-chan takes the 4th piece. The size of this piece is 10.
JOI-kun takes the 3rd piece. The size of this piece is 1.
The sum of the sizes of the pieces that JOI-kun took in the end is 8+9+1=18.
Input Example 2
8
1
10
4
5
6
2
9
3
Output Example 2
26
Input Example 3
15
182243672
10074562
977552215
122668426
685444213
3784162
463324752
560071245
134465220
21447865
654556327
183481051
20041805
405079
JOI Park
Problem Description: In preparation for the Olympics to be held in the IOI country in 20XX, it was decided to develop the JOI Park in the IOI country. JOI Park has N squares, and the squares are numbered from 1 to N. There are M roads that connect the squares, and the roads are numbered from 1 to M. Road i (1 ≤ i ≤ M) connects square Ai and square Bi bidirectionally, and its length is Di. It is possible to reach any square from any other square by following some roads.
In the development plan, first, an integer
X
greater than or equal to 0 is chosen, and all squares (including square 1) whose distance from square 1 is less than or equal to
X
are connected by an underground passage. Here, the distance between square
i
and square
j
is the minimum sum of the lengths of the roads that are traveled to go from square
i
to square
j
. The integer
C
related to the cost of building underground passages is determined in the development plan. The cost of building an underground passage is
C × X
.
Next, all roads that connect squares by an underground passage are removed. There is no cost for removing the roads. Finally, all the remaining roads are repaired. The cost of repairing a road of length
d
is
d
. There are no underground passages in the JOI Park before the development plan is implemented. Find the minimum sum of the costs required for development of the JOI Park.
Task
Given the information about the squares in the JOI Park and an integer related to the cost of building underground passages, write a program to find the minimum sum of the costs required for development of the JOI Park.
Input
The data is read from standard input in the following format:
The first line contains three integers
N
,
M
, and
C
, separated by a single space, indicating that there are
N
squares,
M
roads, and the integer related to the cost of building underground passages is
C
.
Among the following
M
lines, the
i
-th line (1 ≤
i
≤
M
) contains three integers
A
i
,
B
i
, and
D
i
, separated by a single space, indicating that road
i
connects square
A
i
and square
B
i
with a length of
D
i
.
Output
Print a single integer to standard output, indicating the minimum sum of the costs required for development of the JOI Park.
Constraints
For all input data, the following conditions hold.
2 ≤
N
≤ 100,000.
1 ≤
M
≤ 200,000.
1 &le
Problem Name: Subject Selection
Problem
Problem Description: JOI took tests of six subjects: physics, chemistry, biology, geology, history, and geography.
Each test was scored out of 100 points.
JOI selects 3 subjects out of physics, chemistry, biology, and geology, and selects 1 subject out of history and geography.
When selecting subjects to maximize the total test score, find the total score of the selected subjects.
Input
The input consists of six lines, with one integer written on each line.
The first line contains the score A for JOI's physics test.
The second line contains the score B for JOI's chemistry test.
The third line contains the score C for JOI's biology test.
The fourth line contains the score D for JOI's geology test.
The fifth line contains the score E for JOI's history test.
The sixth line contains the score F for JOI's geography test.
All integers written are between 0 and 100, inclusive.
Output
Output the total score of the tests that JOI selected on one line.
Sample Input and Output
Sample Input 1
100
34
76
42
10
0
Sample Output 1
228
Sample Input 2
15
21
15
42
15
62
Sample Output 2
140
In Sample Input 1, when JOI selects physics, biology, geology, and history, the total score of the tests is the highest.
The scores for physics, biology, geology, and history are 100, 76, 42, and 10, respectively, so the total score of the selected subjects is 228.
In Sample Input 2, when JOI selects chemistry, biology, geology, and geography, the total score of the tests is the highest.
The scores for chemistry, biology, geology, and geography are 21, 15, 42, and 62, respectively, so the total score of the selected subjects is 140.
Even if JOI selects physics, chemistry, geology, and geography in Sample Input 2, the total score of the selected subjects is still 140.
Created by the Japanese Committee for the International Olympiad in Informatics, "15th JOI Competition (2015-2016) Qualifying Round Task."
Problem Name: Zombie Island
Problem
Problem Description: JOI's island where he lives has been invaded by zombies. JOI decided to escape to a shelter that is set as the safest place on the island.
The island where JOI lives consists of N towns from town 1 to town N, and the towns are connected by roads. There are M roads on the island, and each road connects two different towns. JOI can freely move on the roads in both directions, but cannot go from one town to another through anything other than a road.
Some towns are under zombie control and cannot be visited. A town that can be reached by using S or fewer roads from a town under zombie control is called a "dangerous town." Other towns are called "safe towns."
JOI's house is in town 1, and the shelter is in town N. Towns 1 and N are not under zombie control. Because moving on the island's roads takes time, JOI must stay overnight in a town every time he moves to another town. If he stays in a safe town, he stays at a hotel that is cheaper by P yen, but if he stays in a dangerous town, he stays at a hotel that has excellent security for Q yen. JOI wants to move as cheaply as possible and evacuate to town N. There is no need to stay in towns 1 and N.
Find the minimum total cost of accommodation that JOI needs when he moves from town 1 to town N.
Input
The input is made up of 2 + K + M lines.
The first line contains four integers N, M, K, S (2 ≦ N ≦ 100000, 1 ≦ M ≦ 200000, 0 ≦ K ≦ N - 2, 0 ≦ S ≦ 100000), separated by spaces. This indicates that the island consists of N towns and M roads, and K of the N towns are under zombie control. A town that can be reached by using S or fewer roads from a town under zombie control is called a "dangerous town."
The second line contains two integers P and Q (1 ≦ P ＜ Q ≦ 100000), separated by spaces. This indicates that JOI stays at a hotel that costs P yen in safe towns and stays at a hotel that costs Q yen in dangerous towns.
Among the next K lines, the i-th line (1 ≦ i ≦ K) contains an integer C
i
(2 ≦ C
i
≦ N - 1). This indicates that town C
i
is under zombie control. C
1
, ..., C
K
are all different.
Among the next M lines, the j-th line (1 ≦ j ≦ M) contains two integers A
j
and B
j
(1 ≦ A
j
＜ B
j
≦ N), separated by spaces. This indicates that there is a road between town A
j
and town B
j
. The same pair (A
j
, B
j
) is not written twice or more.
In the input data given, it is guaranteed that you can move only through towns that are not under zombie control from town 1 to town N.
Output
Output the minimum total cost of accommodation that JOI needs when he moves from town 1 to town N in one line.
Note that the output may not necessarily fit within the range of 32-bit signed integers
Problem Name: Microwave
Problem
Problem Description: JOI is trying to warm up a piece of meat from A ℃ to B ℃ using a microwave for meal preparation.
When the temperature of the meat is below 0 ℃, it is frozen.
Also, when the temperature is higher than 0 ℃, it is not frozen.
When the temperature is exactly 0 ℃, the meat can be either frozen or not frozen.
JOI has decided to estimate the time it will take to warm up the meat by assuming the following:
When the meat is frozen and its temperature is less than 0 ℃: it warms up 1 ℃ in C seconds
When the meat is frozen and its temperature is exactly 0 ℃: it takes D seconds to thaw the meat and change it to a non-frozen state.
When the meat is not frozen: it warms up 1 ℃ in E seconds.
Using this estimate, determine how long it will take to warm up the meat to B ℃.
Input
The input consists of five lines, each containing one integer.
The original temperature of the meat A is written on the first line.
The target temperature B is written on the second line.
The time required to warm up the frozen meat by 1 ℃, C, is written on the third line.
The time required to thaw frozen meat, D, is written on the fourth line.
The time required to warm up non-frozen meat by 1 ℃, E, is written on the fifth line.
The original temperature A is between -100 and 100 inclusive, and the target temperature B is between 1 and 100 inclusive, and A ≠ 0 and A < B are satisfied.
The time required to warm up, C, D, and E are all between 1 and 100.
Output
Output the number of seconds required to warm up the meat to B ℃ in a single line.
Examples
Example 1
-10
20
5
10
3
Output 1
120
Example 2
35
92
31
50
11
Output 2
627
In Example 1, the meat is originally frozen at -10 ℃. The time required is as follows:
50 seconds to warm up from -10 ℃ to 0 ℃.
10 seconds to thaw the meat at 0 ℃.
60 seconds to warm up from 0 ℃ to 20 ℃.
Therefore, the total required time is 120 seconds.
In Example 2, the meat is not frozen. Therefore, it takes 627 seconds to warm it up from 35 ℃ to 92 ℃.
The Information Olympiad Japan Committee, "The 16th Japan Information Olympiad JOI 2016/2017 Preliminary Competition Task"
Problem Name: Ridge
Problem
Problem Description: JOI Caldera is a beautiful terrain loved by many mountaineers for its scenic views.
In particular, the view from a place called Ridge is breathtaking.
The land of JOI Caldera is a rectangle with a length of H kilometers north to south and W kilometers east to west.
Divide the land of JOI Caldera into H×W regions, calling them areas, with one kilometer intervals in the north-south and east-west directions.
In each area, the altitude is the same, and the altitudes of different areas are different.
When it rains in a certain area, the rainwater flows into all the areas with lower altitude in the four adjacent areas to the east, west, north, and south of that area.
If there is no such area, the rainwater accumulates in that area.
The same applies to rainwater that flows in from other areas.
The outside of JOI Caldera is surrounded by steep cliffs of the outer ring mountain, so rainwater does not flow out of JOI Caldera.
When rain falls only in a certain area and rainwater accumulates in multiple areas in the end, that area is called the Ridge.
Create a program to find the number of Ridge areas for mountaineers who love scenic views.
Input
The input consists of 1 + H lines.
The first line contains two integers H and W (1 ≦ H ≦ 1000, 1 ≦ W ≦ 1000) separated by a space, which indicate that JOI Caldera spans H kilometers north to south and W kilometers east to west.
The following H lines each contain W integers separated by spaces, representing altitude information.
The integer M
i,j
(1 ≦ M
i,j
≦ H×W) in the i
th
row and j
th
column of the H rows represents the altitude of the area in the i
th
row from the north and the j
th
column from the west in JOI Caldera.
If (i,j) ≠ (k,l), then M
i,j
≠ M
k,l
must be satisfied.
Output
Output the number of Ridge areas on one line.
Examples
Example 1
Input:
3 3
2 9 4
7 5 3
6 1 8
Output:
4
Example 2
Input:
3 5
5 3 8 2 14
9 10 4 1 13
12 7 11 6 15
Output:
4
In Example 1, the four areas with altitudes of 5, 7, 8, and 9 are ridges.
For example, if it rains in an area with an altitude of 9, the rainwater will accumulate in three areas with altitudes of 1, 2, and 3 in the end.
Therefore, the area with an altitude of 9 is the Ridge.
Also, if it rains in an area with an altitude of 6, the rainwater will only accumulate in an area with an altitude of 1.
Therefore, the area with an altitude of 6 is not the Ridge.
In Example 2, the four areas with altitudes of 8, 10, 11, and 12 are ridges.
Problem Name: Pair of Primes
Problem Description: We arrange the numbers between 1 and N (1 <= N <= 10000) in increasing
order and decreasing order like this:
1 2 3 4 5 6 7 8 9 . . . N
N . . . 9 8 7 6 5 4 3 2 1
Two numbers faced each other form a pair. Your task is to compute the number of pairs P such that both
numbers in the pairs are prime.
Input
Input contains several test cases. Each test case consists of an integer N in
one line.
Output
For each line of input, output P .
Sample Input
1
4
7
51
Output for the Sample Input
0
2
2
6