Legendary Players

A direct mapping from player handles to their respective ratings is required. A hash map provides an efficient and clean way to resolve this without writing multiple conditional statements.

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
    unordered_map<string, int> ratings = {
        {"tourist", 3858}, {"ksun48", 3679}, {"Benq", 3658},
        {"Um_nik", 3648}, {"apiad", 3638}, {"Stonefeang", 3630},
        {"ecnerwala", 3613}, {"mnbvmar", 3555}, {"newbiedmy", 3516},
        {"semiexp", 3481}
    };
    string handle;
    cin >> handle;
    cout << ratings[handle] << endl;
    return 0;
}

Measure

Iterate through each position from 0 to N. For a given position, determine the largest digit between 1 and 9 that evenly divides N, and where the position is a multiple of N divided by that digit. If no such digit exists, output a hyphen.

#include <iostream>

using namespace std;

int main() {
    int limit;
    cin >> limit;
    for (int idx = 0; idx <= limit; ++idx) {
        int chosen = -1;
        for (int d = 9; d >= 1; --d) {
            if (limit % d == 0 && idx % (limit / d) == 0) {
                chosen = d;
                break;
            }
        }
        cout << (char)(chosen == -1 ? '-' : '0' + chosen);
    }
    return 0;
}

False Hope

Consider all possible permutations of uncovering the 3x3 grid cells. A disappointment occurs if, within any row, column, or diagonal, the first two uncovered cells share the same value while the third differs. By checking all 9! permutations, we can count the successful outcomes and compute the probability.

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

using namespace std;

int main() {
    vector<int> grid(9);
    for (int i = 0; i < 9; ++i) cin >> grid[i];
    
    vector<int> order = {0, 1, 2, 3, 4, 5, 6, 7, 8};
    int total = 0, success = 0;
    
    vector<vector<int>> lines = {
        {0, 1, 2}, {3, 4, 5}, {6, 7, 8},
        {0, 3, 6}, {1, 4, 7}, {2, 5, 8},
        {0, 4, 8}, {2, 4, 6}
    };
    
    do {
        total++;
        bool disappointed = false;
        vector<int> reveal_time(9);
        for (int i = 0; i < 9; ++i) reveal_time[order[i]] = i;
        
        for (auto& line : lines) {
            int a = line[0], b = line[1], c = line[2];
            vector<pair<int, int>> seq = {
                {reveal_time[a], grid[a]},
                {reveal_time[b], grid[b]},
                {reveal_time[c], grid[c]}
            };
            sort(seq.begin(), seq.end());
            if (seq[0].second == seq[1].second && seq[1].second != seq[2].second) {
                disappointed = true;
                break;
            }
        }
        if (!disappointed) success++;
    } while (next_permutation(order.begin(), order.end()));
    
    printf("%.10f\n", (double)success / total);
    return 0;
}

Minimum Width

Apply binary search on the possible minimum width. For a candidate width, simulate the layout process to count the required number of lines. The lower bound is the length of the longest word, and the upper bound is the sum of all word lengths plus spaces.

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

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> lengths(n);
    long long max_len = 0, total_len = 0;
    for (int i = 0; i < n; ++i) {
        cin >> lengths[i];
        max_len = max(max_len, (long long)lengths[i]);
        total_len += lengths[i];
    }
    
    long long low = max_len, high = total_len + n, ans = high;
    while (low <= high) {
        long long mid = (low + high) / 2;
        long long lines_needed = 1, current_width = 0;
        for (int i = 0; i < n; ++i) {
            if (current_width + lengths[i] <= mid) {
                current_width += lengths[i] + 1;
            } else {
                lines_needed++;
                current_width = lengths[i] + 1;
            }
        }
        if (lines_needed <= m) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

Bus Stops

Since all bus stop periods are at most 8, their least common multiple is 840. Precompute the travel time for all departure times modulo 840. Queries can then be answered in constant time by combining the precomputed offset with the quotient of the departure time divided by 840.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, start_walk, end_walk;
    cin >> n >> start_walk >> end_walk;
    vector<int> periods(n - 1), ride_times(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        cin >> periods[i] >> ride_times[i];
    }
    
    vector<long long> precomputed(840);
    for (int t = 0; t < 840; ++t) {
        long long current_time = t + start_walk;
        for (int i = 0; i < n - 1; ++i) {
            if (current_time % periods[i] != 0) {
                current_time += periods[i] - (current_time % periods[i]);
            }
            current_time += ride_times[i];
        }
        current_time += end_walk;
        precomputed[t] = current_time;
    }
    
    int q;
    cin >> q;
    while (q--) {
        long long query_time;
        cin >> query_time;
        long long base = (query_time / 840) * 840;
        cout << precomputed[query_time % 840] + base << "\n";
    }
    return 0;
}

Fighter Takahashi

The problem restricts the number of medicine nodes to at most 10, suggesting a bitmask DP approach. The state tracks which medicines have been consumed. For each state, we simulate defeating all reachable monsters using a priority queue (greedily fighting weaker monsters first to gain strength). When a medicine is reachable, transitioning to the state that includes it updates the multiplier and potentially unlocks further paths.

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

using namespace std;

