Trong một cuộc thi lập trình đồng đội, có N nam và N nữ. Sức mạnh code của nam thứ i là Ai, của nữ thứ i là Bi. Cần ghép mỗi bạn nam với một bạn nữ thành 1 đội. Độ chênh lệch của đội được tính bằng Ai * Bi. Ban tổ chức muốn tổng độ chênh lệch của tất cả N đội là nhỏ nhất có thể để giải đấu cân bằng.

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

Dòng 2: N số nguyên mảng A (1 <= A_i <= 10^5).

Dòng 3: N số nguyên mảng B (1 <= B_i <= 10^5).

Kết quả ra: Tổng độ chênh lệch nhỏ nhất.

Ví dụ:

Input:

3
3 1 1
6 5 4

Output:

23

(Ghép: 34 + 15 + 16)

Một gói tin được truyền đi chứa toàn bộ các số nguyên từ 1 đến N (không lặp lại). Quá trình truyền tải bị gián đoạn khiến cho đúng 1 con số bị mất tích, nên gói tin nhận được chỉ còn N-1 số. Do bộ nhớ của thiết bị nhận cực kỳ hạn chế (chỉ cho phép dùng O(1) bộ nhớ phụ), bạn hãy sử dụng các phép toán tối ưu để nhanh chóng tìm ra con số đã bị rơi mất.

Input:

Dòng 1: Số nguyên dương N (2 <= N <= 10^6).

Dòng 2: N-1 số nguyên dương là gói tin nhận được.

Output: Con số bị thất lạc.

Ví dụ:

Input:

5
1 4 3 5

Output:

2

Các kỹ sư lập trình phần mềm điều khiển tàu vũ trụ cần kiểm tra tính hợp lệ của một đoạn mã lệnh chỉ chứa các loại ngoặc đơn '()', ngoặc vuông '[]' và ngoặc nhọn '{}'. Một đoạn mã được coi là cân bằng nếu mỗi ngoặc mở đều có một ngoặc đóng tương ứng cùng loại, và chúng phải được đóng theo đúng thứ tự (ngoặc mở sau phải đóng trước). Hãy kiểm tra xem đoạn mã có an toàn để chạy hay không.

Input: Một dòng chứa xâu S chỉ gồm 6 loại ký tự ngoặc (Độ dài <= 10^5).

Output: In ra YES nếu hợp lệ, NO nếu không.

Ví dụ:

Input:

{[()()]}

Output:

YES

Có N bục đá xếp thành hàng ngang, đánh số từ 0 đến N-1. Bục thứ i có ghi số Ai, nghĩa là từ bục này, con ếch có thể nhảy tiến lên phía trước tối đa Ai bước. Ếch đang ở bục 0, hỏi cần ít nhất bao nhiêu lần nhảy để ếch đến được bục N-1? Dữ liệu đảm bảo luôn có cách đi tới đích.

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

Dòng 2: N số nguyên Ai (0 <= Ai <= 10^5).

Kết quả ra: Số lần nhảy ít nhất.

Ví dụ:

Input:

5
2 3 1 1 4

Output:

2

(Nhảy từ 0 đến 1 (1 bước), nhảy từ 1 đến 4 (3 bước)).

Một nông dân đi thu hoạch chè tại đồi chè Tân Cương. Ông mang theo một chiếc gùi có sức chứa tối đa là W kg. Có N luống chè, luống thứ i có tổng khối lượng là wi kg và có tổng giá trị là vi đồng. Do chè có thể hái lẻ tẻ, ông có thể hái một phần của luống chè (ví dụ lấy 1 nửa khối lượng thì được 1 nửa giá trị).

Hãy tính tổng giá trị lớn nhất ông có thể thu được.

Dữ liệu vào:

Dòng 1: Hai số nguyên N và W (1 <= N <= 10^5, 1 <= W <= 10^9).

N dòng tiếp theo: Mỗi dòng chứa hai số nguyên vi và wi (1 <= vi, wi <= 10^6).

Kết quả ra: Tổng giá trị lớn nhất có thể thu được, in ra phần nguyên.

Ví dụ:

Input:

3 50
60 10
100 20
120 30

Output:

240

(Lấy toàn bộ luống 1 và 2, lấy 2/3 luống 3).

Giờ ra chơi, N học sinh đứng thành một hàng ngang. Học sinh thứ i có chiều cao là Hi. Thầy giáo muốn xếp lại hàng sao cho tổng độ chênh lệch chiều cao giữa các học sinh đứng cạnh nhau là lớn nhất. (Tổng = |H1 - H2| + |H2 - H3| + ... + |H{N-1} - H_N|).

Dữ liệu vào:

Dòng 1: Số nguyên N (2 <= N <= 10^5).

Dòng 2: N số nguyên Hi (1 <= Hi <= 10^9).

Kết quả ra: Tổng độ chênh lệch lớn nhất.

Ví dụ:

Input:

4
1 2 4 8

Output:

16

Một lò phản ứng hóa học ghi nhận N chỉ số năng lượng liên tiếp Ai (có thể âm hoặc dương). Độ bùng nổ của phản ứng được tính bằng tổng của một dải các chỉ số liên tiếp. Để đẩy giới hạn lò phản ứng lên mức tối đa, nhà khoa học được cấp quyền can thiệp đặc biệt: Bạn được phép chọn tối đa 1 chỉ số Ai bất kỳ và nhân giá trị của nó với -1 (biến âm thành dương hoặc ngược lại), hoặc không can thiệp gì cả. Hãy tìm độ bùng nổ (tổng dải con liên tiếp) lớn nhất có thể đạt được.

Input:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

Dòng 2: N số nguyên Ai (|Ai| <= 10^4).

Output: Tổng dải con lớn nhất sau khi áp dụng tối đa 1 lần can thiệp.

Ví dụ:

Input:

5
3 -5 2 4 -1

Output:

14

(Giải thích: Dải con chọn là [3, -5, 2, 4]. Can thiệp nhân -1 vào số -5. Dải trở thành [3, 5, 2, 4], tổng = 14).