回分類題庫
h226: G.排隊
關鍵字: NPSC 2020 高中組初賽

測資點 : 6 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 2 Times / 2 Users | Submit : 5 Times / 2 Users | Accepted rate : 100%
題目加入時間 : 2021-09-11 15:08

Content: 简体中文

這天,一款全新的妹妹虛擬實境遊戲即將發售,身為這類遊戲的愛好者——小 Y 為了搶先體驗,他現在身處在一個很長的隊伍中,漫長的等待時間使他非常無聊,所以他決定開始觀察隊伍的排隊現象。

小 Y 觀察到隊伍內總共有 N 個人,一開始隊伍是在筆直的數線上的,第 i 個人的座標為 i。小 Y 也知道自己是這隻隊伍的第 Q + 1 個人,所以他很在意前 Q 個人依序買到遊戲後,隊伍會發生什麼事。

因此,小 Y 接下來會觀察 Q 次事件,第 i 次事件排在隊伍最前面的人,也就是第 i 個人,就會買到遊戲,並離開隊伍,自此這個人的位置便會出現空格,此時隊伍可能會開始移動。

不過常常會有討厭的人待在原地不動(像是滑手機之類的),導致後面的人會因為察覺不到隊伍有移動而無法前進,小 Y 發現對於第 i 次事件,有往前移動的人是還待在原隊伍的前 ki 位(也就是第 i + 1 ∼ i + ki 個人),這 ki 位會不受影響地依序直接移動到前 ki 個位置,也就是座標 1 ∼ ki

小 Y 已經把所有事件的 ki 都紀錄下來了,你可以告訴他,對於每次事件,隊伍內所有人(包含該次事件買到遊戲的人)移動的距離總和是多少呢?當然,我們假設每次事件只有買到遊戲的人和待在原隊伍的前 ki 個人會做移動,且任何人都只會在事件發生時移動。 

Input:

輸入資料第一行有一個正整數 T (1<=T<=3),代表接下來有幾組測試資料。

每組測試資料的第一行有兩個正整數 N, Q,代表隊伍的人數、小 Y 前面排了多少人。

第二行有 Q 個以空格分開的整數 k1, k2, · · · , kQ,代表每次事件,往前移動的人是還待在原隊伍的前 ki 位,若 ki = 0 代表此次事件除了買遊戲的人以外,沒有其他的人移動。 

Output:

對於每組測試資料輸出一行 Q 個數字 d1, d2, · · · , dQ,代表第 i 次事件中,所有人移動的距離總和是 di。數字之間以單一空格隔開,最後一個數字後面必須是一個單一的換行字元。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
10 5
3 4 2 5 3
8 6
3 1 2 1 0 0
1000000000 7
100 1000 10000 8787 888777 98765 123456

Sample Output :

3 6 2 15 3
3 1 5 1 0 5
100 1901 28002 8787 4405105 98765 148148

Hint :

Author :

NPSC 2020 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum