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?

Input

• 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)\).

Output

• \(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\).

Example

2
8 3 5 7 1
8 3 5 1 1

YES
NO

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.

Input

• 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.

Output

• 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.

Example

6
123 123 456 321 654 789

3

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\).

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.

Input

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

Output

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

Example

5

1

Scoring

• 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\).

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\).

Input

• Dòng đầu tiên gồm xâu \(s\) có độ dài không quá \(10^4\).
• Dòng tiếp theo gồm xâu \(t\) có độ dài không quá \(10^4\).
• Dữ liệu đảm bảo cả hai xâu chỉ gồm các ký tự in thường từ a đến z.

Output

• Một dòng duy nhất gồm phần dư của số cặp xâu bằng nhau khi chia cho \(10^9 + 7\).

Example

aba
abc

4

abc
bac

5

Scoring

• \(10\%\) số điểm có độ dài xâu \(s\) là \(1\).
• \(10\%\) số điểm khác có độ dài xâu \(s\) là \(2\).
• \(8\%\) số điểm khác có độ dài hai xâu không quá \(10\).
• \(8\%\) số điểm khác có độ dài hai xâu không quá \(15\).
• \(8\%\) số điểm khác có độ dài hai xâu không quá \(20\).
• \(8\%\) số điểm khác có xâu \(s\) chỉ gồm một loại ký tự và có độ dài không quá \(7000\).
• \(8\%\) số điểm khác có độ dài hai xâu không quá \(100\).
• \(8\%\) số điểm khác có độ dài hai xâu không quá \(300\).
• \(8\%\) số điểm khác có độ dài hai xâu không quá \(2000\).
• \(8\%\) số điểm khác có độ dài hai xâu không quá \(5000\).
• \(8\%\) số điểm khác có độ dài hai xâu không quá \(7000\).
• \(8\%\) số điểm còn lại không có giới hạn gì thêm.

Cho một xâu kí tự, hãy kiểm tra tính đối xứng của nó. Một xâu kí tự được gọi là xâu đối xứng nếu ta đọc xâu này từ trái sang phải hoặc từ phải sang trái là như nhau.

Input

• Một xâu ký tự \(S\).

Output

• In ra \(YES\) nếu \(S\) là xâu đối xứng, ngược lại in ra \(NO\).

Constraints

• \(1 \leq S.size() \leq 255\)

Example

abccba 

YES

abcccc 

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