ZeroJudge G798: 帶動商機 (Business)

某街道上最近新開了幾間商店,相較於原本就已存在的商店,這些新開商店的人潮較為稀少。當地的經理見此情況,決定舉辦一些活動來吸引人潮,好讓新興商店也能夠逐漸茁壯。

在經過試辦活動幾週之後,經理觀察每間商店的拜訪人數,發現了以下的現象:

  • 若該商店 X 今日拜訪人數較相鄰商店多,且相鄰商店只有一間,則相鄰商店隔天的拜訪人數會增加商店 X 今日拜訪人數的 10% (無條件捨去)。
  • 若該商店 X 今日拜訪人數較相鄰商店多,但相鄰商店數有兩間,則拜訪人數較商店 X 人數少的商店隔天的拜訪人數會增加商店 X 今日拜訪人數的 5% (無條件捨去)。

舉例來說,若該街道由左至右有五間商店,今日的拜訪人數如下:

ZeroJudge G798 解說用圖

依據經理觀察到的變化趨勢,明天的拜訪人數將會變成:

ZeroJudge G798 解說用圖-運算結果

給定一條街道上的各商店今日的拜訪人數以及經過天數,請你撰寫程式幫忙計算經過指定天數後每間商店的預期拜訪人數。

範例測資

範例輸入範例輸出
輸入第一行包含若干個 (不超過 30 個) 整數 S (1 ≤ S ≤ 90000),代表由左至右每間商店的今日拜訪人數,最後以 0 代表該街道結尾,不列入計算範圍。第二行有一個整數 N (1 ≤ N ≤ 100),代表經過天數。請輸出經過 N 天之後,各商店預期的人潮數量,兩個數字間以一個空白隔開。
10 200 0
1
30 200
100 95 90 0
1
100 105 94
10 100 90 95 0
2
20 105 104 100
79 43 56 554 21 15 0
6
87 105 218 554 183 39
514 215 262 211 0
100
22114 23626 23453 21891

解題思路

將資料收到一個 Vector<int>num中,將 i 等於第一個位置和最後一個位置分開來計算。宣告一個一模一樣的陣列 current,進行相加的時候是使用原始的資料但是要加到 current,舉例:current[i+1] += num[i] / 10。每次結束一天的運算時要 num.assign(current.begin(), current.end())。最後輸出 num 中的資料。

範例程式碼-ZeroJudge G798: 帶動商機 (Business)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int S;
    vector<int>num;
    while (cin >> S && S != 0)
    {
        num.push_back(S);
    }
    int N;
    cin >> N;
    vector<int>current;
    current.assign(num.begin(), num.end());
    for (int i = 0; i<N; i++)
    {
        for (int j = 0; j<num.size(); j++)
        {
            if (j == 0)
            {
                if (num[j] > num[j+1]) current[j+1] += num[j]/10;
                continue;
            }
            if (j == int(num.size())-1)
            {
                if (num[j] > num[j-1]) current[j-1] += num[j]/10;
                continue;
            }
            if (num[j] > num[j+1]) current[j+1] += num[j]/20;
            if (num[j] > num[j-1]) current[j-1] += num[j]/20;
        }
        num.clear();
        num.assign(current.begin(), current.end());
    }
    for (int i = 0; i<num.size(); i++)
    {
        cout << num[i] << " ";
    }
    cout << "\n";
}

//ZeroJudge G798
//Dr. SeanXD

發佈留言