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.