作者： chenchen

Bessie has recently gotten into chemistry. At the moment, she has two different colors 1 and 2 of various liquids that don't mix well with one another. She has two test tubes of infinite capacity filled with N (1≤N≤10⁵ ) units each of some mixture of liquids of these two colors. Because the liquids don’t mix, once they settled, they divided into layers of separate colors. Because of this, the two tubes can be viewed as strings f₁f₂…f_N and s₁s₂…s_N where f_i represents the color of the liquid that is i units from the bottom of the first tube, and s_i represents the color of the liquid that is i units from the bottom of the second tube. It is guaranteed that there is at least one unit of each color of liquid.

Bessie wants to separate these liquids so that each test tube contains all units of one color of liquid. She has a third empty beaker of infinite capacity to help her in this task. When Bessie makes a "pour", she moves all liquid of color i
at the top of one test tube or beaker into another.

Determine the minimum number of pours to separate all the liquid into the two test tubes, and the series of moves needed to do so. It does not matter which test tube ends up with which color, but the beaker must be empty..

There will be T (1≤T≤10) test cases, with a parameter P for each test case.

Suppose the minimum number of pours to separate the liquids into the original tubes is M.

If P=1, you will receive credit if you print only M.
If P=2, you will receive credit if you print an integer A such that M≤A≤M+5, followed by A lines that construct a solution with that number of moves. Each line should contain the source and the destination tube (1, 2, or 3for the beaker). The source tube must be nonempty before the move and a tube may not be poured into itself.
If P=3, you will receive credit if you print M, followed by a valid construction using that number of moves.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T, the. number of test cases. For each test case, the next line contains N and P representing the amount each test tube is initially filled to, and the query type. The following line contains f₁f₂f₃…f_N representing the first test tube. f_i∈{1,2} and f₁ represents the bottom of the test tube. The subsequent line contains s₁,s₂,…,s_N representing the second test tube.s_i∈{1,2} and s₁ represents the bottom of the test tube.

It is guaranteed that there will be at least one 1 and one 2 across both input strings.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, you will print a single number representing the minimum pours to separate the liquid in the test tubes. Depending on the query type, you may also need to provide a valid construction.

SAMPLE INPUT:

6
4 1
1221
2211
4 2
1221
2211
4 3
1221
2211
6 3
222222
111112
4 3
1121
1222
4 2
1121
1222

SAMPLE OUTPUT:

4
4
1 2
1 3
2 1
3 2
4
1 2
1 3
2 1
3 2
1
2 1
5
2 3
1 2
1 3
1 2
3 1
6
2 3
1 2
1 3
1 2
2 1
3 2

In the first three test cases, the minimum number of pours to separate the tubes is 4. We can see how the following moves separate the test tubes:

Initial state:

1: 1221
2: 2211
3:

After the move "1 2":

1: 122
2: 22111
3:

After the move "1 3":

1: 1
2: 22111
3: 22
After the move "2 1":
1: 1111
2: 22
3: 22

After the move "3 2":

1: 1111
2: 2222
3:

In the last test case, the minimum amount of pours is 5. However, since P=2, the given construction with 6 moves is valid since it is within 5 pours from the optimal answer.

SCORING:

Inputs 2-6: P=1
Inputs 7-11: P=2
Inputs 12-21: No additional constraints.

Additionally, it is guaranteed that T=10 for all inputs besides the sample.

Problem credits: Suhas Nagar

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Note: The time limit for this problem is 2.5s, 1.25 times the default.

Note: The large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

The Paris Moolympics are coming up and Farmer John is training his team of cows in archery! He has set up the following exercise on the 2D coordinate plane.

There are N(1≤N≤4⋅10⁴) axis-aligned rectangular targets and 4N cows. Every cow must be assigned to a different target vertex. At moment i, for 1≤i≤N:

1.Target i appears.
2.The 4 cows assigned to its vertices shoot at them.
3.If a cow's shot passes through the interior of the target before it hits the assigned vertex or misses, the cows fail the exercise.
4.The target disappears to make space for the next one.

Each cow is located on the y-axis (x=0), and each target is a rectangle where target i has its lower left coordinate at and its upper right coordinate at The coordinates also satisfy (Note: X₁ is the same for every target).

