ZeroJudge G798: Business

Recently, several new shops have opened on a certain street. Compared to the existing ones, these new shops have fewer visitors. Seeing this situation, the local manager decided to organize some events to attract crowds, allowing the new shops to gradually thrive.

After a few weeks of trial events, the manager observed the visitation numbers for each shop and noticed the following phenomena:

  • If shop X has more visitors today compared to its adjacent shop, and there is only one adjacent shop, then the visitation number of the adjacent shop will increase by 10% of the visitors to shop X today (rounded down to the nearest whole number) on the following day.
  • If shop X has more visitors today compared to its adjacent shops, and there are two adjacent shops, then the visitation number of the shop with fewer visitors than shop X will increase by 5% of the visitors to shop X today (rounded down to the nearest whole number) on the following day.

For example, if there are five shops on the street from left to right, and today's visitation numbers are as follows:

ZeroJudge G798 解說用圖

Based on the observed trend by the manager, tomorrow's visitation numbers will change as follows:

ZeroJudge G798 解說用圖-運算結果

Given the visitation numbers for each shop on a street today and the number of days that passed, please write a program to calculate the expected visitation numbers for each shop after the specified number of days.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line contains several integers S (not exceeding 30), representing the visitation numbers for each shop from left to right today. It ends with 0, which does not count in the calculation. The second line contains an integer N (1 ≤ N ≤ 100), representing the number of days passed.Please output the expected visitation numbers for each shop after N days, separated by a single space.
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

Thought Process

Receive the data into a vector num, separating the calculations for the first and last positions by setting i equal to the first and last positions. Declare an identical array current, and during addition, use the original data but add to current, like this: current[i+1] += num[i] / 10. After completing the calculations for each day, assign current back to num using num.assign(current.begin(), current.end()). Finally, output the data from num.

Sample Code-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

Comments