某街道上最近新開了幾間商店,相較於原本就已存在的商店,這些新開商店的人潮較為稀少。當地的經理見此情況,決定舉辦一些活動來吸引人潮,好讓新興商店也能夠逐漸茁壯。
在經過試辦活動幾週之後,經理觀察每間商店的拜訪人數,發現了以下的現象:
- 若該商店 X 今日拜訪人數較相鄰商店多,且相鄰商店只有一間,則相鄰商店隔天的拜訪人數會增加商店 X 今日拜訪人數的 10% (無條件捨去)。
- 若該商店 X 今日拜訪人數較相鄰商店多,但相鄰商店數有兩間,則拜訪人數較商店 X 人數少的商店隔天的拜訪人數會增加商店 X 今日拜訪人數的 5% (無條件捨去)。
舉例來說,若該街道由左至右有五間商店,今日的拜訪人數如下:
依據經理觀察到的變化趨勢,明天的拜訪人數將會變成:
給定一條街道上的各商店今日的拜訪人數以及經過天數,請你撰寫程式幫忙計算經過指定天數後每間商店的預期拜訪人數。
範例測資
範例輸入 | 範例輸出 |
---|---|
輸入第一行包含若干個 (不超過 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