[SHUPC 2024] 彭罗斯水槽

Luogu

IDLGP10318

Time1000ms

Memory256MB

DifficultyP5

2024差分单调栈高校校赛

小 A 在上课时出现了幻觉，他幻想出了若干个水槽，它们环形排列，每一个水槽里的水都会流向下一个水槽（当然在现实里这是不可能的）。于是小 A 开始思考这样一个问题：有 $n$ 个水槽环形排列，每个水槽都有一个容量，初始时水都是满的。接下来每一秒，水槽 $i$ 的水全部转移到 $i+1$ （特殊的，第 $n$ 个水槽的水会转移到第 $1$ 个），如果转移的水超出了容量就会溢出。现在他想知道，在接下来的 $1$ 至 $n$ 秒内，每一秒所有水槽的水量总和。 ## Input 第一行读入一个正整数 $n\ (1\le n\le 10^5)$ ，表示水槽的个数。第二行读入 $n$ 个数字，第 $i$ 个数字 $a_i\ (1\le a_i\le 10^9)$ 表示水槽 $i$ 的容量。 ## Output $n$ 个数字，用空格隔开。分别表示 $1$ 至 $n$ 秒，每一秒所有水槽的水量总和。 [samples]

Samples

Input #1

5
3 2 5 4 3

Output #1

14 12 11 10 10

Input #2

6
171 814 2313 6676 196 897

Output #2

3861 1719 1076 1051 1026 1026

API Response (JSON)

{
  "problem": {
    "name": "[SHUPC 2024] 彭罗斯水槽",
    "description": {
      "content": "小 A 在上课时出现了幻觉，他幻想出了若干个水槽，它们环形排列，每一个水槽里的水都会流向下一个水槽（当然在现实里这是不可能的）。 于是小 A 开始思考这样一个问题： 有 $n$ 个水槽环形排列，每个水槽都有一个容量，初始时水都是满的。接下来每一秒，水槽 $i$ 的水全部转移到 $i+1$ （特殊的，第 $n$ 个水槽的水会转移到第 $1$ 个），如果转移的水超出了容量就会溢出。 现在他想知道",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10318"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 A 在上课时出现了幻觉，他幻想出了若干个水槽，它们环形排列，每一个水槽里的水都会流向下一个水槽（当然在现实里这是不可能的）。\n\n于是小 A 开始思考这样一个问题：\n\n有 $n$ 个水槽环形排列，每个水槽都有一个容量，初始时水都是满的。接下来每一秒，水槽 $i$ 的水全部转移到 $i+1$ （特殊的，第 $n$ 个水槽的水会转移到第 $1$ 个），如果转移的水超出了容量就会溢出。\n\n现在他想知道...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments