## Intuition The problem involves disassembling a stable structure of cubes such that the resulting sequence of numbers (formed by the integers on the cubes) is maximized. Vasya and Petya take turns removing cubes, with Vasya aiming to maximize the number and Petya trying to minimize it. The key insight is to understand the stability condition and how it affects the order in which cubes can be removed. ## Approach 1. **Understanding Stability**: A cube can be removed if it is on the ground (y = 0) or if there is a supporting cube directly or diagonally below it. This means we need to track which cubes are "removable" at any point. 2. **Game Strategy**: - Vasya (maximizer) will always try to remove the cube with the highest number among the currently removable cubes. - Petya (minimizer) will always try to remove the cube with the lowest number among the currently removable cubes. 3. **Simulation**: - Use a priority queue (or set) to keep track of removable cubes. For Vasya's turn, use a max-heap; for Petya's turn, use a min-heap. - Start with all cubes that are on the ground (y = 0) as initially removable. - As cubes are removed, check if their removal makes any other cubes removable and update the priority queue accordingly. 4. **Modulo Operation**: Since the final number can be large, compute the result modulo \(10^9 + 9\). ## Complexity - **Time Complexity**: \(O(m \log m)\) due to the use of a priority queue for managing removable cubes. - **Space Complexity**: \(O(m)\) for storing cube coordinates and the priority queue. ## Solution (C++) ```cpp #include using namespace std; const int MOD = 1e9 + 9; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m; cin >> m; vector> cubes(m); for (int i = 0; i < m; ++i) { cin >> cubes[i].first >> cubes[i].second; } // Priority queue for Vasya (max-heap) and Petya (min-heap) priority_queue> vasyaQueue; // max-heap priority_queue, vector>, greater>> petyaQueue; // min-heap // Map to track the number of supports for each cube map, int> supportCount; // Set to track removable cubes set> removable; // Initialize removable cubes (those on the ground) for (int i = 0; i < m; ++i) { if (cubes[i].second == 0) { removable.insert({cubes[i].first, cubes[i].second}); vasyaQueue.push({i, cubes[i].second}); petyaQueue.push({i, cubes[i].second}); } else { // Count supports for cubes not on the ground supportCount[{cubes[i].first, cubes[i].second}] = 0; } } // Function to check if a cube becomes removable auto canRemove = [&](int x, int y) { return removable.count({x - 1, y - 1}) || removable.count({x, y - 1}) || removable.count({x + 1, y - 1}); }; // Result number long long result = 0; bool vasyaTurn = true; for (int step = 0; step < m; ++step) { int index; if (vasyaTurn) { // Vasya's turn: maximize while (!vasyaQueue.empty()) { auto [idx, y] = vasyaQueue.top(); vasyaQueue.pop(); if (removable.count(cubes[idx])) { index = idx; break; } } } else { // Petya's turn: minimize while (!petyaQueue.empty()) { auto [idx, y] = petyaQueue.top(); petyaQueue.pop(); if (removable.count(cubes[idx])) { index = idx; break; } } } // Add to result result = (result * m + index) % MOD; // Remove the cube removable.erase(cubes[index]); // Check if removing this cube makes others removable for (int dx = -1; dx <= 1; ++dx) { int nx = cubes[index].first + dx; int ny = cubes[index].second + 1; if (supportCount.count({nx, ny})) { supportCount[{nx, ny}]--; if (supportCount[{nx, ny}] == 0 && canRemove(nx, ny)) { removable.insert({nx, ny}); vasyaQueue.push({nx, ny}); petyaQueue.push({nx, ny}); } } } // Switch turns vasyaTurn = !vasyaTurn; } cout << result << '\n'; return 0; } ``` This solution efficiently simulates the game using priority queues to manage the order of cube removal, ensuring that both players play optimally.

Cubes

Problem Details