吳邦一程設練習 #3

ccu_practice_3.md

吳邦一程設練習 #3 (Week 9 to Week 12)

w09a.cpp

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

using namespace std;

bool solve() {
    int D;
    int na, nb, nc;
    int va, vb, vc;

    cin >> D >> na >> nb >> nc >> va >> vb >> vc;
    // scanf("%d %d %d %d %d %d %d", &D, &na, &nb, &nc, &va, &vb, &vc);

    for (int i = 0; i <= na; i++) {
        if (D - i * va < 0) // D - i*va is decreasing when i++
            return false;

        for (int j = 0; j <= nb; j++) {
            int r = D - i * va - j * vb;
            if (r < 0)
                break;

            if (vc == 0 && r == 0)
                return true;
            else if (vc != 0 && r % vc == 0 && r / vc <= nc)
                return true;
        }
    }
    return false;
}

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

    int T;
    cin >> T;
    // scanf("%d", &T);

    while (T--) {
        cout << (solve() ? "yes" : "no") << "\n";
        // if (solve())
        //     puts("yes");
        // else
        //     puts("no");
    }

    return 0;
}

w09a_dp.cpp

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

using namespace std;

int main() {
    int T;
    cin >> T;

    while (T--) {
        int D;
        cin >> D;
        int n[4];
        int v[4];
        n[0] = v[0] = -1;
        for (int i = 1; i <= 3; i++)
            cin >> n[i];
        for (int i = 1; i <= 3; i++)
            cin >> v[i];

        bool dp[4][D+1];
        memset(dp, false, sizeof(dp));
        dp[0][0] = true;

        for (int i = 1; i <= 3; i++) {
            // dp[i][w] = any(dp[i-1][w - v[i] * k] for 0 <= k <= n[i])
            for (int w = 0; w <= D; w++) {
                dp[i][w] = false;
                for (int k = 0; k <= n[i]; k++) {
                    if (w - v[i] * k < 0)
                        break;
                    if (dp[i - 1][w - v[i] * k]) {
                        dp[i][w] = true;
                        break;
                    }
                }
            }
        }

        // for (int i = 0; i <= 3; i++) {
        //     for (int j = 0; j <= D; j++)
        //         cout << dp[i][j] << ", ";
        //     cout << endl;
        // }

        if (dp[3][D])
            cout << "yes\n";
        else
            cout << "no\n";
    }

    return 0;
}

w09b.cpp

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

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];

        int dp[N][2]; // dp[i][0] 不去；dp[i][1] 去。
        memset(dp, -1, sizeof(dp));
        dp[0][0] = 0;
        dp[0][1] = data[0];
        for (int i = 1; i < N; i++) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + data[i];
        }

        cout << max(dp[N-1][0], dp[N-1][1]) << endl;
    }

    return 0;
}

w09c.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

int dp[1000+1][2];

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

    int T;
    cin >> T;

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

        int r[N+1];
        int parent[N+1];
        int children_cnt[N+1];
        int dp[N+1][2]; // dp[i][0] 不去, dp[i][1] 去

        memset(r, -1, sizeof(r));
        memset(parent, -1, sizeof(parent));
        memset(children_cnt, 0, sizeof(children_cnt));
        memset(dp, 0, sizeof(dp));

        r[1] = R1;

        for (int i = 2; i <= N; i++) {
            cin >> parent[i] >> r[i];
            children_cnt[parent[i]]++;
        }

        queue<int> q;
        for (int i = 1; i <= N; i++)
            if (children_cnt[i] == 0)
                q.push(i);

        while (!q.empty()) {
            int v = q.front(); q.pop();
            int p = parent[v];

            dp[v][0] += 0;
            dp[v][1] += r[v];

            dp[p][0] += max(dp[v][0], dp[v][1]);
            dp[p][1] += dp[v][0];

            if (--children_cnt[p] == 0)
                q.push(p);
        }

        // for (int i = 1; i <= N; i++)
        //     cout << dp[i][0] << ", " << dp[i][1] << endl;

        cout << max(dp[1][0], dp[1][1]) << endl;
    }

    return 0;
}