In addition, each cow has a "focus" angle they are working on. Therefore, they will turn at a specific angle when shooting. Given that their shot travels in a straight line from their position towards their assigned vertex, the trajectory of cow i's arrow can be described by s_i (0<|s_i |<10⁹), the slope of the trajectory.

So that he can carefully examine the cows' technique, Farmer John wants to minimize the distance between the furthest cows. If Farmer John were to optimally assign each cow to a target vertex and place them on the y-axis, can you help him determine what the minimum distance between the furthest cows would be or if the cows will always fail the exercise?

Each input contains T (1≤T≤10) independent test cases. The sum of N across all test cases is guaranteed to not exceed 4⋅10⁴.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T(1≤T≤10), the number of independent test cases. Each test case is described as follows:The first line of each test case contains two integers, N and X₁, the number of targets and the left-most x-coordinate of the targets respectively.

This is followed by N lines with the i-th line consisting of three integers,and , the lower y-coordinate, the upper y-coordinate, and the right x-coordinate of the i-th target respectively.

The last line consists of 4N integers,s₁,s₂,…,s_4N where s_i denotes the slope of cow i's shot trajectory.

OUTPUT FORMAT (print output to the terminal / stdout):

The minimum possible distance between the furthest cows or −1 if the cows will always fail the exercise.

SAMPLE INPUT:

3
2 1
1 3 6
4 6 3
1 -1 2 -2 3 -3 4 -4
2 1
1 3 6
4 6 3
1 1 2 2 3 3 4 4
2 1
1 3 3
4 6 3
1 -1 2 -2 3 -3 4 -4

SAMPLE OUTPUT:

17
-1
11

One optimal assignment for test case 1 is the following target vertices for cows 1-8 respectively:
(6,1),(6,3),(3,4),(3,6),(1,4),(1,3),(1,6),(1,1)

This gives the following y locations for cows 1-8 respectively:
−5,9,−2,12,1,6,2,5

This gives a minimum distance of 12−(−5)=17.

One reason the second test case is impossible is because it is impossible to shoot the vertex at (6,3)(the top right vertex of target 1) without the shot passing through the interior of target 1.

SCORING:

Input 2: |s_i|is the same for all 1≤i≤4N.
Input 3-9: The sum of N across all testcases is at most 1000.
Inputs 10-15: No additional constraints.

Problem credits: Suhas Nagar

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

In her free time, Bessie likes to dabble in experimental physics. She has recently discovered a pair of new subatomic particles, named mootrinos and antimootrinos. Like standard matter-antimatter pairs, mootrinos and antimootrinos annihilate each other and disappear when they meet. But what makes these particles unique is that they switch their direction of motion (while maintaining the same speed) whenever Bessie looks at them.

For her latest experiment, Bessie has placed an even number N (2≤N≤2⋅10⁵) of these particles in a line. The line starts with a mootrino on the left and then alternates between the two types of particles, with the i-th particle located at position p_i (0≤p₁<⋯<p_N≤10¹⁸). Mootrinos initially move right while antimootrinos initially move left, and the i-th particle moves with a constant speed of s_i units per second (1≤s_i≤10⁹).

Bessie makes observations at the following times:

First, 1 second after the start of the experiment.
Then 2 seconds after the first observation.
Then 3 seconds after the second observation.
...
Then n+1 seconds after the n-th observation.

During each observation, Bessie notes down which particles have disappeared.

This experiment may take an extremely long time to complete, so Bessie would like to first simulate its results. Given the experiment setup, help Bessie determine when (i.e., the observation number) she will observe each particle disappear! It may be shown that all particles will eventually disappear.

INPUT FORMAT (input arrives from the terminal / stdin):

Each input contains T(1≤T≤10) independent test cases.Each test case consists of three lines. The first line contains N, the second line contains p_1,…, p_N, and the third line contains s₁…,s_N.

It is guaranteed that the sum of all N does not exceed 2⋅10⁵.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output the observation number for each particle's disappearance, separated by spaces.

SAMPLE INPUT:

4
2
1 11
1 1
2
1 12
1 1
2
1 11
4 6
2
1 11
4 5

SAMPLE OUTPUT:

9 9
11 11
1 1
3 3

For the first test, Bessie observes the following during the first 8
observations:

The mootrino (initially moving right) appears at positions 2→0→3→−1→4→−2→5→−3.
The antimootrino (initially moving left) appears at positions 10→12→9→13→8→14→7→15.

