Difference between revisions of "4 October 2018: ANZAC Round 3"

From UMCPC Wiki
Jump to navigation Jump to search
(Added sample solutions to some problems G, H, I and J.)
 
(Added solution for problem L.)
Line 147: Line 147:
 
     }
 
     }
 
     cout << ans << endl;
 
     cout << ans << endl;
 +
}
 +
</syntaxhighlight>
 +
 +
== Problem L: Tree Disagreement ==
 +
<syntaxhighlight lang="c++">
 +
#include <bits/stdc++.h>
 +
 +
using namespace std;
 +
 +
int main() {
 +
    int N;
 +
 +
    scanf("%d", &N);
 +
 +
    vector<int> H(N), W(N);
 +
   
 +
    for (int i = 0; i < N; i++) {
 +
        scanf("%d", &H[i]);
 +
        H[i]--;
 +
    }
 +
    for (int i = 0; i < N; i++) {
 +
        int node;
 +
        scanf("%d", &node);
 +
        W[node-1] = i;
 +
    }
 +
 +
    int ans = 0;
 +
    for (int i = 0, j = N-1; i < N; i++) {
 +
        if (W[H[i]] > j) ans++;
 +
        j = W[H[i]];
 +
    }
 +
 +
    printf("%d\n", ans + (N > 1) + (N > 1 && W[H[1]] == N-2));
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>

Revision as of 00:01, 4 October 2018

Links

Problem G: Errands

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int N, M, K;
vector<pair<int, int>> G[100000];

ll shortest_path(int from, int to) {
    vector<ll> dist(N, -1);
    priority_queue<
        pair<ll, int>, 
        vector<pair<ll, int>>, 
        greater<pair<ll, int>>> pq;

    dist[from] = 0;
    pq.emplace(0, from);

    while (!pq.empty()) {
        auto p = pq.top(); pq.pop();
        auto d = p.first;
        auto u = p.second;
        if (d != dist[u]) continue;
        if (u == to) break;
        for (auto edge : G[u]) {
            auto v = edge.first;
            auto c = edge.second;
            if (dist[v] == -1 || dist[u] + c < dist[v]) {
                dist[v] = dist[u] + c;
                pq.emplace(dist[v], v);
            }
        }
    }

    return dist[to];
}

int main() {
    scanf("%d%d%d", &N, &M, &K);
    for (int i = 0; i < M; i++) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        u--;
        v--;
        G[u].emplace_back(v, c);
        G[v].emplace_back(u, c);
    }
    ll ans = 0;
    int prev = 0;
    for (int i = 0; i < K; i++) {
        int next;
        scanf("%d", &next);
        ans += shortest_path(prev, --next) + 1;
        prev = next;
    }
    printf("%lld\n", ans);
}

Problem H: Catch

#include <bits/stdc++.h>

using namespace std;

int A, B, C;

int main() {
    scanf("%d%d%d", &A, &B, &C);
    
    if (A > B + C || B > C + A || C > A + B) {
        printf("No\n");
    }

    printf("Yes\n");

    double X = (C*C - B*B + A*A)/(2.0*A);
    double Y = sqrt(C*C - X*X);
    
    printf("%d %d\n", 0, 0);
    printf("%d %d\n", A, 0);
    printf("%f %f\n", X, Y);
}

Problem I: HonkMobile

#include <bits/stdc++.h>

using namespace std;

int N, K;
int H[1000], P[1000];
int DP[1001][1001];

int main() {
    scanf("%d%d", &N, &K);
    for (int i = 0; i < K; i++) {
        scanf("%d%d", &H[i], &P[i]);
    }
    for (int i = 1; i <= N; i++) {
        DP[i][0] = INT_MAX;
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= K; j++) {
            DP[i][j] = min(DP[i][j-1], P[j-1] + DP[max(0, i - H[j-1])][j]);
        }
    }
    printf("%d\n", DP[N][K]);
}

Problem J: Tying Strings

#include <bits/stdc++.h>

using namespace std;

string S;
int N;

string tie(int k) {
    ostringstream oss;
    for (int i = 0; i < N - 2*k; i++) {
        oss << S[i];
    }
    for (int i = N - 2*k, j = N - 1; i < j; i++, j--) {
        oss << min(S[i], S[j]);
    }
    return oss.str();
}

int main() {
    cin >> S;
    N = S.size();
    string ans = S;
    for (int i = 0; i <= N / 2; i++) {
        ans = min(ans, tie(i));
    }
    cout << ans << endl;
}

Problem L: Tree Disagreement

#include <bits/stdc++.h>

using namespace std;

int main() {
    int N;

    scanf("%d", &N);

    vector<int> H(N), W(N);
    
    for (int i = 0; i < N; i++) {
        scanf("%d", &H[i]);
        H[i]--;
    }
    for (int i = 0; i < N; i++) {
        int node;
        scanf("%d", &node);
        W[node-1] = i;
    }

    int ans = 0;
    for (int i = 0, j = N-1; i < N; i++) {
        if (W[H[i]] > j) ans++;
        j = W[H[i]];
    }

    printf("%d\n", ans + (N > 1) + (N > 1 && W[H[1]] == N-2));
}