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

Huy đang học số học và rất yêu thích số \(x\). Nhưng vì chỉ yêu thích một số, nên khi được hỏi đưa ra nhiều số, Huy đã nghĩ ra định nghĩa “số gần yêu thích”. Số gần yêu thích là số khác số yêu thích và kết thúc bằng số yêu thích của Huy.

Ví dụ, khi \(x=24\) thì các số gần yêu thích là \(124,3524,22224,…\); các số \(204,2432,2240,…\) không phải số gần yêu thích.

Yêu cầu: Cho 2 số nguyên \(x,m\). Đếm số lượng số gần yêu thích không vượt quá \(m\).

Input

• Gồm 2 số nguyên \(x,m\ (1≤x≤10^5,1≤m≤10^{18})\).

Output

• Một số nguyên dương là số lượng số gần yêu thích tìm được.

Scoring

• 35% số test \(x<10;m≤1000\);
• 30% số test có \(m≤100000\);
• 35% số test còn lại không có ràng buộc bổ sung.

Example

3 17

1

24 1000

9

Một cuộc thi lập trình điều khiển robot được ban tổ chức olympic 30-4 thiết kế cho các bạn yêu thích Tin học. Ban tổ chức thiết kế một sơ đồ cho robot di chuyển gồm \(n\) địa điểm được đánh số từ 1 tới \(n\) và được nối với nhau bởi \(m\) con đường hai chiều, đánh số từ 1 tới \(m\). Con đường thứ \(i\) nối hai địa điểm \(u_i\) và \(v_i\) với trọng số \(w_i\ (1≤u_i,v_i≤n;w_i≤10^9)\). Tại mỗi địa điểm ghi một số nguyên \(a_i\) là số điểm thưởng mà robot nhận được khi đến địa điểm này lần đầu.

Ban tổ chức chọn một địa điểm \(s\) làm địa điểm xuất phát và robot nhận được điểm thưởng đầu tiên tại địa điểm này. Mỗi khi đi qua con đường có trọng số lớn hơn điểm thưởng đang có, robot sẽ nhận một thẻ phạt. Robot được phép bị phạt không quá \(k\) thẻ. Khi bị phạt thẻ, robot sẽ không được phép nhận thêm điểm thưởng ở bất kỳ địa điểm nào nữa.

Yêu cầu: Hãy xác định số địa điểm lớn nhất mà robot có thể đi qua.

Input

• Dòng đầu tiên chứa 4 số nguyên \(n,m,s\) và \(k\ (1≤n≤10^5;1≤m≤2×10^5; 1≤s≤n;k≤1)\);
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n\ (1≤a_i≤10^9 )\);
• Dòng thứ \(i\) trong \(m\) dòng tiếp theo chứa 3 số nguyên \(u_i,v_i\) và \(w_i\ (1≤u_i≠v_i≤n;1≤w_i≤10^9)\).

Output

• Một số nguyên duy nhất là số địa điểm tối đa mà robot có thể đi qua.

Scoring

• \(30\%\) số điểm có \(m=n-1<10^3;u_i=i; v_i=i+1;k=0\);
• \(20\%\) số điểm có \(k=0;n≤10^3\);
• \(20\%\) số điểm có \(k=0;n≤10^5\);
• \(30\%\) số test có \(k=1\).

Example

6 7 3 1
3 4 2 3 2 7
1 6 10
1 5 8
5 2 12
2 6 10
2 3 5
3 4 1
3 5 11  

5

Một cửa hàng nọ có một thanh gỗ kích thước \(1×n\) dùng để nuôi ốc sên. Người ta đã dùng bút đánh dấu, chia thanh gỗ thành \(n\) ô vuông có độ dài cạnh bằng nhau; được đánh số từ \(1\) đến \(n\) từ trái sang phải. Do thanh gỗ không đều, các ô có thể có mức độ phù hợp khác nhau cho ốc sên; độ phù hợp của ô thứ \(i\) là \(a_i\). Một số con ốc sên đã được đặt lên thanh gỗ, thoả mãn mỗi con ốc sên nằm gọn vào một ô và mỗi ô đều chứa không quá một con ốc sên.

Quyên đến cửa hàng để mua ốc sên về nuôi. Cậu dự định phương án là mua các ô từ \(L\) đến \(R\) và các con ốc sên ở trên đó. Vì Quyên muốn nuôi riêng từng con ốc nên chủ cửa hàng sẽ phải cắt phần gỗ được chọn thành một số đoạn, sao cho trên mỗi đoạn có đúng một con ốc sên. Cụ thể hơn, giả sử có \(k\) con ốc sên trên đoạn \([L,R]\), chủ cửa hàng cần cắt đoạn \([L,R]\) thành đúng \(k\) đoạn sao cho mỗi đoạn có đúng một con ốc sên và không có đoạn nào của \([L,R]\) bị thừa ra. Để ốc phát triển tốt, một con ốc sên (trong số vừa được chọn ra) sẽ chỉ được bán nếu tổng độ phù hợp của các ô của đoạn mà nó đứng là không âm. Tức là, con ốc trên đoạn \([u,v]\) được bán nếu \(a_u+a_{u+1}+⋯+a_v≥ 0\). Do có thể có nhiều cách cắt khác nhau, chủ cửa hàng muốn cắt sao cho bán được nhiều ốc sên nhất có thể.

Yêu cầu: Quyên đưa ra \(Q\) dự định mua, dự định thứ \(i\) được mô tả bởi hai số nguyên dương \(L_i,R_i\). Hãy giúp chủ cửa hàng tìm cách cắt cho từng dự định, sao cho số lượng ốc sên bán được cho dự định đó là lớn nhất có thể và in ra số lượng đó. Lưu ý Quyên chỉ đưa ra các dự định và chủ cửa hàng đưa ra giải pháp chứ chưa thực sự cắt thanh gỗ ban đầu.

Input

• Dòng đầu chứa hai số nguyên dương \(n,Q\ (n,Q≤ 5× 10^5)\);
• Dòng tiếp theo chứa một xâu nhị phân độ dài \(n\), ký tự thứ \(i\) là 0 hoặc 1 tương ứng là ô thứ \(i\) không đặt hoặc có đặt một con ốc sên;
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1,a_2,…,a_n\ (|a_i |≤10^9)\);

• Dòng thứ \(i\) trong số \(Q\) dòng tiếp theo chứa hai số nguyên \(L_i,R_i\ (1≤L_i≤R_i≤n)\).

  Dữ liệu bảo đảm có ít nhất một con ốc sên trong đoạn \([L_i,R_i ],i=1,2,…,Q\).

Output

• Ghi ra trên \(Q\) dòng, dòng thứ \(i\) ghi một số nguyên là số ốc sên bán được nhiều nhất với dự định thứ \(i\) của Quyên.

Scoring

• Có \(16\%\) số test có \(a_i≥0 ∀i=1,2,3,…,n;n≤8000;Q=1\);
• Có \(14\%\) số test có \(n≤8000;Q=1\) và \(a_i=0\) nếu ô thứ \(i\) có ốc sên, \(a_i<0\) nếu ô thứ \(i\) không có ốc sên;
• Có \(16\%\) số test với \(n≤8000;Q=1\);
• Có \(12\%\) số test với \(n,Q≤8000\);
• Có \(18\%\) số test với \(n,Q≤ 50000\);
• Có \(24\%\) số test với ràng buộc gốc.

Example

8 5
01001101
1 -2 1 2 -1 2 1 -3
1 8
1 5
2 5
5 8
1 2 

3
2
1
1
0