2026 · HSG THCS · Đà Nẵng

Cho một xâu ~S~ có độ dài ~N~ kí tự, ghi lại hành trình di chuyển của một Robot trên lưới các ô vuông. Trong xâu ~S~ chứa các kí tự ~U, D, L, R~ tương ứng với các hướng di chuyển, mỗi lần di chuyển một ô vuông với: ~U~ - lên trên, ~D~ - xuống dưới, ~L~ - sang trái, ~R~ - sang phải.

Yêu cầu: Hãy tìm tọa độ của Robot khi kết thúc hành trình, biết rằng ban đầu Robot xuất phát tại tọa độ ~(0, 0)~.

Input

• Dòng thứ nhất chứa số nguyên dương ~N (N \leq 10^5)~.
• Dòng thứ hai chứa xâu ~S~.

Output

• Hai số nguyên ~x~ và ~y~ cách nhau một kí tự trống, là tọa độ của Robot khi kết thúc hành trình.

Sample Input 1

10
UULLDRDDR

Sample Output 1

0 -1

Số nguyên tố lệch là một số nguyên dương thỏa mãn cả 2 điều kiện: Là số nguyên tố và số lượng chữ số chẵn khác số lượng chữ số lẻ.

Yêu cầu: Cho dãy có ~N~ số nguyên dương ~a_1,a_2,a_3,...,a_n~. Hãy đếm số lượng số nguyên tố lệch trong dãy.

Input

• Dòng thứ nhất chứa số nguyên dương ~N(N \le 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1,A_2,A_3,...,A_N (A_i \le 10^6)~ mỗi số cách nhau một ký tự trống.

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Sample Input 1

5
23 232 311 15 60

Sample Output 1

1

Note

• Các số nguyên tố trong dãy số là ~23,311~. Trong đó ~23~ không phải số nguyên tố lệch vì có một chữ số chẵn và một chữ số lẻ, số ~311~ là số nguyên tố lệch vì có ba chữ số lẻ và không chữ số chẵn.

Ràng buộc

Một công ty Logistics có ~k~ Drone giao hàng. Công ty nhận một đơn hàng vận chuyển ~n~ thùng hàng, các thùng hàng được đánh số thứ tự từ ~1~ đến ~n~ , thùng hàng thứ ~i~ có trọng lượng là ~a_i~.

Mỗi Drone tham gia sẽ vận chuyển các thùng hàng liên tiếp trong đơn hàng mà không làm thay đổi thứ tự các thùng hàng. Năng lượng vận hành của mỗi Drone được tính bằng tổng trọng lượng của các thùng hàng trên Drone. Chi phí của đơn hàng được tính bằng năng lượng vận hành lớn nhất trong các Drone tham gia vận chuyển.

Yêu cầu: Tính chi phí thấp nhất để vận chuyển đơn hàng.

Input

• Dòng thứ nhất chứa số nguyên dương ~n~ và ~k~ mỗi số cách nhau một kí tự trống ~(k \le n)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a1,a2,a3,...an mỗi số cách nhau một ký tự trống.

Output

• Một số nguyên duy nhất là chi phí thấp nhất để vận chuyển đơn hàng.

Sample Input 1

5 2
1 3 2 3 5

Sample Output 1

8

Note: Drone 1 vận chuyển các thùng hàng có trọng lượng ~1,3,2~. Drone 2 vận chuyển các thùng hàng có trọng lượng ~3,5~. Chi phí vận chuyển đơn hàng được tính bằng năng lượng vận hành của Drone 2: ~3+5=8~.

Sample Input 2:

5 3
1 1 2 3 4

Sample Output 2:

4

Note: Drone 1 vận chuyển các thùng hàng có trọng lượng ~1,1,2~. Drone 2 vận chuyển các thùng hàng có trọng lượng ~3~. Drone 3 vận chuyển các thùng hàng có trọng lượng ~4~. Chi phí vận chuyển đơn hàng được tính bằng năng lượng vận hành của Drone 1: ~1+1+2=4~ hoặc Drone 3: ~4~.

Ràng buộc

Đoạn con của dãy số là một dãy các số được tạo thành từ các phần tử liên tiếp của dãy số ban đầu.

Độ đẹp của một dãy số là một số nguyên dương ~X~ nhỏ nhất sao cho ta có thể chia dãy số ban đầu thành ~X~ đoạn con không giao nhau và tổng của tất cả các số trong mỗi đoạn con không lớn hơn ~S~.

Ví dụ: Với ~S = 8~, đoạn ~[2, 3, 5]~ có thể chia thành:

• ~([2, 3], [5])~
• ~([2], [3, 5])~
• ~([2], [3], [5])~

Vì cần tìm ~X~ nhỏ nhất nên đoạn ~[2, 5, 3]~ có độ đẹp là ~2~.

Độ đẹp hoàn hảo của dãy số là tổng độ đẹp của tất cả đoạn con của nó.

Yêu cầu: Cho dãy số nguyên dương ~A_1,A_2,A_3,...,A_N~. Tính độ đẹp hoàn hảo của dãy số đã cho.

Input

• Dòng thứ nhất chứa hai số nguyên dương ~N~ và ~S~. (~N ≤ 10^5~, ~S ≤ 10^9~)
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ (~A_i ≤ 10^6~)

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Sample Input 1

4 8
1 2 5 3

Sample Output 1

12

Dãy ~1, 2, 5, 3~ có các đoạn con là:
$$~[1]~, ~[2]~, ~[5]~, ~[3]~, ~[1, 2]~, ~[2, 5]~, ~[5, 3]~, ~[1, 2, 5]~, ~[2, 5, 3]~, ~[1, 2, 5, 3]~$$

Trong đó:

• ~[1]~, ~[2]~, ~[5]~, ~[3]~, ~[1, 2]~, ~[2, 5]~, ~[5, 3]~, ~[1, 2, 5]~ có độ đẹp là ~1~.
• ~[2, 5, 3]~, ~[1, 2, 5, 3]~ có độ đẹp là ~2~.

Vậy độ đẹp hoàn hảo bằng:
$$~1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 2 = 12~$$

Subtasks