A. Grid Ice Floor

This problem requires analyzing the accessible states of each cell on a grid. When standing at position (i, j), there are exactly 5 possible movement states:

• Moving upward
• Moving downward
• Moving leftward
• Moving rightward
• Standing still

We define dp[i][j][state] to indicate whether reaching cell (i, j) with a specific state is achievable. The transition logic processes each state and enumerates all possible successor states.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int rows, cols;
    cin >> rows >> cols;
    vector<string> grid(rows);
    for (auto& row : grid) cin >> row;
    
    // dp[r][c][dir]: dir=0(up),1(down),2(left),3(right),4(stop)
    vector<vector<array<int, 5>>> reachable(rows,
        vector<array<int, 5>>(cols, array<int, 5>{}));
    queue<array<int, 3>> bfsQueue;
    
    const array<int, 4> dirX = {1, -1, 0, 0};
    const array<int, 4> dirY = {0, 0, 1, -1};
    
    // Start: can move right or down from (0,0)
    bfsQueue.push({0, 0, 2});
    bfsQueue.push({0, 0, 0});
    reachable[0][0][0] = reachable[0][0][2] = reachable[0][0][4] = 1;
    
    auto isBlocked = [&](int x, int y) {
        return x < 0 || x >= rows || y < 0 || y >= cols || grid[x][y] == '#';
    };
    
    while (!bfsQueue.empty()) {
        auto [x, y, dir] = bfsQueue.front();
        bfsQueue.pop();
        
        if (dir == 4) {  // Standing still: can start moving in any direction
            for (int i = 0; i < 4; ++i) {
                int nx = x + dirX[i], ny = y + dirY[i];
                if (!isBlocked(nx, ny) && !reachable[nx][ny][i]) {
                    bfsQueue.push({nx, ny, i});
                    reachable[nx][ny][i] = 1;
                }
            }
            continue;
        }
        
        int nx = x + dirX[dir], ny = y + dirY[dir];
        if (isBlocked(nx, ny)) {
            if (!reachable[x][y][4]) {
                bfsQueue.push({x, y, 4});
                reachable[x][y][4] = 1;
            }
        } else {
            bfsQueue.push({nx, ny, dir});
            reachable[nx][ny][dir] = 1;
        }
    }
    
    int result = 0;
    for (int i = 0; i < rows; ++i)
        for (int j = 0; j < cols; ++j)
            result += any_of(reachable[i][j].begin(), reachable[i][j].end(), 
                            [](int v) { return v; });
    
    cout << result << '\n';
    return 0;
}

B. Strictly Superior

The task is to determine whether one product is strictly superior to another by checking price and feature requirements. Using bitsets provides efficient comparision operations.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    vector<bitset<110>> features(n + 1);
    vector<int> price(n + 1);
    
    for (int i = 1; i <= n; ++i) {
        int cnt;
        scanf("%d %d", &price[i], &cnt);
        for (int j = 0; j < cnt; ++j) {
            int feat;
            scanf("%d", &feat);
            features[i].set(feat);
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j) continue;
            
            if (price[i] <= price[j]) {
                bitset<110> common = features[i] & features[j];
                if (common == features[j] && (price[i] < price[j] || common != features[i])) {
                    printf("Yes\n");
                    return 0;
                }
            }
        }
    }
    printf("No\n");
    return 0;
}

C. Reversible

This problem uses a set to store string representations for deduplication. Both the original string and its reverse are considered equivalent, so we hash both and store only one.

#include <bits/stdc++.h>
using namespace std;

using ULL = unsigned long long;
const ULL BASE = 131;

char buffer[200010];
set<ULL> uniqueStrings;

ULL computeHash(int length) {
    ULL hashVal = 0;
    for (int i = 1; i <= length; ++i)
        hashVal = hashVal * BASE + buffer[i];
    return hashVal;
}

int main() {
    int n;
    scanf("%d", &n);
    
    for (int i = 1; i <= n; ++i) {
        scanf("%s", buffer + 1);
        int len = strlen(buffer + 1);
        
        ULL hash1 = computeHash(len);
        reverse(buffer + 1, buffer + 1 + len);
        ULL hash2 = computeHash(len);
        
        if (uniqueStrings.find(hash1) == uniqueStrings.end() &&
            uniqueStrings.find(hash2) == uniqueStrings.end())
            uniqueStrings.insert(hash1);
    }
    
    printf("%lld\n", (long long)uniqueStrings.size());
    return 0;
}

D. Find It!

The given graph construction forms a functional graph structure, which consists of one or more rooted cycles with trees pointing inward. From any starting node, traversal eventually reaches a cycle.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> next(n);
    for (int i = 0; i < n; ++i) {
        cin >> next[i];
        --next[i];  // Convert to 0-indexed
    }
    
    vector<int> visited(n, 0);
    int current = 0;
    
    // Traverse until we find a visited node (cycle entry point)
    while (!visited[current]) {
        visited[current] = 1;
        current = next[current];
    }
    
    vector<int> cycleNodes = {current};
    for (int i = next[current]; i != current; i = next[i])
        cycleNodes.push_back(i);
    
    cout << cycleNodes.size() << '\n';
    for (int node : cycleNodes)
        cout << node + 1 << ' ';
    cout << '\n';
    
    return 0;
}

E. Vacation Together

Store all input strings in a 2D character array, then iterate column by column. Count consecutive columns containing no 'x' character and track the maximum length.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int rows, cols;
    scanf("%d %d", &rows, &cols);
    
    vector<string> data(rows);
    for (int i = 0; i < rows; ++i)
        scanf("%s", &data[i][0]);
    
    int streak = 0, best = -1;
    
    for (int j = 0; j < cols; ++j) {
        bool hasX = false;
        for (int i = 0; i < rows; ++i)
            if (data[i][j] == 'x') hasX = true;
        
        if (!hasX) ++streak;
        else streak = 0;
        
        best = max(best, streak);
    }
    
    printf("%d\n", best);
    return 0;
}

F. Number Box

Analyzing the problem: any two negative numbers can cancel each other regardless of distance, while a single zero can offset any number of negatives at varying distances. The solution requires counting negative numbers and checking for zero presence. When an odd number of negatives exists, the minimum matrix value becomes the unique negative.

G. Jumping Takahashi 2

The approach combines binary search with graph traversal. We binary search the maximum jump distance parameter, then construct a graph where edges connect nodes within reachable distance and perform connectivity checks via depth-first search.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int readInt() {
    int x = 0, sign = 1;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-') sign = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + (c & 15);
    return x * sign;
}

const int MAXN = 205;
const int INF = 5e9;

ll posX[MAXN], posY[MAXN], power[MAXN];
vector<int> adj[MAXN];
bool seen[MAXN];

ll manhattanDist(int i, int j) {
    return llabs(posX[i] - posX[j]) + llabs(posY[i] - posY[j]);
}

void dfs(int u) {
    seen[u] = true;
    for (int v : adj[u])
        if (!seen[v]) dfs(v);
}

bool check(ll limit) {
    for (int i = 1; i <= MAXN; ++i) adj[i].clear();
    
    for (int i = 1; i <= MAXN; ++i) {
        for (int j = 1; j <= MAXN; ++j) {
            if (i == j) continue;
            if (manhattanDist(i, j) <= power[i] * limit)
                adj[i].push_back(j);
        }
    }
    
    for (int start = 1; start <= MAXN; ++start) {
        memset(seen, 0, sizeof(seen));
        dfs(start);
        bool allVisited = true;
        for (int k = 1; k <= MAXN; ++k)
            if (!seen[k]) allVisited = false;
        if (allVisited) return true;
    }
    return false;
}

int main() {
    int n = readInt();
    for (int i = 1; i <= n; ++i) {
        posX[i] = readInt();
        posY[i] = readInt();
        power[i] = readInt();
    }
    
    int lo = 0, hi = INF, answer = INF;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (check(mid)) {
            hi = mid - 1;
            answer = mid;
        } else {
            lo = mid + 1;
        }
    }
    
    printf("%d\n", answer);
    return 0;
}

H. When?

A straightforward time calculation problem. Minutes past the hour determine weather it's 21:XX or 22:XX, with zero-padded output for single digits.

#include <cstdio>

int main() {
    int minutes;
    scanf("%d", &minutes);
    
    if (minutes < 60) {
        printf("21:%02d", minutes);
    } else {
        printf("22:%02d", minutes - 60);
    }
    return 0;
}

I. Rotation

Instead of performing actual string rotations (which is O(n) per operation), track the cumulative shift modulo the string length. When answering queries, calculate the effective position after accounting for all shifts.

#include <cstdio>

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    
    char str[100005];
    scanf("%s", str);
    
    long long totalShift = 0;
    
    for (int i = 0; i < q; ++i) {
        int op, val;
        scanf("%d %d", &op, &val);
        
        if (op == 1) {
            totalShift += val;
        } else {
            if (totalShift / n > 0)
                totalShift %= n;
            
            if (totalShift >= val)
                printf("%c\n", str[n - totalShift + val - 1]);
            else
                printf("%c\n", str[val - totalShift - 1]);
        }
    }
    return 0;
}

J. Trophy

K. Many Oranges

The problem requires calculating minimum and maximum possible orange counts based on weight constraints. Given total weight in grams and per-orange weight range, compute bounds using integer division.

#include <cstdio>

int main() {
    int minWeight, maxWeight, totalGrams;
    scanf("%d %d %d", &minWeight, &maxWeight, &totalGrams);
    totalGrams *= 1000;
    
    int minCount = (totalGrams % maxWeight == 0) 
                   ? totalGrams / maxWeight 
                   : totalGrams / maxWeight + 1;
    int maxCount = totalGrams / minWeight;
    
    if (minCount > maxCount) {
        printf("UNSATISFIABLE\n");
    } else {
        printf("%d %d\n", minCount, maxCount);
    }
    return 0;
}

L. Alcoholic

Check if cumulative alcohol content exceeds the limit at any point. The key insight is to avoid floating-point comparisons; instead, compare volume * percentage * 100 directly using integers to prevent precision errors.

#include <cstdio>

int main() {
    int n, limit;
    scanf("%d %d", &n, &limit);
    
    int cumulative = 0;
    
    for (int i = 0; i < n; ++i) {
        int vol, percent;
        scanf("%d %d", &vol, &percent);
        cumulative += vol * percent;
        
        if (cumulative > limit * 100) {
            printf("%d\n", i + 1);
            return 0;
        }
    }
    
    printf("-1\n");
    return 0;
}