Kỳ thi sơ loại Young ICT năm 2024 - Bảng B

Hậu (♕, ♛) là một trong hai loại quân cờ chủ lực nặng trên bàn cờ vua (loại còn lại là Xe), đây là quân mạnh nhất trên bàn cờ và quan trọng thứ hai sau quân Vua. Quân Hậu có thể di chuyển không giới hạn ô theo phương ngang, phương dọc hoặc phương chéo.

Cho bàn cờ vua có kích thước \(n \times n\), các cột được đánh số từ \(1\) đến \(n\) theo chiều từ trái qua phải, các hàng được đánh số từ \(1\) đến \(n\) theo chiều từ trên xuống dưới. Ô \((x,y)\) của bàn cờ nằm ở hàng thứ \(x\) và cột thứ \(y\).

Yêu cầu: Biết được tọa độ của quân Hậu là ô \((x, y)\), hỏi quân Hậu có thể tiến đến ô \((u, v)\) trong một bước hay không?

Dữ liệu

• Dòng đầu tiên chứa một số tự nhiên \(t\), là số câu hỏi. \((1 \leq t \le 10^{6})\)
• \(t\) dòng tiếp theo, mỗi dòng chứa \(5\) số nguyên dương \(n, x, y, u\) và \(v\) \((1 \leq x,y,u,v \leq n \leq 10^{4})\). Dữ liệu đảm bảo \((x, y)\) khác \((u, v)\), tức quân Hậu không nằm ở ô \((u, v)\).

Kết quả

• \(t\) dòng, mỗi dòng in câu trả lời, YES nếu như quân Hậu có thể tiến đến ô (\(u, v\)), ngược lại in ra NO.

Chấm điểm

• Gọi \(c\) là số câu hỏi bạn trả lời đúng và \(T\) là số câu hỏi, \(d = \frac{c}{T}\), điểm của bạn sẽ được tính bằng công thức \(1 - (1 - d) ^ d\).

Ví dụ

2
8 3 5 7 1
8 3 5 1 1

YES
NO

Giải thích

Hình thể hiện các ô mà quân Hậu có thể tiến đến ở test ví dụ.

Bạn được cho một dãy số nguyên dương \(A\) có \(N\) phần tử \(A_1, A_2, \dots, A_N\).

Hai cặp số nguyên dương \((x, y)\) được coi là cặp số đảo ngược nếu đảo ngược thứ tự các chữ số của \(x\) thì được số \(y\), và nếu đảo ngược thứ tự các chữ số của \(y\) thì được số \(x\):

• Cặp số \((123, 321)\) là cặp số đảo ngược.
• Cặp số \((897, 12)\) không là cặp số đảo ngược.

Yêu cầu: Bạn hãy đếm số cặp phần tử trong dãy \(A\) là cặp số đảo ngược.

Dữ liệu

• Dòng đầu chứa số nguyên dương \(N (N \le 10^5)\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N (A_i \le 10^9)\).

Các số trên cùng một dòng cách nhau bởi chính xác một dấu cách.

Kết quả

Ghi ra một số nguyên là số lượng cặp số nguyên dương \((i, j)\) sao cho \(1 \le i < j \le N\) và \((A_i, A_j)\) là cặp số đảo ngược.

Ràng buộc

• Có \(50\%\) số test tương ứng với \(50\%\) số điểm thỏa mãn: \(N \le 1000\).
• Có \(25\%\) số test khác tương ứng với \(25\%\) số điểm thỏa mãn: \(N \le 10^5\) và \(A_i \le 10^5\).
• Có \(25\%\) số test còn lại tương ứng với \(25\%\) số điểm thỏa mãn: \(N \le 10^5\) và \(A_i \le 10^9\).

Ví dụ

6
123 123 456 321 654 789

3

Giải thích

Các cặp số \((i,j)\) thỏa mãn là \((1, 4)\), \((2, 4)\) và \((3, 5)\).

Giai thừa của một số nguyên dương \(N\) là tích của \(N\) số nguyên dương đầu tiên.

Siêu giai thừa của một số nguyên dương \(N\) là tích của \(N\) giai thừa đầu tiên.

Yêu cầu: Viết chương trình nhập vào một số nguyên dương \(N\), hãy tìm số lượng số \(0\) tận cùng của \(N\) siêu giai thừa.

Dữ liệu

Một dòng duy nhất chứa số nguyên dương \(N (N \le 10^{9})\).

Kết quả

Ghi ra một số nguyên là số lượng số \(0\) tận cùng của \(sf(N)\).

