Độ khó: Khá (3/4 điểm)

Một dãy số gồm ~M~ phần tử ~a_1, a_2, \ldots, a_M~ được gọi là dãy số hai phía nếu thoả mãn điều kiện sau:

• ~M~ chẵn, khi đó chia dãy thành hai phần ~\{a_1, a_2, \ldots, a_{M/2}\}~ và ~\{a_{M/2+1}, \ldots, a_M\}~;
• Các phần tử ở mỗi phần có giá trị bằng nhau. Tức là ~a_1 = a_2 = \cdots = a_{M/2}~ và ~a_{M/2+1} = \ldots = a_M~;
• Giá trị của hai phần phải khác nhau. Tức là ~a_1 \ne a_M~.

Ví dụ:

• Dãy số hai phía: ~\{0, 0, 0, 1, 1, 1\}~, ~\{1, 1, 2, 2\}~, …
• Không phải dãy hai phía: ~\{1, 1, 0\}~, ~\{0, 0, 2, 1\}~, ~\{2, 2\}~, …

Cho dãy số gồm ~N~ phần tử, mỗi phần tử nhận một trong ba giá trị ~0, 1, 2~ và số nguyên dương ~K~. Hãy thay đổi không quá ~K~ phần tử của dãy số để được dãy con dài nhất là dãy số hai phía.

Dữ liệu vào từ tệp văn bản DSHP.INP:

• Dòng đầu tiên chứa hai số nguyên ~N, K~ ~(1 \le K \le N \le 10^5)~;
• Dòng tiếp theo chứa ~N~ số ~0~ hoặc ~1~ hoặc ~2~ mô tả dãy số ban đầu.

Kết quả ghi ra tệp văn bản DSHP.OUT:

Một số nguyên duy nhất là độ dài lớn nhất của dãy số hai phía tìm được, sau khi thay đổi không quá ~K~ số của dãy số đã cho.

Ràng buộc:

• Có ~50\%~ số test ứng với ~50\%~ số điểm thoả mãn: ~1 \le K \le N \le 10^2~;
• ~30\%~ số test khác ứng với ~30\%~ số điểm thoả mãn: ~1 \le K \le N \le 10^3~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc gì thêm.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input 1

7 3
2 1 2 0 0 2 1

Sample Output 1

6

Giải thích: Có thể thay đổi thành dãy số: ~2, 2, 2, 0, 0, 0, 1~. Hoặc cũng có thể thay đổi thành dãy số: ~1, 1, 1, 0, 0, 0, 1~.

Sample Input 2

4 2
1 1 0 0

Sample Output 2

4

Giải thích: Không cần thay đổi phần tử nào trong dãy số.

Độ khó: Khá (3/4 điểm)

Cho xâu ~S~ gồm các chữ cái tiếng Anh in thường. Gọi ~f(S)~ là số lượng kí tự phân biệt của xâu ~S~.

Ví dụ ~S = \texttt{"abccaaa"}~, vậy ~f(S) = 3~.

Với mỗi ~K~ có giá trị từ ~1~ đến ~f(S)~, hãy đếm số lượng xâu con ~X~ của ~S~ có ~f(X) = K~.

Dữ liệu vào từ tệp văn bản KTPB.INP:

Gồm một xâu ~S~ (có số lượng kí tự - kí hiệu là ~|S|~ không vượt quá ~10^6~).

Kết quả ghi ra tệp văn bản KTPB.OUT:

Gồm ~f(S)~ dòng, mỗi dòng là kết quả tương ứng khi ~K~ có giá trị từ ~1~ đến ~f(S)~.

Ràng buộc:

• Có ~40\%~ số test ứng với ~40\%~ số điểm thoả mãn: ~|S| \le 10^2~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm thoả mãn: ~|S| \le 2 \times 10^3~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm thoả mãn: ~|S| \le 10^5~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc gì thêm.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input

abba

Sample Output

5
5

Giải thích:

Các xâu con có 1 kí tự phân biệt là (xâu in đậm): abba, abba, abba, abba, abba

Các xâu con có 2 kí tự phân biệt là (xâu in đậm): abba, abba, abba, abba, abba

Độ khó: Khó (4/4 điểm)

Cho dãy số gồm ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~. Thao tác gộp dãy số lại như sau: chọn hai phần tử liên tiếp ~a_i~ và ~a_{i+1}~ có cùng giá trị là ~x~, rồi xóa ~a_{i+1}~ khỏi dãy và tăng ~a_i~ lên ~1~ thành ~x + 1~, sau đó các phần tử còn lại của dãy được dồn lại.

Hãy tìm cách thực hiện liên tục các thao tác như trên để được dãy có ít phần tử nhất.

Dữ liệu vào từ tệp văn bản GDS.INP:

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 10^6)~;
• Dòng thứ hai chứa ~N~ số nguyên ~a_i~ ~(1 \le a_i \le 10^9;\ 1 \le i \le N)~.

Kết quả ghi ra tệp văn bản GDS.OUT:

Ghi ra số lượng phần tử ít nhất có thể của dãy sau khi thực hiện các thao tác gộp dãy số.