Then right at observation 9, the two particles meet at position 6 and annihilate each other.

For the second test, the antimootrino starts 1 additional unit to the right, so the two particles meet at position 6.5 half a second before observation 11.

Note that we only care about observation numbers, not times or positions.

SAMPLE INPUT:

2
4
1 3 5 8
1 1 1 1
4
1 4 5 8
1 1 1 1

SAMPLE OUTPUT:

1 1 3 3
7 2 2 7

For the first test:

The two leftmost particles meet at position 2 right at observation 1.
The two rightmost particles meet at position 6.5 half a second before observation 3.

SCORING:

Input 3 satisfies N=2.
Input 4 satisfies N≤2000 and p_i≤10⁴ for all cows.
Inputs 5-7 satisfy N≤2000.
Inputs 8-12 satisfy no additional constraints.

Problem credits: Aryansh Shrivastava, Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Farmer John's N(1≤N≤5⋅10⁵)cows are lined up in a circle. The ith cow has a bucket with integer capacity a_i (1≤a_i≤10⁹) liters. All buckets are initially full.

Every minute, cow i will pass all the milk in their bucket to cow i+1 for 1≤i<N, with cow N passing its milk to cow 1. All exchanges happen simultaneously (i.e., if a cow has a full bucket but gives away x liters of milk and also receives x
liters, her milk is preserved). If a cow's total milk ever ends up exceeding ai, then the excess milk will be lost.

After each of 1,2,…,N minutes, how much total milk is left among all cows?

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.

The next line contains integers a₁,a₂,…,a_N

OUTPUT FORMAT (print output to the terminal / stdout):

Output N lines, where the i-th line is the total milk left among all cows after i
minutes.

SAMPLE INPUT:

6
2 2 2 1 2 1

SAMPLE OUTPUT:

8
7
6
6
6
6

Initially, the amount of milk in each bucket is [2,2,2,1,2,1].

After 1 minute, the amount of milk in each bucket is [1,2,2,1,1,1] so the total amount of milk is 8.

After 2 minutes, the amount of milk in each bucket is [1,1,2,1,1,1] so the total amount of milk is 7.

After 3 minutes, the amount of milk in each bucket is [1,1,1,1,1,1] so the total amount of milk is 6.

After 4 minutes, the amount of milk in each bucket is [1,1,1,1,1,1] so the total amount of milk is 6.

After 5 minutes, the amount of milk in each bucket is [1,1,1,1,1,1] so the total amount of milk is 6.

After 6 minutes, the amount of milk in each bucket is [1,1,1,1,1,1] so the total amount of milk is 6.

SAMPLE INPUT:

8
3 8 6 4 8 3 8 1

SAMPLE OUTPUT:

25
20
17
14
12
10
8
8

After 1 minute, the amount of milk in each bucket is [1,3,6,4,4,3,3,1] so the total amount of milk is 25.

SAMPLE INPUT:

10
9 9 10 10 6 8 2 1000000000 1000000000 1000000000

SAMPLE OUTPUT:

2000000053
1000000054
56
49
42
35
28
24
20
20

SCORING:

Inputs 4-5: N≤2000
Inputs 6-8: a_i ≤2
Inputs 9-13: All a_i are generated uniformly at random in the range [1,109].
Inputs 14-23: No additional constraints.

Problem credits: Chongtian Ma, Alex Liang, Patrick Deng

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

**Note: The time limit for this problem is 3s, 1.5x the default. The memory limit for this problem is 512MB, twice the default.**

Farmer John would like to promote his line of Bessla electric tractors by showcasing Bessla's network of charging stations. He has identified N
(2≤N≤5⋅10⁴) points of interest labeled 1…N, of which the first C
(1≤C<N) are charging stations and the remainder are travel destinations. These points of interest are interconnected by M (1≤M≤10⁵) bidirectional roads, the i-th of which connects distinct points u_i and v_i (1≤u_i,v_i≤N) and has length ℓ_i miles (1≤ℓ_i ≤10⁹).

A Bessla can travel up to 2R miles (1≤R≤10⁹) on a single charge, allowing it to reach any destination within R miles of a charging station. A destination is deemed well-connected if it is reachable from at least K(1≤K≤10) distinct charging stations. Your task is to assist Farmer John in identifying the set of well-connected travel destinations.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains five space-separated integers N, M, C, R, and K. Each of the following M lines contains three space-separated integers u_i, v_i, and ℓ_i such that u_i≠v_i.