w09d.cpp

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

using namespace std;

typedef pair<long long, long long> pll;
typedef long long ll;

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

    int T;
    cin >> T;

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

        vector<pll> data(N);
        for (int i = 0; i < N; i++) {
            cin >> data[i].first >> data[i].second;
        }

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

        ll cnt = 0;
        ll end = data[0].second;
        ll start = data[0].first;

        int idx = 1;
        for(;;) {
            while (idx < N && data[idx].first <= end) {
                end = max(end, data[idx].second);
                idx++;
            }

            if (idx >= N) {
                cnt += end - start;
                break;
            }

            cnt += end - start;
            start = data[idx].first;
            end = data[idx].second;
        }

        cout << cnt << endl;
    }

    return 0;
}

w10a.cpp

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

using namespace std;

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

        int enemy[N];
        int us[N];
        for (int i = 0; i < N; i++)
            cin >> enemy[i];
        for (int i = 0; i < N; i++)
            cin >> us[i];

        sort(enemy, enemy + N);
        sort(us, us + N);

        int win_cnt = 0;
        int enemy_idx = N - 1;
        for (int us_idx = N - 1; us_idx >= 0; us_idx--) {
            while (enemy_idx >= 0 && enemy[enemy_idx] >= us[us_idx])
                enemy_idx--;

            if (enemy_idx == -1)
                break;

            // cout << enemy[enemy_idx] << ", " << us[us_idx] << endl;
            win_cnt++;
            enemy_idx--;
        }

        cout << win_cnt << endl;
    }

    return 0;
}

w10b.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cctype>
#include <sstream>
using namespace std;

int main() {
    string inp;
    while (getline(cin, inp)) {
        int start = 0;
        int end = 0;
        int len = inp.length();

        while (start < len) {
            end = start;
            while (isdigit(inp[end]))
                end++;

            istringstream iss(inp.substr(start, end - start));
            int N;
            iss >> N;

            start = end;
            while (end < len && !isdigit(inp[end]))
                end++;

            string token = inp.substr(start, end - start);
            while(N--)
                cout << token;

            start = end;
        }

        cout << endl;
    }

    return 0;
}

w10c.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;
}

w10d.cpp

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

using namespace std;

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

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

        long long data[N][N];
        for (int row = 0; row < N; row++)
            for (int col = 0; col < N; col++)
                cin >> data[row][col];

        long long dp[N][N];
        memset(dp, -1, sizeof(dp));
        dp[0][0] = data[0][0];
        for (int row = 1; row < N; row++)
            dp[row][0] = dp[row - 1][0] + data[row][0];
        for (int col = 1; col < N; col++)
            dp[0][col] = dp[0][col-1] + data[0][col];
        for (int row = 1; row < N; row++)
            for (int col = 1; col < N; col++)
                dp[row][col] = max(dp[row-1][col], dp[row][col-1]) + data[row][col];
        cout << dp[N-1][N-1] << endl;
    }

    return 0;
}

w11a.cpp

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

using namespace std;

bool dp[200][200000];
int n[200];
int w[200];
int query[50];

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

    int T;
    cin >> T;

    while (T--) {
        memset(dp, false, sizeof(dp));
        memset(n, -1, sizeof(n));
        memset(w, -1, sizeof(w));
        memset(query, -1, sizeof(query));

        int N, M;
        cin >> N >> M;

        for (int i = 0; i < N; i++)
            cin >> w[i];
        for (int i = 0; i < M; i++)
            cin >> query[i];

        int m = *max_element(query, query+M);

        // 0/1 knapsack : dp[i][j] = any(dp[i-1][j-w[i]], dp[i-1][j]);
        dp[0][0] = true;
        dp[0][w[0]] = true;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= m; j++) {
                if (j - w[i] < 0)
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = dp[i-1][j-w[i]] | dp[i-1][j];
            }
        }

        int cnt = 0;
        for (int i = 0; i < M; i++)
            if (dp[N-1][query[i]])
                cnt++;

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

    return 0;
}

