Tin học trẻ C1 - Vòng Sơ khảo quốc gia 2024

Alice có một khu đất trống được chia làm \(m \times n\) mảnh đất hình vuông. Các hàng mảnh đất hình vuông được đánh số từ \(1\) đến \(m\) từ trên xuống dưới, các cột mảnh đất hình vuông được đánh số từ \(1\) đến \(n\) từ trái sang phải. Mảnh đất hình vuông nằm giao giữa hàng \(i\) \((1 \leq i \leq m)\) và cột \(j\) \((1 \leq j \leq m)\) gọi là ô \((i, j)\).

Alice dự định sẽ đi lần lượt từng ô theo đường xoắn ốc cùng chiều kim đồng hồ bắt đầu từ ô \((1, 1)\) để trồng cây trên các mảnh đất hình vuông.

Ví dụ, với khu đất \(4 \times 5\) thì thứ tự các ô Alice đi như hình dưới.

Qua khảo sát, Alice biết rằng có \(k\) ô \((x_{1}, y_{1}), (x_{2}, y_{2}), \ldots, (x_{k}, y_{k})\) không thể trồng cây. Khi đó, nếu Alice đi vào các ô này Alice sẽ bỏ qua và không trồng cây ở đó. Là một người yêu thích toán học, Alice mong muốn mỗi ô sẽ được trồng một số cây đều là số nguyên tố.

Cụ thể, khi đi theo đường xoắn ốc như dự định, nếu vào ô là ô \((u, v)\) trồng được cây và ô này là ô thứ \(t\) trồng được cây (tính từ lúc bắt đầu xuất phát) thì ô \((u, v)\) sẽ được trồng số lượng cây là số nguyên tố lớn thứ \(t\).

Ví dụ, nếu khu đất \(4 \times 5\) có \(7\) ô không thể trồng được cây là \((1, 2), (2, 3), (3, 4), (4, 5), (2, 1), (3, 2), (4, 3)\) thì số cây được trồng tại các ô như hình dưới.

Sau khi trồng cây xong, Alice muốn tính số lượng cây nằm trong hình chữ nhật có ô trái trên là ô \((u_{1}, v_{1})\) và ô phải dưới là ô \((u_{2}, v_{2})\). Hãy giúp Alice trả lời câu hỏi như vậy.

Input

• Dòng đầu chứa bốn số nguyên \(m, n, k, q\) \((m, n \leq 500, k \leq m \times n, q \leq 10^{6})\);
• Dòng thứ \(i\) trong \(k\) dòng sau chứa hai số nguyên \(x_{i}, y_{i}\) \((1 \leq x_{i} \leq m, 1 \leq y_{i} \leq n)\);
• Tiếp theo là \(q\) dòng, mỗi dòng chứa bốn số \(u_{1}, v_{1}, u_{2}, v_{2}\) mô tả một câu hỏi.

Output