const int MAXN = 105;
int node_parent[MAXN], node_type[MAXN];
long long req_strength[MAXN], reward[MAXN];
vector<int> tree[MAXN];
int potion_id[MAXN], total_potions = 0;

struct GameState {
    long long current_power = 0;
    bool visited[MAXN] = {false};
    priority_queue<pair<long long, int>> monsters; // {-strength, node}
};

GameState state_dp[1 << 10];

void expand_monsters(GameState& gs, int start) {
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : tree[u]) {
            if (gs.visited[v]) continue;
            if (node_type[v] == 1) {
                if (gs.current_power >= req_strength[v]) {
                    gs.current_power += reward[v];
                    gs.visited[v] = true;
                    q.push(v);
                } else {
                    gs.monsters.push({-req_strength[v], v});
                }
            } else {
                gs.visited[v] = true;
                q.push(v);
            }
        }
    }
    
    bool changed = true;
    while (changed) {
        changed = false;
        while (!gs.monsters.empty() && gs.current_power >= -gs.monsters.top().first) {
            int v = gs.monsters.top().second; gs.monsters.pop();
            if (gs.visited[v]) continue;
            gs.current_power += reward[v];
            gs.visited[v] = true;
            q.push(v);
            changed = true;
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : tree[u]) {
                if (gs.visited[v]) continue;
                if (node_type[v] == 1) {
                    if (gs.current_power >= req_strength[v]) {
                        gs.current_power += reward[v];
                        gs.visited[v] = true;
                        q.push(v);
                        changed = true;
                    } else {
                        gs.monsters.push({-req_strength[v], v});
                    }
                } else {
                    gs.visited[v] = true;
                    q.push(v);
                    changed = true;
                }
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    long long max_req = 0;
    for (int i = 2; i <= n; ++i) {
        cin >> node_parent[i] >> node_type[i] >> req_strength[i] >> reward[i];
        tree[node_parent[i]].push_back(i);
        max_req = max(max_req, req_strength[i]);
        if (node_type[i] == 2) potion_id[i] = total_potions++;
    }
    
    state_dp[0].current_power = 1;
    state_dp[0].visited[1] = true;
    expand_monsters(state_dp[0], 1);
    
    for (int mask = 0; mask < (1 << total_potions); ++mask) {
        if (state_dp[mask].current_power == 0) continue;
        for (int i = 2; i <= n; ++i) {
            if (node_type[i] == 2 && state_dp[mask].visited[i] && !(mask & (1 << potion_id[i]))) {
                int bit = potion_id[i];
                int next_mask = mask | (1 << bit);
                long long new_power = state_dp[mask].current_power * reward[i];
                if (new_power > state_dp[next_mask].current_power) {
                    state_dp[next_mask] = state_dp[mask];
                    state_dp[next_mask].current_power *= reward[i];
                    expand_monsters(state_dp[next_mask], i);
                }
            }
        }
    }
    
    long long final_power = 0;
    for (int mask = 0; mask < (1 << total_potions); ++mask) {
        final_power = max(final_power, state_dp[mask].current_power);
    }
    
    cout << (final_power >= max_req ? "Yes" : "No") << endl;
    return 0;
}

Counting Shortest Paths

Find the shortest path count in an unweighted graph where edges are defined by the complement graph. BFS can be optimized using a set of unvisited nodes. For each node, instead of iterating its complement edges, iterate the original edges to find which nodes are not reachable in the complement graph. Maintain distance and use dynamic programming: the number of ways to reach a node at distance d is the total ways to reach any node at distance d-1, minus the ways from neighbors in the original graph at distance d-1.

#include <iostream>
#include <vector>
#include <set>
#include <queue>

using namespace std;

const int MOD = 998244353;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    vector<int> dist(n + 1, -1);
    vector<long long> ways(n + 1, 0);
    vector<vector<int>> levels(n + 1);
    
    set<int> unvisited;
    for (int i = 2; i <= n; ++i) unvisited.insert(i);
    
    queue<int> q;
    q.push(1);
    dist[1] = 0;
    ways[1] = 1;
    levels[0].push_back(1);
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        set<int> next_visits = unvisited;
        for (int v : adj[u]) {
            if (unvisited.count(v)) {
                next_visits.erase(v);
            }
        }
        for (int v : next_visits) {
            dist[v] = dist[u] + 1;
            levels[dist[v]].push_back(v);
            unvisited.erase(v);
            q.push(v);
        }
    }
    
    if (dist[n] == -1) {
        cout << -1 << endl;
        return 0;
    }
    
    vector<long long> level_sum(n + 1, 0);
    level_sum[0] = 1;
    
    for (int d = 1; d <= dist[n]; ++d) {
        for (int u : levels[d]) {
            ways[u] = level_sum[d - 1];
        }
        for (int u : levels[d - 1]) {
            for (int v : adj[u]) {
                if (dist[v] == d) {
                    ways[v] = (ways[v] - ways[u] + MOD) % MOD;
                }
            }
        }
        for (int u : levels[d]) {
            level_sum[d] = (level_sum[d] + ways[u]) % MOD;
        }
    }
    
    cout << ways[n] << endl;
    return 0;
}