w11b.cpp

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

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

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

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

        vector<int> dp(V, -1);
        dp[0] = w[0];
        for (int i = 1; i < V; i++) {
            int flag = 1;

            // i 的來源為「將 i 的某個是 1 的位元轉 0」的這些值 。
            int m = -1;
            while (flag <= i) {
                if ((i & flag) != 0)
                    m = max(m, dp[i ^ flag]);
                flag = flag << 1;
            }

            dp[i] = m + w[i];
        }

        cout << dp[V-1] << "\n";
    }

    return 0;
}

w11c.cpp

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

using namespace std;

int dp[50 + 2][50 + 2];
int data[50 + 2];

int solve(int left, int right) {
    if (dp[left][right] != -1)
        return dp[left][right];

    if (left + 1 == right)
        return (dp[left][right] = 0);

    dp[left][right] = 10000000;
    for (int c = left + 1; c < right; c++) {
        int value = solve(left, c) + solve(c, right) +
                    (data[right] - data[left]);
        dp[left][right] = min(dp[left][right], value);
    }

    return dp[left][right];
}

// 題目與 GCJ 2009 Round 1C: Bribe the Prisoner 同構。
// 參 https://gist.github.com/Whispering/03d0b3f62b3cd2f63d2e
// 為處理方便，加入一個切割點在最左及一個切割點在最右。
// 這樣使得 solve(left, right) 是一個 (left, right) 開區間, 轉移方程式較好寫。
// 再使用 top-down dp 及可。

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

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

        memset(dp, -1, sizeof(dp));
        memset(data, -1, sizeof(data));

        int N;
        cin >> N;

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

        cout << "The minimum cutting is " << solve(0, N+1) << ".\n";
    }

    return 0;
}

w12a.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

int last_pos[2000];

int main() {
    ios::sync_with_stdio(false);
    
    int N;
    while (cin >> N) {
        if (N == 0) break;
        
        memset(last_pos, -1, sizeof(last_pos));
        int min_len = 10000000;
        int result_start = -1;
        int result_end = -1;
        int value = -1;
        
        for (int i = 0; i < N; i++) {
            int inp;
            cin >> inp;
            
            if (last_pos[inp] == -1){
                last_pos[inp] = i;
                continue;
            }
            
            int len = i - last_pos[inp] + 1;
            if (len < min_len) {
                min_len = len;
                result_start = last_pos[inp];
                result_end = i;
                value = inp;
            }
            
            last_pos[inp] = i;
        }
        
        if (min_len == 10000000)
            cout << "No solution\n";
        else
            cout << "(" << result_start << "," << result_end << "):" 
                 << value << "\n";

    }
    return 0;
}

w12b.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

int first_pos[2000];

int main() {
    ios::sync_with_stdio(false);
    
    int N;
    while (cin >> N) {
        if (N == 0) break;
        
        memset(first_pos, -1, sizeof(first_pos));
        int max_len = 1;
        int result_start = -1;
        int result_end = -1;
        int value = -1;
        
        for (int i = 0; i < N; i++) {
            int inp;
            cin >> inp;
            
            if (first_pos[inp] == -1)
                first_pos[inp] = i;
            else if (i - first_pos[inp] + 1 > max_len) {
                max_len = i - first_pos[inp] + 1;
                result_start = first_pos[inp];
                result_end = i;
                value = inp;
            }
        }
        
        if (max_len == 1)
            cout << "No solution\n";
        else
            cout << "(" << result_start << "," << result_end << "):" 
                 << value << "\n";

    }
    return 0;
}