Ràng buộc:

• Có ~20\%~ số test ứng với ~20\%~ số điểm thoả mãn: ~N \le 10;\ a_i \le 30~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm thoả mãn: ~N \le 200;\ a_i \le 30~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm thoả mãn: ~N \le 2000;\ a_i \le 30~;
• ~10\%~ số test khác ứng với ~10\%~ số điểm thoả mãn: ~N \le 2000~;
• ~10\%~ số test khác ứng với ~10\%~ số điểm thoả mãn: ~a_i \le 30~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc gì thêm.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input

4
3 2 2 2

Sample Output

2

Giải thích: Các bước gộp dãy số như sau:

• Dãy ban đầu: ~3\ 2\ 2\ 2~
• Gộp hai số ở vị trí ~2~ và ~3~ thì dãy số là: ~3\ 3\ 2~
• Gộp hai số ở vị trí ~1~ và ~2~ thì dãy số là: ~4\ 2~

Độ khó: Khó (4/4 điểm)

Cho một cây gồm ~N~ đỉnh được đánh số từ ~1~ đến ~N~, trong đó đỉnh ~1~ là gốc của cây. Tất cả đỉnh trên đường đi từ đỉnh ~1~ đến đỉnh ~u~ được gọi là tổ tiên của đỉnh ~u~. Mỗi đỉnh đều có hai loại trọng số, đỉnh thứ ~i~ có trọng số đỉnh là ~a_i~ và trọng số tổ tiên là ~b_i~.

Tổ tiên chung gần nhất của một tập đỉnh là đỉnh chung đầu tiên của các đỉnh khi đi về đỉnh gốc ~1~ (nếu tập hợp gồm ~1~ đỉnh thì tổ tiên chung gần nhất là chính đỉnh đó). Ví dụ, như hình bên, tổ tiên chung gần nhất của tập hợp đỉnh ~\{3, 7\}~ là đỉnh ~2~; tổ tiên chung gần nhất của tập hợp đỉnh ~\{4, 7, 1\}~ là đỉnh ~1~.

Xét một tập hợp gồm ~k~ ~(0 < k \le N)~ đỉnh phân biệt bất kì ~\{u_1, u_2, \ldots, u_k\}~. Gọi ~p~ là tổ tiên chung gần nhất của ~k~ đỉnh. Khi đó giá trị của tập đỉnh này được tính bằng công thức: ~a_{u_1} \times a_{u_2} \times \ldots \times a_{u_k} \times b_p~. Vậy một cây ~N~ đỉnh sẽ có ~2^N - 1~ tập đỉnh phân biệt.

Hãy tính tổng giá trị của tất cả các tập đỉnh có thể tạo ra.

Dữ liệu vào từ tệp văn bản TSTD.INP:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(N \le 10^6)~ là số đỉnh của cây;
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~ ~(a_i \le 10^9;\ 1 \le i \le N)~ mô tả trọng số đỉnh của các đỉnh tương ứng từ đỉnh ~1~ đến đỉnh ~N~;
• Dòng thứ ba chứa ~N~ số nguyên dương ~b_1, b_2, \ldots, b_N~ ~(b_i \le 10^9;\ 1 \le i \le N)~ mô tả trọng số khi nó là tổ tiên của các đỉnh tương ứng từ đỉnh ~1~ đến đỉnh ~N~;
• ~N - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u, v~ ~(u, v \le N)~ mô tả cạnh của cây.

Kết quả ghi ra tệp văn bản TSTD.OUT:

Gồm một số nguyên duy nhất là kết quả của bài toán, vì kết quả có thể rất lớn nên in ra phần dư của kết quả khi chia cho ~10^9 + 7~.

Ràng buộc:

• Có ~20\%~ số test ứng với ~20\%~ số điểm có ~N \le 15~ và cây có dạng đường thẳng: đỉnh ~1~ nối với đỉnh ~2~, đỉnh ~2~ nối với đỉnh ~3~, …, đỉnh ~N - 1~ nối với đỉnh ~N~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N \le 15~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có cây dạng đường thẳng: đỉnh ~1~ nối với đỉnh ~2~, đỉnh ~2~ nối với đỉnh ~3~, …, đỉnh ~N - 1~ nối với đỉnh ~N~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có mọi trọng số đỉnh của các đỉnh đều là ~1~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc gì thêm.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input

3
1 1 2
2 1 2
1 2
1 3

Sample Output

21

Giải thích:

• Tập đỉnh ~\{1\}~ có giá trị: ~2~
• Tập đỉnh ~\{2\}~ có giá trị: ~1~
• Tập đỉnh ~\{3\}~ có giá trị: ~4~
• Tập đỉnh ~\{1, 2\}~ có giá trị: ~2~
• Tập đỉnh ~\{1, 3\}~ có giá trị: ~4~
• Tập đỉnh ~\{2, 3\}~ có giá trị: ~4~
• Tập đỉnh ~\{1, 2, 3\}~ có giá trị: ~4~

~\Rightarrow~ Tổng là: ~21~