2024 愚人節題目集 Day 7 - 社區高中

題目 & 題序 by AaW

Cjtsai 是大電神，都會寫 Rust，幫都在混的 AaW 賺到 YTP 的獎金
賺到錢之後，為了讓錢滾錢，cjtsai 決定開一間名為建中的學店，販售各大社區高中文憑。
已知，cjtsai 總共販售

m

種文憑，一個月會有

n

個客人光顧。
為了維護市場機制同時最大化獲利，cjtsai 打算利用一個函數來動態決定每種文憑的價格。
但是，出這題的 AaW 公民沒學好，所以他要亂掰一個函數。
已知，cjtsai 會為第

x

種文憑定義一個基本價格

p_{x}

第 i 位顧客要購買第

a_{i}

種文憑

b_{i}

張，他的期待價格為

c_{i}

，視野範圍為

d_{i}

第 i 位顧客的成交價格

k_{i}

為期待價格

c_{i}

、市場行情價為

g (a_{i}, d_{i}, i)

，基本價格

p_{a_{i}}

的平均（無條件捨去到整數位），
同時定義市場行情價為第

d_{i}

個人到第

i - 1

個人所購買第

a_{i}

種文憑的成交單價(

k_{j}

)加權平均數（無條件捨去到整數位），
即

g (a_{i}, d_{i}, i) = ⌊ \frac{\sum_{j = d_{i}}^{i} (a_{j} == a_{i}) \times k_{j} \times b_{j}}{\sum_{j = d_{i}}^{i} b_{j}} ⌋

若第

d_{i}

個人到第

i - 1

個人都沒有購買第

a_{i}

種文憑，則市場行情價為

0

透過上述公式，我們可以輕鬆得知，cjtsai 的總獲利就是

\sum_{i = 1}^{n} b_{i} \times k_{i}

，輕鬆賺大錢ㄋㄚ～

然而cjtsai在估算行情價時忘記把房租成本算進去了。我們都知道，建中附近房東不是省油的燈，每次都一直漲租金漲到把電搞垮。cjtsai的房東也不例外，他看cjtsai賺了很多錢，決定提高房租。
已知，房東會派人檢查 cjtsai 總共有多少客戶，以及估計第 i 個顧客的總消費額

w_{i}

，並且將房租定義為

\sum_{i = 1}^{n} ⌊ 0.9 \times w_{i} ⌋

。
cjtsai 忙著賺大錢和交女朋友，於是請 AaW 幫他寫一個程式計算他總共會獲利或虧損多少錢。
但 AaW 不會寫 code ，寫出來的 code 一堆 bug ，你可以幫他除蟲嗎？

以下為 AaW 所寫的 code
在 edit distance 30 以內將其修改正確，可獲得 50 分
在 edit distance 3 以內將其修改正確，可獲得 100 分
edit distance 計算方式請見 hint 欄位

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cerr << x << endl;

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, s, l = true;
    cin >> n >> m;
    vector<int> p(m+1);
    for (int i = 1; i <= m; ++i) cin >> p[i];

    // sum of profit
    s = 0;

    // pre sum array of product a_i
    vector<vector<int>> pre(m+1, vector<int>(n+1, 0));
    vector<vector<int>> cnt(m+1, vector<int>(n+1, 0));

    for (int i = 1; i <= n; ++i) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        int g;
        if (cnt[a][i-1] - cnt[a][d-1] <= 0) g = 0;
        else g = (pre[a][i-1] - pre[a][d-1]) / (cnt[a][i-1] - cnt[a][d-1]);

        int k = (c + g + p[a]) / 3;
        pre[a][i] = pre[a][i-1] + b * k;
        cnt[a][i] = cnt[a][i-1] + b;
        for (int j = 1; j <= m; ++j) {
            if (j != a) {
                pre[j][i] = pre[j][i-1];
                cnt[j][i] = cnt[j][i-1];
            }
        }
        s += b * k;
    }

    // debug output
    // int e = 0;
    // for (int i = 1; i <= m; ++i) {
    //        e += pre[i][n];
    // }
    // debug(e);

    // caculate shop rent
    auto shop = [&](){
        int value = 0;
        float percent = 0.9;
        for (int i = 1; i <= n; ++i) {
            int w; cin >> w;
            // use minus because shop rent reduce profit; 
            value -= floor(w * percent);
        }
        return value;
    }();

    cout << shop + s << endl;

    return 0;
}