Kỳ thi sơ loại Young ICT năm 2024 - Bảng C2 - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Xâu ICT	100 (p)	1.0s	512M
2	Bộ ba số Pytago	100 (p)	1.0s	512M
3	Xâu con bằng nhau	100 (p)	1.0s	512M
4	Đoạn con chính phương	100 (p)	1.0s	256M

1. Xâu ICT

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Xâu ICT là một xâu kí tự chỉ chứa ba loại kí tự i, c hoặc t. Bạn được cho một xâu kí tự \(S\) có độ dài \(N\), chỉ chứa các kí tự chữ cái in thường từ a đến z.

Yêu cầu: Hãy tìm một đoạn xâu con liên tiếp dài nhất là xâu ICT.

Input

Dòng đầu chứa số nguyên dương \(N\) (\(N \le 10^6\)).
Dòng thứ hai chứa xâu \(S\), bao gồm \(N\) kí tự chữ cái in thường từ a đến z.

Output

Ghi ra một số nguyên là độ dài đoạn con liên tiếp dài nhất là xâu ICT.

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ó \(50\%\) số test còn lại tương ứng với \(50\%\) số điểm thỏa mãn: \(N \le 10^6\).

Example

Test 1

Input

14
youngicttalent

Output

Test 2

Input

9
tinhoctre

Output

2. Bộ ba số Pytago

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

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

Một bộ ba số Pythago gồm ba số nguyên dương \(a\), \(b\), và \(c\) sao cho \(a^2 + b^2 = c^2\) hoặc \(a^2 + c^2 = b^2\) hoặc \(b^2 + c^2 = a^2\).

Yêu cầu: Hãy tìm số lượng bộ ba phần tử của dãy \(A\) là một bộ ba số Pythago.

Input

Dòng đầu tiên, chứa một số nguyên dương \(N\) (\(N \le 10^6\)).
Dòng thứ hai, chứa \(N\) số nguyên dương, \(A_1, A_2, A_3, \dots, A_N\) (\(A_i \le 1000\)).

Các dữ liệu trên cùng một dòng cách nhau bởi chính xác một dấu cách.

Output

In ra màn hình, số lượng bộ số \((i, j, k)\) thỏa mãn \(1 \le i < j < k \le N\) và \((A_i, A_j, A_k)\) là một bộ ba số Pytago.

Example

Test 1

Input

7
6 3 5 10 4 5 8

Output

Note

Các bộ số \((i, j, k)\) thỏa mãn điều kiện là \((2, 3, 5)\), \((2, 5, 6)\) và \((1, 4, 7)\).

Scoring

\(25\%\) số test tương ứng với \(25\%\) điểm thỏa mãn \(N \le 100\).
\(25\%\) số test khác tương ứng với \(25\%\) điểm thỏa mãn \(N \le 5000\).
\(25\%\) số test khác tương ứng với \(25\%\) điểm thỏa mãn \(N \le 10^6\) và \(A_i \le 100\).
\(25\%\) số test còn lại tương ứng với \(25\%\) điểm thỏa mãn \(N \le 10^6\) và \(A_i \le 1000\).

3. Xâu con bằng nhau

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

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

Test 1

Input

aba
abc

Output

Note

Các xâu con của xâu aba là: a, b, a, ab, aa, ba, aba.
Các xâu con của xâu abc là: a, b, c, ab, ac, bc, abc.
Số cặp xâu con bằng nhau là \(4\).

Test 2

Input

abc
bac

Output

Note

Các xâu con của xâu bac là: b, a, c, ba, bc, ac, bac.
Số cặp xâu con bằng nhau là \(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.

4. Đoạn con chính phương

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một dãy số nguyên dương \(a_1, a_2, \ldots, a_n\). Đếm số cặp \((l, r)\) sao cho \(1 \le l \le r \le n\) và \(a_l \times a_{l + 1} \times \ldots \times a_r\) là số chính phương.

Input

Dòng đầu tiên gồm một số nguyên dương \(n\) (\(1 \le n \le 5 \cdot 10^5\)).
Dòng tiếp theo gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 5 \cdot 10^6\)).

Output

Một dòng duy nhất gồm số cặp \((l, r)\) tìm được.

Example

Test 1

Input

5
1 2 8 4 4

Output

Note

Ví dụ, với \(l = 1, r = 5\) ta có \(a_1 \times a_2 \times a_3 \times a_4 \times a_5 = 1 \times 2 \times 8 \times 4 \times 4 = 256 = 16^2\), do đó \((1, 5)\) là một cặp thỏa mãn.
Các cặp \((l, r)\) thỏa mãn là: \((1, 1), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (4, 4), (4, 5), (5, 5)\).

Scoring

\(10\%\) số điểm có \(1 \le n \le 10\) và \(1 \le a_i \le 12\).
\(12\%\) số điểm tiếp theo có \(1 \le n \le 100\), trong đó:
- \(6\%\) số điểm có \(1 \le a_i \le 100\).
- \(6\%\) số điểm còn lại có \(1 \le a_i \le 10^5\).
\(30\%\) số điểm tiếp theo có \(1 \le n \le 1000\), trong đó:
- \(8\%\) số điểm có \(a_i\) là số nguyên tố.
- \(8\%\) số điểm khác có \(1 \le a_i \le 100\).
- \(8\%\) số điểm khác có \(1 \le a_i \le 1000\).
- \(6\%\) số điểm còn lại có \(1 \le a_i \le 5 \cdot 10^6\).
\(48\%\) số điểm còn lại có \(1 \le n \le 5 \cdot 10^5\), trong đó:
- \(10\%\) số điểm có \(a_i = 1\).
- \(10\%\) số điểm khác có \(a_i = 2\).
- \(8\%\) số điểm khác có \(1 \le a_i \le 2\).
- \(8\%\) số điểm khác có \(1 \le a_i \le 3\).
- \(6\%\) số điểm khác có \(1 \le a_i \le 100\).
- \(4\%\) số điểm khác có \(1 \le a_i \le 10^5\).
- \(2\%\) số điểm còn lại có \(1 \le a_i \le 5 \cdot 10^6\).