#PU1402. USACO 2024 February Contest, Gold — Problem 2. Milk Exchange
USACO 2024 February Contest, Gold — Problem 2. Milk Exchange
USACO 2024 February Contest, Gold — Problem 2. Milk Exchange
题目描述
Farmer John's cows are lined up in a circle. The th cow has a bucket with integer capacity liters. All buckets are initially full. Every minute, cow will pass all the milk in their bucket to cow for , with cow passing its milk to cow . All exchanges happen simultaneously (i.e., if a cow has a full bucket but gives away liters of milk and also receives liters, her milk is preserved). If a cow's total milk ever ends up exceeding , then the excess milk will be lost. After each of minutes, how much total milk is left among all cows?
输入格式
The first line contains . The next line contains integers .
输出格式
(见题面原文)
数据范围
Inputs 4-5: Inputs 6-8: Inputs 9-13: All are generated uniformly at random in the range . Inputs 14-23: No additional constraints. Problem credits: Chongtian Ma, Alex Liang, Patrick Deng
样例
样例 1
6
2 2 2 1 2 1
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$.
样例 2
8
3 8 6 4 8 3 8 1
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$.
样例 3
10
9 9 10 10 6 8 2 1000000000 1000000000 1000000000
2000000053
1000000054
56
49
42
35
28
24
20
20