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ục đường sắt quốc gia cần lên kế hoạch xây dựng một nhà ga mới. Họ có lịch trình dự kiến của N chuyến tàu đi qua, trong đó chuyến thứ i sẽ đến ga lúc thời điểm Ai và rời đi lúc thời điểm Bi. Một nền tảng đỗ tàu chỉ có thể phục vụ 1 chuyến tàu tại một thời điểm (nếu tàu này rời đi lúc X thì tàu khác có thể đến đỗ vào đúng lúc X). Hãy tính toán xem nhà ga cần xây tối thiểu bao nhiêu nền tảng đỗ để không có chuyến tàu nào bị hoãn.

Input:

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

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

Dòng 3: N số nguyên Bi (Ai < B_i <= 10^9).

Output: Số lượng nền tảng đỗ tối thiểu cần xây.

Ví dụ:

Input:

3
900 940 950
910 1200 1120

Output:

2

Để chữa một căn bệnh nan y, các bác sĩ cần biến đổi chuỗi gen A thành chuỗi gen B. Hệ thống chỉnh sửa gen cho phép thực hiện 3 thao tác: Chèn thêm 1 ký tự, Xóa đi 1 ký tự, hoặc Thay thế 1 ký tự này bằng 1 ký tự khác. Mỗi thao tác đều tiêu tốn một lượng năng lượng như nhau. Hãy tìm số lượng thao tác ít nhất cần thực hiện để biến chuỗi A thành chuỗi B.

Input:

Dòng 1: Xâu A (chỉ gồm chữ cái thường, độ dài <= 2000).

Dòng 2: Xâu B (chỉ gồm chữ cái thường, độ dài <= 2000).

Output: Số lượng thao tác ít nhất.

Ví dụ:

Input:

horse
ros

Output:

3

(Giải thích: horse -> rorse (thay h bằng r) -> rose (xóa r) -> ros (xóa e)).

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)).