Thi thử đội tuyển HSG CVAA - Đề 05

Hiện nay, xem ý nghĩa biển số xe, số điện thoại, ngày sinh hay một dãy số nào đó là điều quan tâm của nhiều người. Cách đánh giá số đẹp của dãy số như sau: Tính tổng các chữ số trong dãy, nếu tổng là số có \(1\) chữ thì đó là giá trị số đẹp (độ đẹp của dãy số), ngược lại thì tiếp tục tính tổng các chữ số trong dãy.

Ví dụ:

• Dãy số ngày sinh \(02022020\) có tổng các chữ số là \(8\), vậy độ đẹp của dãy số là \(8\).
• Dãy số điện thoại \(0912345678\) có tổng các chữ số là \(45\), tính tục tính tổng ta được tổng là \(9\), vậy độ đẹp của dãy số là \(9\).

Yêu cầu: Cho dãy số có \(n\) chữ số. Hãy đánh giá độ đẹp của dãy số đã cho.

Input

• Chứa dãy số có \(n\) chữ số (\(n \leq 18\))

Output

• Một số nguyên là độ đẹp của dãy số.

Example

02022020

8

0912345678

9

Ước số chung của dãy số nguyên dương là các số nguyên dương mà tất cả các số trong dãy đều chia hết cho nó. Hôm nay, Tuấn đang học về ước số chung và Tuấn được thầy giáo cho bài toán: Có một dãy số \(A\) gồm \(N\) số nguyên dương, hãy tìm ước số chung nhỏ nhất khác \(1\). Nói cách khác, Tuấn cần tìm số \(D\) nhỏ nhất, sao cho \(D > 1\) và các số trong dãy số \(A\) đều chia hết cho số \(D\) này.

Yêu cầu: Cho một số \(A\) gồm \(N\) số nguyên dương, hãy giúp Tuấn đưa ra số là Ước số chung nhỏ nhất khác \(1\).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(N\leq 10^5\))
• Dòng tiếp theo gồm \(N\) số nguyên dương \(A_i\) là các phần tử của dãy \(A\) (\(A_i\leq 10^6\)).

Output

• Một số nguyên dương ước chung nhỏ nhất của dãy số. Nếu không tồn tại số siêu nguyên dương nào, in ra \(-1\).

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(N\leq 10^3\), \(A_i\leq 10^5\).
• Subtask \(2\) (\(40\%\) số điểm): Không có ràng buộc gì thêm

Example

3
1 2 3

-1

3
2 4 6

2

Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1, A_2, …, A_n\). Mỗi phần tử có giá trị không vượt quá \(10^9\) và \(1 \lt n \leq 5000\). Một bộ ba số được gọi là bộ số tam giác, nếu ba số này tạo thành ba cạnh của một tam giác nào đó.

Yêu cầu: Hãy đếm xem trong dãy \(A\) có bao nhiêu bộ số tam giác (\(A_i, A_j, A_k\)) với \(i, j, k\) đôi một khác nhau.

Input

• Dòng đầu là số \(n\).
• Dòng tiếp theo là các phần tử của dãy \(A\), mỗi phần tử cách nhau một dấu cách.

Output

• Ghi ra số lượng bộ số tam giác.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(100 \lt n \leq 1000\).
• Subtask \(3\) (\(40\%\) số điểm): \(1000 \lt n \leq 5000\).

Example

5
4 3 1 5 7 

3

Một xâu gọi là xâu nhị phân nếu chỉ chứa hai ký tự \(0\) hoặc \(1\).

Xâu \(v\) gọi là xâu con của \(w\) nếu xâu \(v\) có độ dài khác 0 và gồm các ký tự liên tiếp trong xâu \(w\).

Ví dụ: xâu \(010\) có các xâu con là: \(0, 1, 0, 01, 10, 010\).

Yêu cầu: Cho trước một giá trị \(k\), hãy đếm xem có bao nhiêu xâu con chứa đúng \(k\) ký tự \(1\).

Input

• Dòng \(1\): chứa một số nguyên \(k (0 \leq k \leq 10^6)\).
• Dòng \(2\): chứa một xâu nhị phân có độ dài \(\leq 10^6\).

Output

• Ghi ra một số nguyên duy nhất là kết quả tìm được.

Scoring

• \(len(s)\) là độ dài xâu nhị phân.
• Subtask \(1\) (\(40\%\) số điểm): \(1 \leq k \leq len(s) \leq 500\).
• Subtask \(2\) (\(30\%\) số điểm): \(1000 \leq k \leq len(s) \leq 10000\).
• Subtask \(3\) (\(30\%\) số điểm): \(10^5 \leq k \leq len(s) \leq 10^6\).

Example

2
01010 

4