Tin học trẻ C1 - Vòng Khu vực miền Trung 2023

Cho dãy số nguyên dương \(A_1,A_2,...,A_N\). Một bộ ba (\(i,j,k\)) được gọi là đẹp của dãy \(A\) đã cho nếu thỏa mãn:

• \(1 \le i \le j < k \le N\).
• Gọi dãy con liên tiếp \(A_i,A_{i+1},...,A_j\) là \(X\) và dãy con liên tiếp \(A_{j+1},A_{j+2},...,A_k\) là \(Y\) thì hai dãy này thỏa mãn:
  • Với mỗi giá trị xuất hiện trong dãy \(X\) thì cũng xuất hiện trong dãy \(Y\).
  • Với mỗi giá trị xuất hiện trong dãy \(Y\) thì cũng xuất hiện trong dãy \(X\).

Yêu cầu: Cho dãy số \(A\), hãy đếm số bộ ba đẹp (\(i,j,k\)) của dãy số này.

Input

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 2 \times 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(A_i\) (\(1 \le A_i \le N\)).

Output

• Ghi ra một số nguyên là số lượng bộ ba đẹp của dãy đã cho.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 500\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 5000\).
• Subtask \(3\) (\(20\%\) số điểm): \(A_i \le 50\).
• Subtask \(4\) (\(20\%\) số điểm): mỗi giá trị xuất hiện đúng hai lần.
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

7
3 1 2 1 2 3 1

4

Có \(2^n\) gia đình cùng sống trong một khu phố, các gia đình được đánh số từ \(1\) đến \(2^n-1\). Sau mỗi ngày, mỗi gai đình đều gửi tặng cho tất cả các gia đình khác một số quả, số quả này tính dựa trên số quả gia đình đó nhận được ngày trước đó. Cụ thể, gọi \(f_i\) là tổng số quả gia đình \(i\) nhận được ngày \(d\) thì sang ngày tiếp theo \(d+1\), gia đình \(i\) sẽ gửi cho gia đình \(j\) (\(j \neq i\)) số quà là \(f_i \times (2 \times (i | j) - i - j)\), trong đó \(|\) là phép toán \(OR\).

Yêu cầu: Cho biết số gia đình trong khu phố và số quả mỗi gia đình được nhận ở ngày \(0\), tính số quả mỗi gia đình nhận được ở ngày \(k\).

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n,k\) (\(n \le 20, k \le 10^9\)).
• Dòng thứ hai chứa \(2^n\) số nguyên không âm, số thứ \(i\) là số quả gia đình \(i\) nhận được ở ngày hiện tại. Các số không vượt quá \(10^9\).

Output

• Ghi ra \(n\) số nguyên trên một dòng, số thứ \(i\) là tổng số quả mà gia đình \(i\) nhận được vào ngày thứ \(k\), lấy phần dư khi chia cho (\(10^9+7\)).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 10, k \le 5\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 10, k \le 1000\).
• Subtask \(3\) (\(30\%\) số điểm): \(k \le 10^5\).
• Subtask \(4\) (\(10\%\) số điểm): không có ràng buộc gì thêm.

Example

2 1
3 4 5 1

17 20 19 22

Xây dựng bản đồ Hapmap của con người có thể giúp việc chẩn đoán bệnh cũng như tìm ra các loại thuốc chữa trị mới. Trong xây dựng bản đồ Hapmap, Haplotype và Genotype là hai khái niệm cơ bản trong sinh học được phát biểu đơn giản như sau:

1. Haplotype \(H = (h_1, \dots, h_n)\) là xâu độ dài \(n\), trong đó \(h_i\) chỉ nhận giá trị \(0\) hoặc \(1\).
2. Genotype \(G = (g_1, \dots, g_n)\) là một xâu độ dài \(N\) được tạo ra từ sự đối sánh hai Haplotype \(H = (h_1, \dots, h_n)\) và \(H' = (h_1', \dots, h_n')\) theo quy tắc sau:
   • \(g_i = 0\) nếu \(h_i = h_i' = 0\).
   • \(g_i = 1\) nếu \(h_i = h_i' = 1\).
   • \(g_i = 2\) nếu \(h_i \neq h_i'\).

Như vậy, mỗi cặp Haplotype \(H\) và \(H'\) chỉ tạo ra một Genotype \(G\) duy nhất, nhưng một Genotype \(G\) lại có thể được tạo ra từ nhiều cặp Haplotype khác nhau. Thông tin về gen của một con người được xác định bởi một cặp Haplotype. Để đáp ứng mục đích nghiên cứu, các nhà khoa học cần giải mã thông tin từ Haplotype và Genotype. Do việc giải mã là không duy nhất, nên với một tập Genotype, các nhà khoa học muốn tìm một tập gồm ít Haplotype nhất mà mỗi Genotype đều được tạo ra từ hai Haplotype trong tập.

Yêu cầu: Cho thông tin Genotype là \(G_1, \dots, G_k\) của \(k\) người, hãy tìm \(k\) cặp \((H_1, H_1'), \dots, (H_k, H_k')\) tương ứng cho \(k\) người sao cho tập \(\{H_1, H_1', \dots, H_k, H_k'\}\) có lực lượng là nhỏ nhất.

Input

• Dòng đầu ghi hai số \(k, n\) (\(k \le 100, n \le 200\)).
• Dòng thứ \(t\) (\(1 \le t \le k\)) trong \(k\) dòng tiếp theo chứa xâu độ dài \(n\) biểu diễn Genotype \(G_t\) của người thứ \(t\).

Output

• Ghi số nguyên dương \(p\) là lực lượng của các Haplotype tìm được.
• \(p\) dòng sau, mỗi dòng một xâu mô tả Haplotype.

Scoring

• Có \(10\) test, mỗi test \(10.0\) điểm. Gọi \(p\) là số Haplotype bạn tìm được, \(r\) là kết quả của Ban giám khảo, nếu \(p > 2k\) bạn sẽ bị \(0\) điểm, ngược lại bạn sẽ đạt được: \(10.0 \times \min\left\{1, \left(\frac{r}{p}\right)^3\right\}\).
• Subtask \(1\) (\(50\%\) số điểm): \(k \le 10\).
• Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

2 4
1212
1110

2
1110
1011