Olympic Truyền thống 30/4 2024 - Tin học - Khối 10

Để chào mừng cuộc thi Olympic 30/4, Hạnh nhận nhiệm vụ trang trí băng rôn chào mừng. Ban đầu, băng rôn là một chuỗi có chiều dài \(n\) chỉ gồm các chữ cái in hoa O, L và P. Một băng rôn được gọi là “đẹp” nếu có chứa một trong các kí tự O, L hoặc P với số lần xuất hiện từ \(3\) trở lên.

Yêu cầu: Cho xâu \(S\) là nội dung của băng rôn ban đầu, hãy đếm số lượng xâu con thỏa điều kiện là băng rôn “đẹp”.

Input

• Một dòng duy nhất chứa xâu \(S\) độ dài \(n\) \((3 \leq n \leq 10^{5})\) chỉ gồm các chữ cái O, L, P.

Output

• Một số nguyên duy nhất là số lượng xâu con thỏa điều kiện là băng rôn “đẹp”.

Scoring

• Subtask \(1\) (\(25\%\) điểm): \(3 \leq n \leq 10^{2}\).
• Subtask \(2\) (\(25\%\) điểm): \(10^{2} < n \leq 10^{3}\).
• Subtask \(3\) (\(50\%\) điểm): \(10^{3} < n \leq 10^{5}\).

Example

OLPPP

3

OLPOLP

0

Hệ thống thoát nước ngầm hiện đại của Vũng Tàu gồm n chốt được đánh số từ \(1\) đến \(n\) với \(m\) đường ống hai chiều nối giữa các cặp chốt có dạng \((i, j)\) với \(i \neq j\) và \(1 \leq i, j \leq n\). Ban đầu, các chốt trong hệ thống được đóng nắp và nước bên ngoài không thể chảy vào hệ thống. Khi có một chốt \(x\) được mở nắp, dòng nước bên ngoài sẽ chảy đến các chốt khác có đường ống thông với chốt \(x\) giúp giảm bớt ngập cho thành phố.

Nhà quản lí muốn mở nắp của không quá \(k\) \((1 \leq k \leq n)\) chốt sao cho có thể dẫn nước từ bên ngoài vào, và thông qua các đường ống để dẫn nước sang nhiều chốt nhất có thể. Mặt khác, để giảm chi phí vận hành, các chốt được mở nắp phải có cùng số lượng đường ống nối đến trực tiếp.

Yêu cầu: Cho biết dòng nước có thể chảy đến được nhiều nhất là bao nhiêu chốt?

Input

• Dòng đầu chứa ba số \(n, m, k\) \(\left(1 \leq k \leq n \leq 10^{5}; 0 \leq m \leq \min⁡\left(\dfrac{n \times (n - 1)}{2},10^{5} \right) \right)\)
• Trong \(m\) dòng tiếp theo, mỗi dòng chứa cặp số \(i, j\) cho biết có đường ống nối trực tiếp giữa chốt \(i\) và \(j\) \((i \neq j; 1 \leq i,j \leq n)\). Dữ liệu đảm bảo giữa cặp chốt \((i, j)\) có nhiều nhất \(1\) đường ống nối trực tiếp.

Output

• Một số nguyên là số lượng chốt nhiều nhất mà nước có thể chảy đến khi mở nắp không quá k chốt và đảm bảo các chốt được mở phải có cùng số lượng đường ống nối trực tiếp (có thể cùng bằng 0).

Scoring

• Subtask \(1\) (\(25\%\) điểm): \(k = 1\).
• Subtask \(2\) (\(25\%\) điểm): \(1 \leq n \leq 100\).
• Subtask \(3\) (\(50\%\) điểm): không có ràng buộc gì thêm.

Example

7 4 3
1 2
2 3
2 6
4 5

6

6 0 5

5

Informath là một sản phẩm robot của câu lạc bộ LQĐ IT. Tập tin dữ liệu huấn luyện cho robot có kích thước không quá \(10^{9}\) byte. Trong quá trình huấn luyện, Robot đọc mỗi lần \(a^{b}\) byte dữ liệu (\(a, b\) là các số nguyên dương nào đó và \(b \geq 2\)) với thời gian đọc \(b\) giây.

Cụ thể, với tập tin kích thước \(n\), robot đọc \(a_{1}^{b_{1}}\) \((a_{1}^{b_{1}} \leq n)\) byte và tốn $b_{1} giây. Nếu \(n - a_{1}^{b_{1}} > 0\), robot đọc tiếp \(a_{2}^{b_{2}}\) byte và tốn \(b_{2}\) giây, cứ như thế robot đọc hết tập tin sau \(k\) lần. Như vậy, ta có: \(n = a_{1}^{b_{1}} + a_{2}^{b_{2}} + \ldots + a_{k}^{b_{k}}\) và thời gian đọc là \(b_{1} + b_{2} + \ldots + b_{k}\).

Kiến thức bổ túc:

• "Các số tự nhiên luôn có thể biểu diễn thành tổng của không quá \(4\) số chính phương (số chính phương là bình phương của một số tự nhiên). Ngoại lệ, các số có dạng \(4^{k} \times (8 \times m + 7)\) thì không thể biểu diễn thành tổng của ít hơn \(4\) số chính phương (\(k, m\) là số tự nhiên)".

Ví dụ:

• \(30 = 5^{2} + 2^{2} + 1^{2}, 4=2^{2},2024 = 42^{2} + 16^{2} + 2^{2}\)
• \(60 = 4^{1} \times (8 \times 1 + 7)\) có dạng \(4^{k} \times (8 \times m + 7)\) nên được biểu diễn từ \(4\) số chính phương trở lên: \(60 = 6^{2} + 4^{2} + 2^{2} + 2^{2}\).

Yêu cầu: Cho số nguyên \(n\). Tính thời gian tối thiểu để robot đọc hết tập tin kích thước \(n\).

Input

• Dòng đầu chứa số nguyên \(T\) \((1 \leq T \leq 5)\) – số tập tin dữ liệu huấn luyện;
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(n\) \((1 \leq n \leq 10^{9})\) – kích thước tập tin.

Output

• Gồm T dòng, mỗi dòng là thời gian ít nhất để đọc tập tin có kích thước tương ứng trong file dữ liệu.

Scoring

Gọi \(N\) là tổng kích thước của \(T\) tập tin

• Subtask \(1\) (\(20\%\) điểm): \(T\) tập tin đều có kích thước không vượt quá \(2^{8}\).
• Subtask \(2\) (\(40\%\) điểm): \(2^{8} < N \leq 2^{16}\).
• Subtask \(3\) (\(50\%\) điểm): \(2^{16} < N \leq 10^{9}\).

Example

1
100000000

2

3
27
128
33

3
4
5