Bài kho khó

Bài 1: Dãy con tổng bằng 0 DAY0

Cho dãy số nguyên a=(a₁, a₂, .... , a_n),1 ≤ n ≤ 10000,-10000 ≤ a_i  ≤ 10000

Hãy tìm 1 dãy đoạn dài nhất gồm các phần tử liên tiếp trong dãy a có tổng bằng 0.

Input

·       Dòng 1 chứa số n

·       Dòng 2 chứa n số a1, a2, ... , an theo đúng thứ tự cách nhau ít nhất 1 dấu cách

Lưu ý Dữ liệu luôn cho hợp lí để tồn tại 1 doạn các phần tử liên tiếp có tổng bằng 0.

Output: 2 số là số thứ tự của phần tử đầu tiên và phần tử cuối cùng của dãy liên tiếp có tổng bằng 0. Nếu có nhiều đoạn, xuất đoạn đầu tiên tìm được.

Ví dụ:

Input	Output
9 2 7 5 -3 -2 4 -9 -2 -1	2 8

      B          Bài 2:Xuất hiện XUATHIEN

Cho dãy a có m phần tử nguyên a₁, a₂, …, a_m. Dãy b có n phần tử nguyên b₁, b₂, …, b_n. Cho biết có bao nhiều phần tử trong dãy a xuất hiện trong dãy b.

Input

Dòng đầu gồm 2 số m, n (0 < m, n ≤ 107)

m dòng tiếp theo, dòng thứ i là số nguyên ai (|ai| ≤ 109)

n dòng tiếp theo, dòng thứ i là số nguyên bi (|bi| ≤ 109)

Output: Số lượng phần tử trong dãy a xuất hiện trong b.

Ví dụ:

Input	Output
3 5 1 2 3 1 3 5 4 3	2