作者： chenchen

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试题答案+详细解析

咨询一对一备赛规划