The charging stations are labeled 1,2,…,C. The remaining points of interest are all travel destinations.

OUTPUT FORMAT (print output to the terminal / stdout):

First, output the number of well-connected travel destinations on a single line. Then, list all well-connected travel destinations in ascending order, each on a separate line.

SAMPLE INPUT:

3 3 1 4 1
1 2 3
1 3 5
2 3 2

SAMPLE OUTPUT:

1
2

We have one charging station at 1. From this charging station, we can reach point 2(since it is distance 3 away from 1), but not point 3 (since it is distance 5 away from 1). Thus, only point 2 is well-connected.

SAMPLE INPUT:

4 3 2 101 2
1 2 1
2 3 100
1 4 10

SAMPLE OUTPUT:

2
3
4

We have charging stations at 1 and 2, and both points 3 and 4 are within distance 101 of both 1 and 2. Thus, both points 3 and 4 are well-connected.

SAMPLE INPUT:

4 3 2 100 2
1 2 1
2 3 100
1 4 10

SAMPLE OUTPUT:

1
4

SCORING:

Inputs 4 and 5: K=2 and N≤500 and M≤1000.
Inputs 6 and 7: K=2.
Inputs 8-15: No additional constraints.

Problem credits: Alexander Wei

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

**Note: The memory limit for this problem is 512MB, twice the default.**

Bessie is planning an infinite adventure in a land with N (1≤N≤10⁵) cities. In each city i, there is a portal, as well as a cycling time T_i. All T_i's are powers of 2, and T₁+⋯+T_N≤10⁵. If you enter city i's portal on day t, then you instantly exit the portal in C_i,t  mod T_i.

Bessie has Q(1≤Q≤5⋅10⁴) plans for her trip, each of which consists of a tuple (v,t,Δ). In each plan, she will start in city v on day t. She will then do the following Δ times: She will follow the portal in her current city, then wait one day. For each of her plans, she wants to know what city she will end up in.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains two space-separated integers: N, the number of nodes, and Q, the number of queries.

The second line contains N space-separated integers: T₁, T2,…,T_N
(1≤T_i, T_i is a power of 2, and T₁+⋯+T_N≤10⁵).

For i=1,2,…,N, line i+2 contains T_i space-separated positive integers, namely C_i,0,…,c_i,T_i−1(1≤C_i,t≤N).

For j=1,2,…,Q, line j+N+2 contains three space-separated positive integers,v_j,t_j,Δ_j(1≤v_j≤N, 1≤t_j≤10¹⁸, and 1≤Δ_j≤10¹⁸) representing the j
th query.

OUTPUT FORMAT (print output to the terminal / stdout):

Print Q lines. The jth line must contain the answer to the jth query.

SAMPLE INPUT:

5 4
1 2 1 2 8
2
3 4
4
2 3
5 5 5 5 5 1 5 5
2 4 3
3 3 6
5 3 2
5 3 7

SAMPLE OUTPUT:

2
2
5
4

Bessie's first three adventures proceed as follows:

In the first adventure, she goes from city 2 at time 4 to city 3 at time 5, to city 4 at time 6, to city 2 at time 7.
In the second adventure, she goes from city 3 at time 3 to city 4 at time 4, to city 2 at time 5, to city 4 at time 6, to city 2 at time 7, to city 4 at time 8, to city 2 at time 9.

In the third adventure, she goes from city 5 at time 3 to city 5 at time 4, to city 5 at time 5.

SAMPLE INPUT:

5 5
1 2 1 2 8
2
3 4
4
2 3
5 5 5 5 5 1 5 5
2 4 3
3 2 6
5 3 2
5 3 7
5 3 1000000000000000000

SAMPLE OUTPUT:

2
3
5
4
2

SCORING:

Input 3:Δ_j≤2⋅10².
Inputs 4-5: N,∑T_j≤2⋅10³.
Inputs 6-8: N,∑T_j≤10⁴.
Inputs 9-18: No additional constraints.

Problem credits: Brandon Wang

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie has N (2≤N≤300) tiles in a line with ugliness values a₁,a₂,…,a_N in that order (1≤a_i≤10⁶). K(0≤K≤min(N,6)) of the tiles are stuck in place; specifically, those at indices x₁,…,x_K(1≤x₁<x₂<⋯<x_K≤N).