Ràng buộc

• Có \(25\%\) số test tương ứng với \(25\%\) số điểm thỏa mãn: \(N \le 10^3\).
• Có \(25\%\) số test khác tương ứng với \(25\%\) số điểm thỏa mãn: \(N \le 10^6\).
• Có \(50\%\) số test còn lại tương ứng với \(50\%\) số điểm thỏa mãn: \(N \le 10^{9}\).

Ví dụ

5

1

Giải thích

Các siêu giai thừa đầu tiên \(1, 2, 12, 288, 34560, 24883200, \dots\)

Xâu con của một xâu là xâu đó khi xóa đi một vài ký tự và giữ nguyên thứ tự các ký tự còn lại. Ví dụ, ac, ad, acd là các xâu con của abcd.

Bạn được cho hai xâu \(s\) và \(t\). Nhiệm vụ của bạn là xét tất cả các xâu con khác rỗng của \(s\) và các xâu con khác rỗng của \(t\), đếm xem có bao nhiêu cặp xâu bằng nhau. Vì kết quả rất lớn nên chỉ cần in ra phần dư của kết quả sau khi chia cho \(10^9 + 7\).

aba
abc

4

abc
bac

5

Kiểm tra xem một xâu đã cho có phải là xâu đối xứng không. Xâu đối xứng là xâu đọc ngược hay đọc xuôi đều giống nhau.

Input

• Một dòng duy nhất nhập vào xâu \(s\) \((0 < |s| < 255)\).

Output

• Một dòng duy nhất in ra "YES" nếu xâu \(s\) là dãy đối xứng, "NO" nếu ngược lại.

Example

hah

YES

abc

NO

Cho một mảng gồm \(n\) số nguyên dương \(a_{1}, a_{2}, a_{3},..., a_{n}\). Hỏi có bao nhiêu cặp số \(i < j\) và \(a_{i} = a_{j}\).

Lưu ý: Số lượng này có thể rất lớn nên sử dụng kiểu long long.

Input

• Dòng thứ nhất là chiều dài \(n\) của mảng \((1 \leq n \leq 10^{5})\)
• Dòng thứ hai gồm \(n\) số nguyên \(a_{1}, a_{2}, a_{3},..., a_{n}\) \((1 \leq a_{i} \leq 10^{5})\), mỗi số cách nhau một khoảng trắng.

Output

• Gồm 1 dòng duy nhất là số nguyên xác định số lượng các cặp bằng nhau.

Example

5
8 2 9 8 1  

1

7
6 2 4 2 4 3 4

4

Cho số tự nhiên \(n\). Hãy đếm số chữ số \(0\) tận cùng của \(n!\).

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 20)\) - Số lượng testcase

• \(t\) dòng tiếp theo, mỗi dòng chứa số nguyên \(n(0 \le n \le 10 ^ {18}).\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm.

Example

2
5
25  

1
6

Bạn được cho \(1\) số nguyên dương \(N\).

Viết chương trình tìm giá trị nguyên nhỏ nhất của \(P\). Sao cho với \(1 \leq X \leq P\), \(\Sigma F(X) \geq N\).

Trong đó \(F(X)\) là số lần mà \(X\) có thể chia cho \(5\).

Ví dụ \(F(250)=3, 250/5=50, 50/5=10, 10/5=2\)

\(\Sigma F(X) = F(1) + F(2) + F(3) + ... + F(P).\)

Input

• Dòng đâu tiên chứa số nguyên dương \(T\) \((T \leq 10^5)\) - là số câu hỏi.
• \(T\) dòng, mỗi dòng chứa số nguyên dương \(N\) \((N \leq 10^9)\).

Output

• Gồm \(T\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

2
1
2

5
10

Cho hai xâu \(s\) và \(t\) chỉ gồm các chữ cái thường a...z. Hãy tìm độ dài xâu con chung dài nhất (longest common subsequence) của hai xâu \(s\) và \(t\).

Một xâu con của một xâu \(x\) bất kì thu được bằng cách xóa đi một vài kí tự (có thể không xóa kí tự nào) từ xâu \(x\) và nối những phần tử còn lại mà không thay đổi thứ tự của chúng.

Input

• Dòng thứ nhất chứa xâu \(s\) \((1 \le |s| \le 3000)\).
• Dòng thứ hai chứa xâu \(t\) \((1 \le |t| \le 3000)\).

Output

• In ra độ dài xâu con chung dài nhất cần tìm.

Sample

axyb
abyxb

3