TLEOJ Contest #14 - MEX Board

View as PDF

Submit solution

Points: 800
Time limit: 1.0s
Memory limit: 256M
Input: MEXS.inp
Output: MEXS.out

Authors:
Problem type

Cho một bảng n \times m, các hàng được đánh số từ 1 đến n từ trên xuống dưới, các cột được đánh số từ 1 đến m từ trái sang phải. Ô ở hàng i và cột j (1 \le i \le n; 1 \le j \le m) có điền một số có giá trị là A[i][j]; ban đầu thì với mọi ij, A[i][j] = 0. Giá trị được đặt ở ô ở hàng i và cột j được thực hiện như sau, theo thứ tự từ trái sang phải và từ trên xuống dưới:

  • Gọi S là tập hợp các giá trị được xuất hiện trong tất cả các ô ở hàng x và cột y thỏa mãn một trong hai điều kiện sau: Hoặc x = iy < j; hoặc x < iy = j.
  • Tạo dãy S_2 mới sao cho mọi giá trị trong S_2 khác nhau đôi một và mọi giá trị trong S đều xuất hiện trong S_2.
  • Giá trị tại ô ở hàng i và cột j (A[i][j]), sẽ là số nguyên không âm nhỏ nhất không xuất hiện trong S_2. Giả sử, nếu S_2 = [6; 9; 4; 2; 0], A[i][j] = 11 là số nguyên không âm nhỏ nhất không tồn tại trong S_2. Nói một cách khác, A[i][j] = \text{MEX}(S_2).

Cho hai thao tác được phép sử dụng:

  • Thao tác \text{#}1: Chọn một hàng i bất kì (1 \le i \le n). Trong số các ô ở hàng i, tráo đổi giá trị của ô ở cột thứ j (hay giá trị A[i][j]) với ô ở cột thứ m - j + 1 (hay giá trị A[i][m - j + 1]) với mọi số j nguyên dương thỏa 1 \le j < \frac{m + 1}{2}.
  • Thao tác \text{#}2: Chọn một cột j bất kì (1 \le j \le m). Trong số các ô ở cột j, tráo đổi giá trị của ô ở hàng thứ i (hay giá trị A[i][j]) với ô ở hàng thứ n - j + 1 (hay giá trị A[n - i + 1][j]) với mọi số i nguyên dương thỏa 1 \le i < \frac{n + 1}{2}.

Hãy cho biết rằng nếu thực hiện hai thao tác trên một cách ngẫu nhiên, tại ô ở hàng thứ u và cột thứ v (1 \le u \le n; 1 \le v \le m), giá trị lớn nhất của ô đó có thể là bao nhiêu.

\text{Input} MEXS.inp

  • Dòng đầu gồm ba số n, m (1 \le n, m \le 10^9) – thể hiện độ lớn của bảng, và q (1 \le q \le \text{min}⁡(10^6, n * m)) – số lượng truy vấn.
  • q dòng tiếp theo, mỗi dòng thứ i gồm hai số u_i, v_i (1 \le u_i \le n; 1 \le v_i \le m) – tọa độ của ô được đề cập trong truy vấn thứ i.

\text{Output} MEXS.out

  • Với mỗi truy vấn, in ra một giá trị duy nhất là giá trị lớn nhất của ô tại hàng u_i và cột v_i.

\text{Scoring}

  • Subtask \text{#}1 (20\% số điểm): 1 \le n, m \le 100.
  • Subtask \text{#}2 (30\% số điểm): n = m = 2^k (k \in \mathbb{N}, k \le 10).
  • Subtask \text{#}3 (50\% số điểm): Không có điều kiện gì thêm.

\text{Examples}

\text{Test #}1

\text{Input}

4 4 5
1 1
3 2
4 3
1 2
4 4

\text{Output}

3
3
2
2
3
\text{Explanations}

0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0

Đây là bảng được tạo ra với n = m = 4.


Comments

There are no comments at the moment.