Bessie wants to minimize the total ugliness of the tiles, which is defined as the sum of the maximum ugliness over every consecutive pair of tiles; that is, She is allowed to perform the following operation any number of times: choose two tiles, neither of which are stuck in place, and swap them.

Determine the minimum possible total ugliness Bessie can achieve if she performs operations optimally.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N and K.

The next line contains a₁,…,a_N .

The next line contains the K indices x₁,…,x_K.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the minimum possible total ugliness.

SAMPLE INPUT:

3 0
1 100 10

SAMPLE OUTPUT:

110

Bessie can swap the second and third tiles so that a=[1,10,100], achieving total ugliness max(1,10)+max(10,100)=110. Alternatively, she could swap the first and second tiles so that a=[100,1,10], also achieving total ugliness max(100,1)+max(1,10)=110.

SAMPLE INPUT:

3 1
1 100 10
3

SAMPLE OUTPUT:

110

Bessie could swap the first and second tiles so that a=[100,1,10]
, achieving total ugliness max(100,1)+max(1,10)=110.

SAMPLE INPUT:

3 1
1 100 10
2

SAMPLE OUTPUT:

200

The initial total ugliness of the tiles is max(1,100)+max(100,10)=200
. Bessie is only allowed to swap the first and third tiles, which does not allow her to reduce the total ugliness.

SAMPLE INPUT:

4 2
1 3 2 4
2 3

SAMPLE OUTPUT:
9

SCORING:

Input 5: K=0
Inputs 6-7: K=1
Inputs 8-12: N≤50
Inputs 13-24: No additional constraints
Problem credits: Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie is hard at work preparing test cases for the USA Cowmputing Olympiad February contest. Each minute, she can choose to not prepare any tests, expending no energy; or expend 3^a−1 energy preparing a test cases, for some positive integer a.

Farmer John has D (1≤D≤2⋅10⁵) demands. For the ith demand, he tells Bessie that within the first m_i minutes, she needs to have prepared at least b_i test cases in total (1≤m_i≤10⁶,1≤b_i≤10¹²).

Let eⁱ be the smallest amount of energy Bessie needs to spend to satisfy the first i
demands. Print e₁,…,e_D modulo 10⁹+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains D. The ith of the next D lines contains two space-separated integers m_i and b_i .

OUTPUT FORMAT (print output to the terminal / stdout):

Output D lines, the ith containing e_i mod 10⁹+7.

SAMPLE INPUT:

4
5 11
6 10
10 15
10 30

SAMPLE OUTPUT:

21
21
25
90

For the first test case,

i=1: If Bessie creates [2,3,2,2,2] test cases on the first 5 days, respectively, she would have expended 31+32+31+31+31=21 units of energy and created 11
test cases by the end of day 5.

i=2: Bessie can follow the above strategy to ensure 11 test cases are created by the end of day 5, and this will automatically satisfy the second demand.

i=3: If Bessie creates [2,3,2,2,2,0,1,1,1,1] test cases on the first 10 days, respectively, she would have expended 25 units of energy and satisfied all demands. It can be shown that she cannot expend less energy.

i=4: If Bessie creates 3 test cases on each of the first 10 days she would have expended 32⋅10=90 units of energy and satisfied all demands.
For each i, it can be shown that Bessie cannot satisfy the first i demands using less energy.

SAMPLE INPUT:

2
100 5
100 1000000000000
SAMPLE OUTPUT:
5
627323485

SAMPLE INPUT:

20
303590 482848034083
180190 112716918480
312298 258438719980
671877 605558355401
662137 440411075067
257593 261569032231
766172 268433874550
8114 905639446594
209577 11155741818
227183 874665904430
896141 55422874585
728247 456681845046
193800 632739601224
443005 623200306681
330325 955479269245
377303 177279745225
880246 22559233849
58084 155169139314
813702 758370488574
929760 785245728062

SAMPLE OUTPUT:

108753959
108753959
108753959
148189797
148189797
148189797
148189797
32884410
32884410
32884410
32884410
32884410
32884410
32884410
3883759
3883759
3883759
3883759
3883759
3883759

SCORING:

Inputs 4-5: D≤100 and m_i≤100 for all i
Inputs 6-8: D≤3000
Inputs 9-20: No additional constraints.

Problem credits: Brandon Wang and Claire Zhang

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划