[Học thêm HSG9]Ngày 26/7/2024

Cho một xâu dài vô hạn chứa tất cả các số nguyên dương theo trình tự tăng dần: \(12345678910111213141516171819202122232425…\)

Nhiệm vụ của bạn là xử lí \(q\) truy vấn trả lời cho câu hỏi: số nào nằm ở vị trí thứ \(k\) trong xâu?

Input

Dòng đầu tiên chứa một số nguyên duy nhất \(q\): số lượng truy vấn.
Sau đó gồm \(q\) dòng tiếp theo biểu diễn các truy vấn, mỗi dòng là một số nguyên \(k\): vị trí của kí tự cần tìm trong xâu (xâu được đánh số từ \(1\)).

Output

Với mỗi truy vấn, in ra kết quả tương ứng trên từng dòng.

Constraints

• Subtask \(1(40\%\) số điểm): \(Q=1,k \leq 10^6\)
• Subtask \(2(60\%\) số điểm): \(Q\leq 10^3, k \leq 10^{18}\)

3
7
19
12

7
4
1

Cho hàm \(F(n)\) được định nghĩa như sau:

• \(F(0)='a'\)
• \(F(1)='b'\)
• \(F(2)='c'\)
• \(F(i) = F(i-3)+F(i-2)+F(i-1) \forall i>2\)

Cho hai số nguyên dương \(n\) và \(k\), hãy cho biết ký tự thứ \(k\) của \(F(n)\) là bao nhiêu. Biết rằng ký tự đầu tiên của \(F(n)\) được đánh số là \(1\).

Input

Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(k\)

Output

Dòng thứ nhất chứa ký tự thứ \(k\) của \(F(n)\)

3 2

b

Ràng buộc

\(1 \leq k \leq |F(n)|\)

• Subtask \(1(40\% \text{số test})\): \(n\leq 10\)
• Subtask \(2(60\% \text{số test})\): \(n \leq 35\)

Có thể định nghĩa khái niệm dãy ngoặc đúng dưới dạng đệ quy như sau:

1. "()()" là dãy ngoặc đúng
2. \(C\) là dãy ngoặc đúng nếu \(C\) = (\(A\)) hay \(C\) = \(AB\) với \(A\), \(B\) là các dãy ngoặc đúng.

Ví dụ dãy ngoặc đúng: (), (()), ()(), (())()
Ví dụ dãy ngoặc sai: )(, ((((, ()((, )))), )()(
Bạn hãy viết chương trình liệt kê tất cả các dãy ngoặc đúng có chiều dài \(n\) (\(n\) chẵn)

Input

• Là số nguyên \(n\) (\(n\) chẵn, \(2 ≤ n ≤ 24\))

Output

• In số \(m\) là số lượng các dãy ngoặc đúng có chiều dài \(n\)

4

2

T-rung có một dãy yêu thích \(a\) gồm \(n\) số nguyên. Anh ấy viết nó ra trên bảng trắng theo thứ tự sau:

• Viết số đầu tiên của dãy \(a\) ở phía bên trái (đầu bảng trắng).
• Viết số thứ hai của dãy \(a\) ở phía bên phải (cuối bảng trắng).
• Viết số thứ ba của dãy \(a\) càng xa về bên trái càng tốt (nhưng bên phải số đầu tiên).
• Viết số thứ tư của dãy \(a\) càng xa về bên phải càng tốt (nhưng bên trái số thứ hai).
• T-rung tiếp tục như vậy cho đến khi viết ra toàn bộ dãy số.

Ví dụ, nếu \(n\) = 7 và \(a\) = \([3, 1, 4, 1, 5, 9, 2]\), T-rung sẽ viết dãy số lên bảng trắng là \([3, 4, 5, 2, 9, 1, 1]\).
Bây giờ bạn nhìn thấy dãy số đã được viết trên bảng trắng và muốn khôi phục lại dãy yêu thích của T-rung.

Input

• Dòng đầu tiên chứa một số nguyên dương \(t\) (\(1 ≤ t ≤ 300\)) — số lượng bộ test.
• Sau đó, \(t\) bộ test tiếp theo.
  • Dòng đầu tiên của mỗi bộ test chứa một số nguyên \(n\) (\(1 ≤ n ≤ 5.10^4\)) — độ dài của dãy số được viết trên bảng trắng.
  • Dòng tiếp theo chứa \(n\) số nguyên \(b_1, b_2, ..., b_n\) (\(1 ≤ b_i ≤ 10^9\)) — dãy số được viết trên bảng trắng.

Output

• In ra \(t\) câu trả lời cho các bộ test. Mỗi câu trả lời là dãy số \(a\) mà T-rung đã viết ra trên bảng trắng.

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

3 1 4 1 5 9 2 
9 1 2 7 
8 2 4 4 3 9 1 7 2 8 7 
42 
11 7 
1 1 1 1 1 1 1 1

T-rung rất thích chơi game, đặc biệt là các game giải đố. Với khả năng lập trình của mình, T-rung đã nghĩ ra một trò chơi mới mang tên "No No! Balls pop".

Trong "No No! Balls pop", người chơi sẽ điều khiển một lưới \(m x n\) chứa các quả bóng, mỗi quả bóng có một số nguyên trên đó. Nhiệm vụ của người chơi là đập búa vào các quả bóng để làm vỡ chúng, và tất cả các quả bóng có cùng số nguyên với quả bóng bị đập đầu tiên cũng sẽ vỡ theo. Người chơi có thể đập búa tối đa \(k\) lần. Mục tiêu là làm vỡ nhiều bóng nhất có thể trong số lần đập búa cho phép.

Cách chơi

• Người chơi chọn một quả bóng để đập.
• Quả bóng được chọn sẽ vỡ và tất cả các quả bóng khác có cùng số nguyên với nó cũng sẽ vỡ.
• Người chơi tiếp tục đập bóng cho đến khi không thể đập thêm được nữa hoặc đã đạt đến giới hạn \(k\) lần đập búa.

Ví dụ

Giả sử bạn có một lưới \(3 x 3\) với các quả bóng được gán số như sau:
\(1\) \(1\) \(2\)
\(2\) \(1\) \(1\)
\(3\) \(3\) \(1\)
Nếu người chơi đập vào quả bóng có số \(1\) ở vị trí \((0, 0)\), các quả bóng có số \(1\) ở các vị trí khác cũng sẽ vỡ. Sau đó, nếu người chơi đập vào quả bóng có số \(2\), tất cả các quả bóng có số \(2\) cũng sẽ vỡ.

Yêu cầu

Bạn là người đầu tiên thử nghiệm trò chơi kỳ lạ do T-rung nghĩ ra này. Hãy tìm cách chiến thắng thuyết phục trò chơi này nhé!

Input

• Dòng \(1\): Ghi số nguyên dương \(m\), \(n\) và \(k\) (\(1 ≤ m, n ≤ 300\), \(1 ≤ k ≤ m*n\))
• \(m\) dòng tiếp theo, mỗi dòng ghi \(n\) số nguyên dương là số ghi trên quả bóng có tọa độ \((i, j)\).

Output

• Ghi một số nguyên cho biết số lượng bóng vỡ nhiều nhất tìm được.

Subtask

• Subtask \(1(60\%\) số điểm): \(a_{i,j} \leq 10^6\)
• Subtask \(2(40\%\) số điểm): \(a_{i,j} \leq 10^9\)

3 6 2
1 2 1 3 1 1
2 1 4 1 4 3
1 2 1 4 1 1

13