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

Xét biểu thức sau:

Cho giá trị của \(x\) và \(y\), hãy tính \(A\).

Input

• Dòng đầu tiên chứa số nguyên \(x\) (\(0 \leq x \leq 100\)).
• Dòng thứ hai chứa số nguyên \(y\) (\(0 \leq y \leq 100\)).

Output

• In ra một số nguyên là kết quả của bài toán.

Example

1
2

7

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: Cho dãy \(k\) phép biến đổi, hãy xác định 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\));
• Dòng tiếp theo chứa số nguyên \(k\) \((k \leq 100)\);
• Dòng tiếp theo chứa \(k\) số nguyên, mỗi số bằng \(1\) (Loại \(1\)) hoặc \(2\) (Loại \(2\)) mô tả dãy biến đổi.

Output

• Gồm ba dòng, mỗi dòng chứa bốn số nguyên dương mô tả bảng \(B\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(k = 1\).
• Subtask \(2\) (\(50\%\) 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
2
1 2

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

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 bảng hình vuông kích thước \(N \times N\). Người ta điền \(N \times N\) số đầu tiên của dãy \(1, 3, 5, \dots\) vào bảng theo hình xoắn ốc từ ngoài vào trong, theo chiều kim đồng hồ bắt đầu từ ô góc trái bên trên.

Hình minh họa chính thức cho bảng \(4 \times 4\) và \(5 \times 5\):

Input

• Nhập từ bàn phím một số nguyên dương \(N\) (\(1 \le N \le 10000\)).

Output

• In ra màn hình một số nguyên dương là tổng các số lớn nhất trên mỗi dòng của bảng.

Example

4

84

5

165

Vòng xoắn ốc Ulam là một mô tả đồ họa của tập hợp các số nguyên tố, được phát minh bởi nhà toán học Stanislaw Ulam. Nó được xây dựng bằng cách viết các số nguyên dương theo hình xoắn ốc vuông và đặc biệt đánh dấu các số nguyên tố. Bạn có thể đọc thêm nó tại đây

Nhưng chúng ta sẽ tính toán trên phiên bản thay thế của hình xoắn ốc này trong đó các số nguyên tố được xếp thành hình xoắn ốc thay vì số tự nhiên như trong hình xoắn ốc ban đầu của Ulam.

Các số nguyên tố được viết dưới dạng xoắn ốc bắt đầu từ gốc \((0, 0)\) và di chuyển như thể hiện trong sơ đồ trên. Các số được hiển thị trong cột bên phải và hàng dưới cùng là số cột và số hàng tương ứng (tức là tọa độ \(y\) và \(x\)).

Mục tiêu là tìm vị trí (tọa độ \(x\) và \(y\)) của một số nguyên tố đã cho.

Input

• Một số nguyên dương duy nhất là số nguyên tố \(N\)

Output

• in ra hai số nguyên cách nhau một dấu cách là toạ độ của số nguyên tố \(N\) trong bảng xoắn ốc.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \leq 10^6\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^8\).
• Subtask \(3\) (\(40\%\) số điểm): \(N \leq 10^{10}\).

Example

5 

1 1

11 

-1 1

Một số tự nhiên được gọi là một số hồi văn nếu ta đọc từ trái sang phải hoặc từ phải sang trái đều như nhau.

Ví dụ: số \(23432\) là một số hồi văn.

Yêu cầu: Cho trước 2 số tự nhiên \(a,b\) với \(a \leq b \leq 10^{16}\). Hỏi có bao nhiêu số hồi văn \(x\) thỏa mãn \(a \leq x \leq b\).

Input

• Một dòng ghi 2 số tự nhiên \(a, b\) trên một dòng với \(a, b \leq 10^{16}\).

Output

• Ghi ra một số nguyên \(k\) là số các số hồi văn \(x\) thỏa mãn \(a \leq x \leq b\).

Example

100 191 

10

Hãy đếm số lượng số nguyên trong đoạn từ \(a\) tới \(b\) mà trong mỗi số đó không có hai chữ số liền kề nào giống nhau.

Input

• Gồm một dòng duy nhất chứa hai số nguyên \(a\) và \(b\) \((0 \leq a \leq b \leq 10^{18})\).

Output

• In một số nguyên: đáp án cho vấn đề.

Example

123 321

171

Số Ra-One là số mà hiệu của tổng các chữ số ở vị trí chẵn và tổng các chữ số ở vị trí lẻ là bằng 1.

Ví dụ số \(234563\) là số \(Ra-One\), vì \((2+4+6) - (3+5+3) = 1\).

Còn số \(123456\) không phải số \(Ra-One\), vì \((1+3+5) - (2+4+6) = -4 ≠ 1\)

Tìm số lượng số \(Ra-One\) từ \(A\) đến \(B\).

Input

• Hai số \(A, B\).

Output

• Số lượng số Ra-One tìm được.

Input

1 10

Output

1

Input

10 100

Output

9

Giải thích:

• VD1: Chỉ có 1 số \(Ra-One\) duy nhất là \(10\)
• VD2: Các số \(Ra-One\) là \(10, 21, 32, 43, 54, 65, 76, 87, 98\).

Giới hạn: \(1 ≤ A≤ B≤ 10^8\).

Nguồn: https://www.spoj.com/problems/RAONE

Nhiệm vụ của bạn là đếm số lượng hoán vị của \(1, 2, \dots, n\) có đúng \(k\) cặp nghịch thế (tức là cặp hai phần tử ở sai thứ tự).

Ví dụ, với \(n = 4\) và \(k = 3\), có \(6\) hoán vị:

• \([1,4,3,2]\)
• \([2,3,4,1]\)
• \([2,4,1,3]\)
• \([3,1,4,2]\)
• \([3,2,1,4]\)
• \([4,1,2,3]\)

Input

• Dòng đầu vào duy nhất có hai số nguyên \(n\) và \(k\)
• \(1 \le n \le 500\)
• \(0 \le k \le \frac{n(n-1)}{2}\)

Output

• In đáp án chia lấy dư cho \(10^9 + 7\)

Example

4 3

6