Kỳ thi sơ loại Young ICT năm 2024 - Bảng C2 Problems

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.

Dữ liệu

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.

Kết quả

Ghi ra một số nguyên là độ dài đoạn con liên tiếp dài dấ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\).

Ví dụ

Test 1

Input

14
youngicttalent

Output

Test 2

Input

9
tinhoctre

Output

Bộ ba số Pytago

Nộp bài

Đ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.

Dữ liệu

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.

Kết quả

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.

Ràng buộc

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

Ví dụ

Test 1

Input

7
6 3 5 10 4 5 8

Output

Giải thích

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

Xâu con bằng nhau

Nộp bài

Đ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, Output và Subtask

Input (bàn phím)

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àn hình)

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

Subtask

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

Sample

Input (bàn phím)

aba
abc

Output (màn hình)

Notes

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

Sample

Input (bàn phím)

abc
bac

Output (màn hình)

Notes

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

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

Nộp bài

Đ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, ..., 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 ... \times a_r\) là số chính phương.

Input, Output và Subtask

Input (bàn phím)

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

Output (màn hình)

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

Subtask

\(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 \times 10^6\).
\(48\%\) số điểm còn lại có \(1 \le n \le 5 \times 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 \times 10^6\).

Sample

Input (bàn phím)

5
1 2 8 4 4

Output (màn hình)

Notes

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