• Gồm \(q\) dòng, mỗi dòng là câu trả lời cho câu hỏi tương ứng ở dữ liệu vào.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(m = 1, n \leq 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(m \leq 100, n \leq 100\).
• Subtask \(3\) (\(20\%\) số điểm): \(q \leq 10\).
• Subtask \(4\) (\(20\%\) số điểm): không có rằng buộc gì thêm.

Example

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

33
60

Xâu \(s\) được gọi là xâu con của xâu \(x\) nếu ta có thể nhận được \(s\) từ \(x\) bằng cách giữ nguyên hoặc xóa đi một số kí tự. Ví dụ, xâu bb là xâu con của xâu bab, nhưng xâu aa thì không phải là xâu con của xâu bab.

Cho hai xâu \(x\) và \(y\), tiến hành liệt kê (theo thứ tự từ điển) tất cả các xâu có độ dài \(n\) là xâu con của xâu \(x\) nhưng không phải là xâu con của xâu \(y\).

Ví dụ, \(x =\) abab; \(y =\) abb và \(n = 2\), có hai xâu độ dài bằng \(2\) là xâu con của xâu \(x\) nhưng không phải là xâu con của xâu \(y\) là: aa, ba.

Yêu cầu: Cho hai xâu \(x, y\) và \(m\) xâu \(s_{1}, s_{2}, \ldots, s_{m}\) có có cùng độ dài \(n\), hãy tìm thứ tự từ điển của các xâu \(s_{1}, s_{2}, \ldots, s_{m}\) khi liệt kê (theo thứ tự từ điển) tất cả các xâu có độ dài bằng \(n\) là xâu con của xâu \(x\) nhưng không phải là xâu con của xâu \(y\).

Input

• Dòng đầu chứa ba số nguyên dương \(m, n, k\) \((m, n \leq 200, k \leq 10^{9})\).
• Dòng thứ hai chứa xâu \(x\).
• Dòng thứ ba chứa xâu \(y\).
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(s_{i}\).

Các xâu \(x, y, s_{1}, s_{2}, \ldots, s_{m}\) có độ dài không quá \(200\) và chỉ gồm các kí tự a đến z.

Output

• Gồm \(m\) dòng, gọi \(p_{i}\) là thứ tự từ điển của xâu \(s_{i}\) trong các xâu được xét, đưa ra số \(p_{i} \% k\) trên dòng \(i\) (phép toán \(\%\) là phép toán chia lấy dư). Nếu xâu \(s_{i}\) không phải xâu con của xâu \(x\) hoặc \(s_{i}\) là xâu con của xâu \(y\) thì ghi \(-1\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Độ dài xâu \(x, y\) không vượt quá \(16\) và \(n = 1\).
• Subtask \(2\) (\(50\%\) số điểm): Độ dài xâu \(x, y\) không vượt quá \(16\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 2 100
abab
abb
aa
ab
ba

1
-1
2

Cho dãy số \(A\) gồm \(N\) phần tử \(a_{1}, a_{2}, \ldots, a_{N}\). Hãy đếm số cặp \(L, R\) \((1 \leq L \leq R \leq N)\) sao cho:

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((N \leq 3 \times 10^{5})\) mô tả số lượng phần tử của dãy số \(A\);
• Dòng tiếp theo chứa \(N\) số nguyên dương \(a_{i}\) \((a_{i} \leq 10^{9}; 1 \leq i \leq N)\) mô tả các phần tử của dãy số \(A\).

Output

• In ra một số nguyên là số cặp thoả mãn yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 10^{3}\).
• Subtask \(2\) (\(30\%\) số điểm): dãy số tăng dần: \(a_{i} \leq a_{i + 1}\) \((1 \leq i \leq N)\).
• Subtask \(3\) (\(20\%\) số điểm): không có rằng buộc gì thêm.

Example

3
2 2 4

4

Alice có bảng số \(A\) kích thước \(3 \times 4\). Các hàng được đánh số từ \(1\) đến \(3\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(4\) từ trái sang phải. Ô nằm giao ở hàng \(i\) \((1 \leq i \leq 3)\) và cột \(j\) \((1 \leq j \leq 4)\) được gọi là ô \((i, j)\) và ban đầu chứa số \(a_{i, j}\). Alice đã thực hiện liên tục \(k\) phép biến đổi, mỗi phép thuộc một trong hai loại dưới đây để nhận được bảng số \(B\).

• Loại \(1\): Chọn hình vuông kích thước \(3 \times 3\) bên trái và quay theo chiều kim đồng hồ (xem Hình \(1\)).
  
• Loại \(2\): Chọn hình vuông kích thước \(3 \times 3\) bên phải và quay ngược chiều kim đồng hồ (xem Hình \(2\)).
  

Yêu cầu: Alice đã mất thông tin dãy phép biến đổi, Alice chỉ còn ghi nhớ thông tin bảng \(A\) và \(B\). Hãy giúp Alice tìm ra một dãy các phép biến đổi để đưa bảng \(A\) về bảng \(B\). Chú ý rằng, dãy biến đổi bất kì, miễn là biến đổi được từ bảng \(A\) về bảng \(B\).

Input

• Ba dòng đầu, mỗi dòng chứa bốn số nguyên dương mô tả bảng \(A\) (các số không vượt quá \(100\)).
• Ba dòng sau, mỗi dòng chứa bốn số mô tả bảng \(B\).

Output

• Dòng đầu ghi số nguyên \(t\) là số phép biến đổi.
• Dòng thứ hai chứa \(t\) số bằng \(1\) hoặc \(2\) mô tả dãy biến đổi.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Các số của bảng \(A\) chỉ nhận giá trị \(1\) hoặc \(2\).
• Subtask \(2\) (\(30\%\) số điểm): Có cách biến đổi từ bảng \(A\) về bảng \(B\) với số phép không vượt quá \(36\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

9 9 9 9
1 2 3 4
5 6 7 8
1 9 9 4
5 9 9 8
6 2 7 3

2
1 2