Đề thi thử số 2 (theo format HSG9 Bắc Ninh)

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

Cho dãy gồm \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) và hai số nguyên dương \(L, R\). Hãy tìm một dãy con gồm các phần tử liên tiếp có độ dài \(s\) \((L \leq s \leq R)\) có tổng các phần tử là lớn nhất.

Input

• Dòng đầu tiên gồm ba số nguyên \(n, L\) và \(R\) \((1 \leq L \leq R \leq n \leq 10^{5})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((|a_{i}| \le 10^{9})\).

Output

• Gồm một dòng chứa một số là tổng các phần tử là lớn nhất của dãy con tìm được thỏa mãn.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 5000\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

5 2 3
1 3 -1 5 -1

7

Bé Cam hôm nay đến lớp học Toán và được cô dạy về bình phương của một số. Cô cho Cam một bảng \(A\) kích thước \(10^{6} \times 10^{6}\) phần tử. Các dòng được đánh số từ \(1\) đến \(10^{6}\) theo chiều từ dưới lên trên, các cột được đánh số từ \(1\) đến \(10^{6}\) theo chiều từ trái sang phải. Phần tử nằm ở hàng \(i\), cột \(j\) được kí hiệu là \(A_{ij}\) được tính bằng công thức \(A_{ij} = i^{2} + j^{2}\).

Cô giáo tạo ra dãy \(B\) đánh số từ \(1\) đến \(10^{12}\) gồm toàn bộ các phần tử của bảng \(A\) rồi sắp xếp theo thứ tự không giảm. Sau đó cô hỏi Cam xem số thứ \(K\) trong dãy \(B\) có giá trị là bao nhiêu? Lúc đầu cô đưa số \(K\) nhỏ nên Cam còn đếm được. Khi số \(K\) lớn lên, Cam không còn tính nhẩm trong đầu được nữa, Cam muốn các bạn thi Tin học trẻ hôm nay giúp bé tìm đáp án cho câu hỏi của cô giáo nhé. Hình bên là ảnh Cam chụp góc trái dưới cùng bảng \(A\).

Sau khi chuyển các phần tử của bảng \(A\) vào dãy \(B\) và sắp theo thứ tự không giảm thì Cam có những phần tử đầu tiên của dãy \(B\) là \(\{2, 5, 5, 8, 10, 10, 13, 13, 17, 17, 18, \ldots \}\) Khi cô hỏi \(K=5\) thì Cam đã ngay lập tức đưa ra được đáp án là \(10\). Các bạn hãy giúp bé với những số \(K\) lớn hơn nhé.

Input

• Một dòng duy nhất chứa một số nguyên dương \(K\) \((1 \leq K \leq 10^{12})\).

Output

• In ra một số nguyên là số thứ \(K\) trong dãy \(B\).

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(1 \le K \le 10^5\).
• Subtask \(2\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

5

10

Bạn An có một bí mật rất lớn, nên chỉ có \(3\) người bạn tên là \(X, Y, Z\) được phép biết. Để đảm bảo sự bảo mật, An tạo ra một loại mật mã gần giống RSA: An tạo ra \(4\) chiếc khóa, một chiếc khóa tổng có số \(n\) là tích của ba số trên ba chiếc còn lại. An đem ba chiếc khóa đó tặng cho ba bạn.

An đã làm xong chiếc khóa của mình, và tự hỏi mình có bao nhiêu cách làm khóa? Hai cách làm khóa được gọi là khác nhau nếu tồn tại một bạn nhận được hai chìa khóa khác nhau trong hai cách.

Bạn hãy tính giúp An nhé!

Input

• Chứa một số duy nhất là số \(n\) \((1 \leq n \leq 10^{15})\) trên chìa khóa tổng.

Output

• Gồm một số duy nhất là số cách làm khóa cho ba bạn.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \leq 500\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^{6}\).
• Subtask \(3\) (\(15\%\) số điểm): \(n \leq 10^{12}\).
• Subtask \(4\) (\(15\%\) số điểm): không có rằng buộc gì thêm.

Example