吳邦一程設練習 #2

ccu_practice_2.md

吳邦一程設練習 #2 (Week 5 to Week 8)

w5a.cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    while (N--) {
        int M;
        cin >> M;

        vector<int> data(M);
        for (int i = 0; i < M; i++)
            cin >> data[i];

        int max_sum_so_far = 0;
        int max_sum = 0;
        for (int i = 0; i < M; i++) {
            max_sum_so_far = max(0, max_sum_so_far + data[i]);
            max_sum = max(max_sum, max_sum_so_far);
        }

        cout << max_sum << endl;
    }

    return 0;
}

w5b.cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        vector<ll> data(N);
        for (int i = 0; i < N; i++)
            cin >> data[i];

        sort(data.begin(), data.end());

        ll sum = 0;
        ll waiting = 0;
        for (int i = 0; i < N; i++) {
            waiting += data[i];
            sum += waiting;
            waiting += data[i];
        }

        cout << sum << endl;
    }

    return 0;
}

w5c.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

struct Job {
    int duration;
    int deadline;
};

void solve(vector<Job>& data) {
    sort(data.begin(), data.end(), [&](const Job& a, const Job& b) {
        return a.deadline < b.deadline;
    });

    int current_time = 0;
    for (size_t i = 0; i < data.size(); i++) {
        if (current_time + data[i].duration > data[i].deadline) {
            cout << "No\n";
            return;
        }

        current_time = current_time + data[i].duration;
    }

    cout << "Yes\n";
}

int main() {
    ios::sync_with_stdio(false);

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        vector<Job> data(N);
        for (int i = 0; i < N; i++)
            cin >> data[i].duration;
        for (int i = 0; i < N; i++)
            cin >> data[i].deadline;

        solve(data);
    }

    return 0;
}

w6a.cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    int N;
    while (cin >> N) {
        if (N == 0) break;

        vector<int> data(N);
        for (int i = 0; i < N; i++)
            cin >> data[i];

        sort(data.begin(), data.end());

        // O(n^2 * lg(n)) solution
        int cnt = 0;
        for (int i = 0; i < N - 2; i++) {
            for (int j = i+1; j < N - 1; j++) {
                int sum = data[i] + data[j];
                auto start = data.begin() + j + 1;
                auto it = lower_bound(start, data.end(), sum);
                cnt += (it - start);
            }
        }

        // O(n^2 * lg(n)) solution, hand-made lower_bound
        // int cnt = 0;
        // for (int i = 0; i < N - 2; i++) {
        //     for (int j = i+1; j < N - 1; j++) {
        //         int sum = data[i] + data[j];
        //
        //         int lb = j + 1;
        //         int ub = N - 1;
        //         while (lb <= ub) {
        //             int mid = (lb + ub) / 2;
        //             if (data[mid] < sum) lb = mid + 1;
        //             else ub = mid - 1;
        //         }
        //
        //         cnt += lb - (j + 1);
        //     }
        // }

        // O(n^3) solution
        // int cnt = 0;
        // for (int i = 0; i < N - 2; i++) {
        //     for (int j = i + 1; j < N - 1; j++) {
        //         for (int k = j + 1; k < N; k++) {
        //             if (data[i] + data[j] > data[k])
        //                 cnt++;
        //         }
        //     }
        // }

        cout << cnt << endl;
    }

    return 0;
}

w6b.cpp

#include <iostream>
#include <queue>
#include <algorithm>
#include <functional>

using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);

    int T;
    cin >> T;

    while (T--) {
        int N, M;
        cin >> N >> M;

        priority_queue< ll, vector<ll>, greater<ll> > pq;
        for (int i = 0; i < M; i++)
            pq.push(0);

        for (int i = 0; i < N; i++) {
            ll task;
            cin >> task;

            ll top = pq.top();
            pq.pop();

            pq.push(top + task);
        }

        while (pq.size() > 1)
            pq.pop();

        cout << pq.top() << "\n";
    }

    return 0;
}

w6c.cpp

#include <iostream>
#include <queue>
#include <algorithm>
#include <functional>

using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);

    int T;
    cin >> T;

    while (T--) {
        int N, M;
        cin >> N >> M;

        priority_queue< ll, vector<ll>, greater<ll> > pq;
        for (int i = 0; i < M; i++)
            pq.push(0);

        for (int i = 0; i < N; i++) {
            ll task;
            cin >> task;

            ll top = pq.top();
            pq.pop();

            pq.push(top + task);
        }

        while (pq.size() > 1)
            pq.pop();

        cout << pq.top() << "\n";
    }

    return 0;
}

w7a.cpp

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <functional>

using namespace std;

typedef long long ll;

