Problem A

Given two positive integers \(x\) and \(y\), compute \(\left\lfloor \frac{y}{x} \right\rfloor\).

Problem B

Given a sequence of integers \(a_1, a_2, \ldots, a_n\), output the minimum value among them.

Problem C

Problem Statement

Each takoyaki remains fresh for exactly \(T\) seconds after being cooked. There are \(N\) takoyakis cooked at times \(a_1, a_2, \ldots, a_N\). \(M\) customers arrive at times \(b_1, b_2, \ldots, b_M\). A customer leaves immediately if no fresh takoyaki is available upon arrival. Determine whether all customers can be served.

Solution Approach

This problem follows a first-come-first-served policy. To maximize service, earlier customers should be prioritized since later ones have more opportunities to be served.

Use a queue to manage waiting customers. Iterate through each takoyaki's cooking time:

• Remove all customers from the front of the queue who have already left due to impatience (i.e., their arrival time plus \(T\) is less than the current takoyaki time).
• If the queue is not empty and the front customer arrived no later than the current time, serve them with this takoyaki.

This greedy strategy runs in \(O(N + M)\) time.

If each customer \(i\) has individual patience \(T_i\), the freshness window becomes \([b_i, b_i + T_i]\). The FIFO property no longer holds.

An efficient offline solution uses event-based scanning:

• Create events for interval start \((b_i, \text{type}=0)\) and end \((b_i + T_i + 1, \text{type}=1)\).
• Merge these with takoyaki cooking times as query points.
• Sort all events by time. Use a Fenwick tree or difference array to track active intervals.
• Maintain a counter \(cnt\) of served customers in the current segment. When processing a takoyaki event, if \(cnt < \text{active\_intervals}\), increment both \(cnt\) and the answer.

This yields the maximum number of customers that can be served.

Variant Interpretation

If "a takoyaki lasts \(t\) seconds" is misinterpreted as "serving takes \(t\) seconds", the problem changes: the vendor can only serve one customer every \(t\) seconds.

In this case:

• Sort all arrival and cooking events.
• Ensure the timeline forms a valid sequence where service never overlaps.
• Specifical, the gap betweeen consecutive customer arrivals must be at least \(t\) if they are to be served without conflict.

This can be checked in \(O(N)\) after sorting.

Problem D

Problem Statement

An \(N \times N\) grid contains tastiness values \(a_{i,j}\). Each query asks: given a limit \(P_q\), what is the maximum sum of tastiness obtainable by selecting a single rectangular subgrid containing at most \(P_q\) cells?

Constraints: \(N \leq 100\).

Solution Approach

Precompute a 2D prefix sum array to enable \(O(1)\) rectangle sum queries.

Then, iterate over all possible rectangles defined by top/bottom rows and left/right columns. For each rectangle of area \(S\), update an array \(f[S]\) to store the maximum sum achievable with exactly \(S\) cells.

After processing all rectangles, compute a suffix maximum array \(g\) such that \(g[i] = \max(f[1], f[2], \ldots, f[i])\), representing the best sum for up to \(i\) cells.

For each query \(P_q\), clamp it to \(N^2\) and output \(g[\min(P_q, N^2)]\).

Total complexity: \(O(N^4)\) for rectangle enumeration, which is feasible for \(N = 100\).

for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) std::cin >> grid[i][j];

// Build 2D prefix sum for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) grid[i][j] += grid[i][j - 1];

for (int j = 1; j <= n; ++j) for (int i = 1; i <= n; ++i) grid[i][j] += grid[i - 1][j];

std::vector best(n * n + 1, 0);

// Enumerate all rectangles for (int top = 1; top <= n; ++top) { for (int bottom = top; bottom <= n; ++bottom) { for (int left = 1; left <= n; ++left) { for (int right = left; right <= n; ++right) { int area = (bottom - top + 1) * (right - left + 1); int total = grid[bottom][right] - grid[top - 1][right] - grid[bottom][left - 1] + grid[top - 1][left - 1]; best[area] = std::max(best[area], total); } } } }

// Propagate best values for smaller areas for (int i = 1; i <= n * n; ++i) best[i] = std::max(best[i], best[i - 1]);

int q; std::cin >> q; while (q--) { int p; std::cin >> p; p = std::min(p, n * n); std::cout << best[p] << '\n'; }

</details>