2030: [USACO 2024 February Contest Gold] Problem 2. Milk Exchange

文件提交:无需freopen 内存限制:256 MB 时间限制:2.000 S
评测方式:普通裁判 命题人:
提交:1 解决:1

题目描述

Farmer John's N (1N5105) cows are lined up in a circle. The ith cow has a bucket with integer capacity ai (1ai109) liters. All buckets are initially full.

Every minute, cow i will pass all the milk in their bucket to cow i+1 for 1i<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?

输入

The first line contains N.

The next line contains integers a1,a2,...,aN.

输出

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

样例输入

复制
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.

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: N2000
  • Inputs 6-8: ai2
  • Inputs 9-13: All ai are generated uniformly at random in the range [1,109].
  • Inputs 14-23: No additional constraints.

来源/分类