# 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) = \lfloor \frac{ \sum \limits_{j = d_i} ^ {i} (a_j == a_i) \times k_j\times b_j}{\sum \limits_{j = d_i} ^ i b_j} \rfloor$
若第 $d_i$ 個人到第 $i-1$ 個人都沒有購買第 $a_i$ 種文憑，則市場行情價為$0$
透過上述公式，我們可以輕鬆得知，cjtsai 的總獲利就是 $\sum \limits_{i = 1} ^ {n} b_i \times k_i$，輕鬆賺大錢ㄋㄚ～

然而cjtsai在估算行情價時忘記把房租成本算進去了。我們都知道，建中附近房東不是省油的燈，每次都一直漲租金漲到把電搞垮。cjtsai的房東也不例外，他看cjtsai賺了很多錢，決定提高房租。
已知，房東會派人檢查 cjtsai 總共有多少客戶，以及估計第 i 個顧客的總消費額 $w_i$，並且將房租定義為 $\sum \limits_{i = 1} ^ {n} \lfloor 0.9 \times w_i \rfloor$。
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;
}