Xâu TH là xâu có độ dài không quá 10^6, khác rỗng và chỉ chứa hai ký tự 'T' hoặc 'H'. Xâu S1 gọi là xâu con của xâu S2 nếu xâu S1 có độ dài khác 0 và gồm các ký tự liên tiếp trong xâu S2. Ví dụ: xâu "THT" có các xâu con là "T","H","T","TH","HT","THT".

Yêu cầu: Cho S là xâu TH có độ dài n và số nguyên k. Hãy tính số lượng xâu con của S chứa đúng k ký tự 'H'.

Dữ liệu: Vào từ tệp văn bản STRING.INP gồm:

• Dòng đầu tiên chứa một số nguyên k (0≤k≤n≤10^6);
• Dòng tiếp theo chứa xâu S có độ dài không quá 10^6.

Kết quả: Ghi ra tệp văn bản STRING.OUT gồm một số nguyên duy nhất là số lượng xâu con chứa đúng k kí tự 'H'.

Ví dụ:

STRING.INP      STRING.OUT
2               6
THTHTH

Ràng buộc:

Có 10% số test ứng với 10% số điểm của bài thoả mãn k=0,n≤10^6;
Có 30% số test ứng với 30% số điểm của bài thoả mãn k≥1,n≤100;
Có 30% số test ứng với 30% số điểm của bài thoả mãn k≥1,100<n≤1000;
Có 30% số test ứng với 30% số điểm của bài thoả mãn k≥1,1000<n≤10^6.

Xét bài toán: Cho n phân số a1/b1 ,…,an/bn (ai,bi nguyên dương), hãy tìm dãy chỉ số 1 ≤ i1 < i2 <⋯< ik ≤ n sao cho a (i1) / b (i1) < a (i2) / b (i2 ) <⋯< a (ik) / b (i_k) và k lớn nhất có thể.

Bài toán trên được mở rộng như sau: Có thể đảo lại một phân số nếu muốn (phân số ai / bi đảo lại thành phân số bi / ai ), sau đó tìm dãy chỉ số thỏa mãn đề bài mà k lớn nhất có thể.

Yêu cầu: Cho n phân số và số nguyên w, trong đó 𝑤 = 0 nghĩa là không được phép đảo bất kỳ một phân số nào (bài toán ban đầu) hoặc 𝑤 = 1 nếu được phép đảo không quá một phân số (bài toán mở rộng), hãy đưa ra giá trị 𝑘 lớn nhất có thể.

Dữ liệu: Vào từ tệp văn bản FRACTION.INP theo khuôn dạng:

Dòng đầu ghi hai số nguyên n,w(1≤n≤10^3;0≤w≤1);
Dòng thứ i trong n dòng tiếp theo chứa hai số nguyên dương a_i,b_i lần lượt là tử số và mẫu số của phân số thứ i (1≤i≤n,〖0<a〗_i,b_i≤10^9).

Kết quả: Ghi ra tệp văn bản FRACTION.OUT một số nguyên duy nhất là giá trị k lớn nhất tìm được.

Ví dụ:

FRACTION.INP    FRACTION.OUT
4 0             2
5 1
1 3
3 2
1 2 


4 1             3
5 1
1 3
3 2
1 2

Ràng buộc:

• Có 25% số test ứng với 25% số điểm của bài thỏa mãn: n≤10,w=0;
• Có 25% số test ứng với 25% số điểm của bài thỏa mãn: n≤10,w=1;
• Có 25% số test ứng với 25% số điểm của bài thỏa mãn: 10<n≤10^3,w=0; </li>
• Có 25% số test ứng với 25% số điểm của bài thoả mãn: 10<n≤10^3,w=1.</li>

Thành phố bạn Lam sống có n nút giao thông được đánh số từ 1 đến n. Việc đi lại giữa các nút giao thông được thực hiện qua các tuyến xe bus. Có tất cả m tuyến, tuyến thứ i cho phép di chuyển hai chiều từ nút giao thông ai đến bi (ai≠bi) và có tiền vé một lượt đi là c_i. Các tuyến xe bus được xây dựng để đảm bảo mọi cặp nút giao thông trong thành phố đều có thể liên thông với nhau thông qua một số tuyến xe trực tiếp hoặc gián tiếp. Nhà của Lam ở nút giao thông s còn trường học thì ở nút giao thông t. Do tiết kiệm chi phí, Lam đã tìm một con đường thông qua một số tuyến xe bus để di chuyển từ nhà tới trường với tổng tiền vé ít nhất. Để thuận tiện hơn, Lam đã mua vé năm cho tất cả các tuyến trên con đường đó. Các tuyến đã mua vé năm thì trong năm đó có thể đi lại mà không cần trả phí nữa. Ngoài việc thường xuyên đi lại từ nhà tới trường, Lam còn rất hay di chuyển từ thư viện ở nút giao thông u tới trung tâm Anh ngữ ở nút giao thông v. Do đó, Lam muốn lựa chọn con đường từ nhà tới trường sao cho chi phí di chuyển từ u tới v là nhỏ nhất.

Yêu cầu: Tìm chi phí nhỏ nhất để Lam di chuyển từ u tới v sau khi đã mua vé năm cho con đường từ s tới t theo như mô tả trên.

Dữ liệu: Vào từ tệp BUS.INP gồm:

Dòng đầu chứa 2 số nguyên dương n và m (n ≤10^5,m≤2.10^5 );
Dòng thứ hai chứa 2 số nguyên dương s và t (s,t≤n);
Dòng thứ ba chứa 2 số nguyên dương u và v (u,v≤n);
Dòng thứ i trong m dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương a_i,b_i,c_i mô tả tuyến xe bus thứ i (a_i,b_i≤n, c_i≤10^9; 1≤i≤m).

Kết quả: Ghi ra tệp BUS.OUT một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

    BUS.INP         BUS.OUT
    8 8             5
    1 6
    3 8
    1 2 3
    2 4 2
    2 3 3
    4 5 1
    3 5 2
    5 6 3
    2 7 4
    8 2 3
    GIẢI THÍCH
    - Đường đi từ s đến t: (1)→(2) →(4) →(5) →(6) có chi phí nhỏ nhất là 9.
    - Đường đi từ u đến v: (3)→(5) →(4) →(2) →(8) có chi phí nhỏ nhất là 5 do chỉ phải trả thêm tiền vé cho tuyến (3)→(5) và (2) →(8).

Ràng buộc:

• Có 50% số test ứng với 50% số điểm của bài thoả mãn chỉ có duy nhất một con đường ngắn nhất đi từ s tới t;
• Có 50% số test ứng với 50% số điểm của bài không có ràng buộc gì thêm.