ll solve(const ll M, const vector<ll>& task) {
    priority_queue< ll, vector<ll>, greater<ll> > pq;
    for (int i = 0; i < M; i++)
        pq.push(0);

    int N = task.size();
    for (int i = 0; i < N; i++) {
        ll top = pq.top();
        pq.pop();

        pq.push(top + task[i]);
    }

    while (pq.size() > 1)
        pq.pop();

    return pq.top();
}

int main() {
    ios::sync_with_stdio(false);

    int T;
    cin >> T;

    while (T--) {
        ll N, D;
        cin >> N >> D;

        vector<ll> task(N);
        ll max_ = -1;
        for (int i = 0; i < N; i++) {
            cin >> task[i];
            max_ = max(max_, task[i]);
        }


        if (D < max_) {
            cout << "-1\n";
            continue;
        }


        ll lb = 1;
        ll ub = N;

        while (lb <= ub) {
            ll mid = (lb + ub) / 2;
            if (solve(mid, task) <= D) ub = mid - 1;
            else lb = mid + 1;
        }

        cout << lb << "\n";

    }

    return 0;
}

w7b.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cctype>

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    string inp;
    while (getline(cin, inp)) {
        for (size_t i = 0; i < inp.length(); i++) {
            if (islower(inp[i]))
                inp[i] = 'Z' - (inp[i] - 'a');
            else if (isupper(inp[i]))
                inp[i] = 'z' - (inp[i] - 'A');
            else if (isdigit(inp[i]))
                inp[i] = ((inp[i] == '9') ? '0' : inp[i] + 1);
        }
        cout << inp << "\n";
    }

    return 0;
}

w7c.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        vector<int> parent(N);
        for (int i = 1; i < N; i++)
            cin >> parent[i];

        vector<bool> is_marked(N, false);
        int cnt = 0;
        for (int i = N-1; i > 0; i--) {
            if (is_marked[i])
                cnt++;
            else
                is_marked[parent[i]] = true;
        }

        if (is_marked[0])   // root
            cnt++;

        cout << cnt << "\n";
    }

    return 0;
}

w8a.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <functional>

using namespace std;

typedef pair<int, int> pii;

int main() {
    ios::sync_with_stdio(false);

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        vector<pii> data;

        for (int i = 0; i < N; i++) {
            int w, h;
            cin >> w >> h;
            data.push_back(pii(w, h));
            data.push_back(pii(h, w));
        }

        // Compare pii.first first then pii.second
        sort(data.begin(), data.end(), greater<pii>());

        int total = data[0].second;
        for (int i = 1; i < 2 * N; i++) {
            if (data[i].first < data[i - 1].first)
                total += data[i].second;
        }

        cout << total << "\n";
    }

    return 0;
}

w8b.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <queue>
#include <functional>

using namespace std;

typedef pair<int, int> pii;

void solve(vector<pii>& data) {
    sort(data.begin(), data.end());

    int end = 0;
    int cnt = 0;

    // end = 0 is special case
    // data[idx].first <= 0 instead of 1
    const size_t N = data.size();
    size_t idx = 0;
    while (idx < N) {
        int new_end = -1;
        while(idx < N && data[idx].first <= ((end == 0) ? 0 : end + 1)) {
            new_end = max(new_end, data[idx].second);
            idx++;
        }

        // Need not to check new_end == -1, since the problem guarentee
        // there's a solution.

        end = new_end;
        cnt++;

        if (end == 199) break;
    }

    cout << cnt << "\n";
}

int main() {
    ios::sync_with_stdio(false);

    int T;
    cin >> T;

    string temp;
    getline(cin, temp); // eat the endl
    getline(cin, temp); // eat the first empty line

    while (T--) {
        vector<pii> data;

        string inp;
        while (true) {
            if (!(getline(cin, inp)) || inp.length() == 0) break;

            istringstream iss(inp);
            int a, b;
            iss >> a >> b;
            data.push_back(pii(min(a, b), max(a, b)));
        }

        solve(data);
    }

    return 0;
}

w8c.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    int N;
    while (cin >> N) {
        if (N == 0) break;

        int data[N][2];
        for (int i = 0; i < N; i++) {
            cin >> data[i][0] >> data[i][1];
        }

        int dp[N][2];
        dp[0][0] = abs(data[0][0] - 1000);
        dp[0][1] = abs(data[0][1] - 1000);
        for (int i = 1; i < N; i++) {
            dp[i][0] = min(dp[i-1][0] + abs(data[i][0] - data[i-1][0]),
                            dp[i-1][1] + abs(data[i][0] - data[i-1][1]));
            dp[i][1] = min(dp[i-1][0] + abs(data[i][1] - data[i-1][0]),
                            dp[i-1][1] + abs(data[i][1] - data[i-1][1]));

            //cout << dp[i][0] << ", " << dp[i][1] << endl;
        }

        cout << min(dp[N-1][0], dp[N-1][1]) << "\n";
    }

    return 0;
}