Học sinh giỏi 9 Ninh Bình 2025-2026

Cho bốn số nguyên dương \(a, b, c, d\). Biết rằng \(a, b\) là độ dài 2 cạnh của hình chữ nhật thứ nhất; \(c, d\) là độ dài 2 cạnh của hình chữ nhật thứ hai.

Yêu cầu: Hãy tính diện tích của hai hình chữ nhật và đưa ra diện tích lớn nhất.

Input

• Dữ liệu vào trong tệp HCNMAX.INP theo thứ tự gồm bốn số nguyên dương \(a, b, c, d\) \((a, b, c, d \leq 10^9)\).

Output

• Đưa ra tệp HCNMAX.OUT là diện tích lớn nhất tìm được.

Example

2 4 3 6

18

Số đặc biệt là số chia hết cho tích các chữ số của nó. Ví dụ, số 5 là số đặc biệt vì 5 chia hết cho 5; số 12 là số đặc biệt vì 12 chia hết cho 2 (\(1 \times 2 = 2\)); số 102 không phải là số đặc biệt vì tích các chữ số của nó bằng 0 (\(1 \times 0 \times 2 = 0\)).

Yêu cầu: Cho dãy số \(A\) gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) và 2 số nguyên dương \(l, r\). Hãy liệt kê các số đặc biệt theo đúng thứ tự xuất hiện trong đoạn \(a_l, a_{l+1}, \ldots, a_r\).

Input

• Dòng đầu theo thứ tự gồm ba số nguyên dương \(n, l, r\) (\(1 \leq n \leq 10^5\); \(1 \leq l \leq r \leq n\)).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(a_i \leq 10^9\); \(1 \leq i \leq n\)).

Output

• Gồm duy nhất một dòng ghi các số đặc biệt tìm được, các số cách nhau một dấu cách. Nếu không tìm được số đặc biệt nào thì in ra -1.

Example

8 2 5
2 12 15 20 5 28 36 39

12 15 5

Trong một cuộc thi lập trình Robot, đội của An nhận được xâu tín hiệu S có độ dài không quá \(3 \times 10^6\) kí tự, chỉ gồm các chữ cái thường và chữ số gửi về thông qua đường truyền internet. An cần tách các số từ đoạn tín hiệu này và đếm số lượng số nguyên tố trong các số đã được tách. Biết rằng, mỗi số trong xâu S là một dãy các kí tự chữ số liên tiếp mà có các kí tự liền kề trước hoặc sau (nếu có) là kí tự chữ cái. Các số trong xâu S không vượt quá \(10^6\).

Yêu cầu: Hãy viết chương trình đếm số lượng số nguyên tố được tách ra từ xâu S.

Input

• Dữ liệu vào trong tệp văn bản DEMNT.INP gồm một xâu S chỉ chứa các kí tự chữ cái thường và chữ số.

Output

• Kết quả trong tệp văn bản DEMNT.OUT ghi ra số lượng số nguyên tố trong các số được tách ra.

Example

nb05hsg21bc3956tin19

2

nb1hsg09tin68thcs135

0

Scoring

• Subtask 1: \(25\%\) số test tất cả các số trong xâu S đều có một chữ số.
• Subtask 2: \(50\%\) số test có độ dài của xâu S không vượt quá \(1000\) kí tự.
• Subtask 3: \(25\%\) số test không có ràng buộc gì thêm.

Cho dãy số A gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\), có thể chia dãy số này thành các đoạn liên tiếp sao cho tổng các số trong mỗi đoạn là lũy thừa cơ số 2.

Ví dụ: dãy gồm 6 số \(A = \{5, 3, 1, 1, 1, 3\}\) có 2 cách chia thoả mãn:

• Cách 1: Chia 3 đoạn \(\{5,3\};\{1,1\};\{1,3\}\) có tổng lần lượt là \(8=2^3; 2=2^1; 4=2^2\).
• Cách 2: Chia 4 đoạn \(\{5,3\};\{1\};\{1\};\{1,3\}\) có tổng lần lượt là \(8=2^3; 1=2^0; 1=2^0; 4=2^2\).

Yêu cầu: Em hãy viết chương trình tìm cách chia dãy A trên thành các đoạn con liên tiếp sao cho số lượng đoạn con là ít nhất và tổng các số trong mỗi đoạn là lũy thừa cơ số 2?

Input

• Dòng 1 là số nguyên dương \(n\) \((1 \leq n \leq 10^5)\);
• Dòng 2 gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((0 \leq a_i \leq 2 \times 10^4; 1 \leq i \leq n)\).

Output

• Đưa ra một số nguyên là số đoạn ít nhất chia được. Nếu không chia được thì in ra -1.

Example

6
5 3 1 1 1 3

3

Ràng buộc

• Subtask 1: \(25\%\) số test có tổng tất cả các số trong dãy A là một lũy thừa cơ số 2.
• Subtask 2: \(25\%\) số test có \(n \leq 3\).
• Subtask 3: \(25\%\) số test có \(n \leq 5000\).
• Subtask 4: \(25\%\) số test không có ràng buộc gì thêm.

Một số tự nhiên được gọi là "Số gần chính phương" nếu số đó thỏa mãn đồng thời ba điều kiện sau:

• Có từ 3 chữ số trở lên.
• Chữ số ở hàng cao nhất (hàng đầu tiên bên trái) là một số chính phương.
• Tổng của hai chữ số cuối cùng (hàng chục và hàng đơn vị) là một số chính phương.

Yêu cầu: Cho số nguyên dương \(M\), hãy đếm xem có bao nhiêu số "Số gần chính phương" trong đoạn từ \(1\) đến \(M\).

Input

• Dữ liệu vào từ tệp GCP.INP gồm một số nguyên dương \(M\).

Output

• Đưa ra tệp GCP.OUT gồm một số nguyên duy nhất là số lượng số "Số gần chính phương" tìm được.

Example

105

3

Scoring

• Subtask 1: \(50\%\) số test có \(100 \leq M \leq 999\).
• Subtask 2: \(25\%\) số test có \(1000 \leq M \leq 10^6\).
• Subtask 3: \(25\%\) số test có dạng \(10^K\) với \(6 < K < 18\).