LQDOJ Cup 2025 - Round #1

Bé An rất thích xếp hình. Cậu có một hộp gồm \(n\) khối lập phương đủ màu sắc.
Các khối lập phương được đánh số từ \(1\) đến \(n\), khối thứ \(i\) được mô tả bởi hai thông số: màu \(c_i\) và kích thước \(s_i\).

Một Tháp Sọc được định nghĩa là một tòa tháp gồm các khối lập phương chỉ thuộc chính xác hai màu khác nhau.
Ngoài ra, các khối lập phương trong tháp phải được xếp sao cho màu xen kẽ nhau (tức hai khối kề nhau không được cùng màu).
Tháp phải có ít nhất hai khối lập phương.

Chiều cao của Tháp Sọc chính là tổng kích thước của tất cả khối lập phương trong tháp.
Hãy giúp bé An xây dựng một Tháp Sọc có chiều cao lớn nhất từ những khối lập phương có sẵn.

Input

Dòng đầu tiên chứa một số nguyên \(\theta\) là số lượng bộ dữ liệu. Tiếp theo là các bộ dữ liệu, mỗi bộ được mô tả theo khuôn dạng sau:

• Dòng đầu tiên là một dòng trống.
• Dòng thứ hai chứa một số nguyên \(n\) \((2 \le n \le 10^5)\) - số lượng khối lập phương.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(c_i\) và \(s_i\) \((1 \le c_i, s_i \le 10^9)\) -
  màu sắc và kích thước của khối lập phương thứ \(i\).

Dữ liệu đảm bảo luôn có hai khối lập phương khác màu nhau.

Gọi \(\Sigma_n\) là tổng giá trị của \(n\) trong các bộ dữ liệu của một test. Dữ liệu đảm bảo \(\Sigma_n \leq 5 \cdot 10^5\).

Output

Với mỗi bộ dữ liệu, hãy in ra mô tả của Tháp Sọc có chiều cao lớn nhất theo định dạng sau:

• Dòng đầu tiên chứa chiều cao của tháp.
• Dòng thứ hai chứa số lượng khối lập phương tạo thành tháp.
• Dòng thứ ba chứa các chỉ số của những khối lập phương theo thứ tự từ dưới lên trên.

Nếu tồn tại nhiều Tháp Sọc có chiều cao lớn nhất, bạn có thể in ra bất kỳ tháp nào trong số đó.

Scoring

• Subtask \(1\) (\(20\) điểm): \(n \le 100\) và \(\Sigma_n \leq 500\)
• Subtask \(2\) (\(30\) điểm): \(n \le 1000\) và \(\Sigma_n \leq 5000\)
• Subtask \(3\) (\(50\) điểm): Không có ràng buộc gì thêm.

Example

3

2
1 6
2 7

3
1 10
2 15
2 17

4
1 1
2 2
3 3
4 4

13
2
1 2 
42
3
3 1 2 
7
2
3 4 

Trong một thế giới song song, Thầy Nhỏ đang trên con đường xây dựng Lê-Quý-Đôn Orange-Juice trở thành Nhà máy sản xuất Nước cam lớn nhất Việt Nam. Hùng là một nhà mật mã học tài ba nhưng làm trái ngành, và vô tình nằm trong đội ngũ truyền thông của công ty. Hôm nay, Hùng đề xuất một chiến dịch đố vui có thưởng.

Hùng quyết định lấy công thức món Mocktail yêu thích chưa kịp đặt tên ("chưa" là tên tạm thời) trong quầy bar thử nghiệm của Nhỏ's Coffee (một trong những chuỗi quán đồ uống không chứa caffeine lớn nhất Việt Nam) làm cảm hứng. Được biết, món này cần chuẩn bị \(n\) nguyên liệu có tên được mã hóa là \(P_1, P_2, \dots, P_n\); và để pha được một ly ``chưa'' đúng chuẩn thì phải thực hiện tuần tự \(m\) bước: \(i_1, i_2, \dots, i_m\)~-- chính là thứ tự đưa nguyên liệu vào ly mocktail này.

Trò chơi rất đơn giản: mọi người sẽ cùng nhau đoán mật mã \(T\) được ghép từ các xâu \(P_{i_1}, P_{i_2}, \dots, P_{i_m}\)~-- chính là công thức món mới. Trong quá trình chơi, giả sử người chơi đoán đáp án là \(G\) và đáp án sai, hệ thống sẽ thông báo số ký tự đúng và số ký tự sai; số ký tự đúng được tính bằng độ dài của xâu con chung dài nhất giữa \(G\) và \(T\), số ký tự sai bằng độ dài của \(G\) trừ cho số ký tự đúng.

Công ty chấp thuận ý tưởng này, và đưa kế hoạch xuống các phòng ban liên quan, trong đó có phòng Kỹ thuật. Bạn là lập trình viên tài ba nhất của phòng Kỹ thuật, và được giao nhiệm vụ đếm số ký tự đúng. Đội Kiểm tra chất lượng (Quality Assurance) của phòng đã chuẩn bị sẵn \(q\) trường hợp đầu vào kiểm thử là các xâu kí tự \(S_1, S_2, \ldots, S_q\). Với mỗi xâu \(S_i\), bạn cần tính độ dài của xâu con chung dài nhất giữa \(S_i\) và \(T\).

Nhắc lại, xâu ký tự \(A = \alpha_1 \alpha_2 \ldots \alpha_{\sigma}\) được gọi là xâu con của xâu ký tự \(B = \beta_1 \beta_2 \ldots \beta_{\tau}\) khi và chỉ khi tồn tại dãy chỉ số \(\iota_1, \iota_2, \ldots, \iota_{\sigma}\) thỏa mãn \(1 \leq \iota_1 < \iota_2 < \ldots < \iota_{\sigma} \leq \tau\) và \(\alpha_{\kappa} = \beta_{\iota_{\kappa}}\) với mọi \(1 \leq {\kappa} \leq \sigma\). Xâu rỗng được coi là xâu con của mọi xâu ký tự. Ví dụ: ac, abc, <xâu rỗng> là xâu con của abc; nhưng cb hay ad thì không.

Input

• Dòng đầu tiên chứa ba số \(n\), \(m\) và \(q\) \((1 \leq n \leq 10^5, 1 \leq m \leq 2 \cdot 10^5, 1 \leq q \leq 75000)\).
• Dòng thứ hai chứa \(n\) xâu \(P_1, P_2, \ldots, P_n\); các xâu đều không rỗng, chỉ gồm các ký tự latin thường, và có tổng độ dài không quá \(10^6\).
• Dòng thứ ba chứa \(m\) số nguyên \(i_1, i_2, \ldots, i_m\) \((1 \leq i_j \leq n)\).
• Trong \(q\) dòng cuối cùng, dòng thứ \(i\) chứa một xâu \(S_i\) chỉ gồm các ký tự latin thường có độ dài không quá \(3000\). Tổng độ dài \(q\) xâu này không quá \(75000\).

Output

In ra \(q\) dòng, dòng thứ \(i\) chứa số ký tự đúng giữa xâu \(S_i\) và \(T\).

Scoring

• Subtask \(1\) (\(19\) điểm): Các xâu \(P_1, P_2, \ldots, P_n\) có \(1\) ký tự và \(m \leq 2000\).
• Subtask \(2\) (\(23\) điểm): Các xâu \(P_1, P_2, \ldots, P_n\) có không quá \(10\) ký tự.
• Subtask \(3\) (\(29\) điểm): Các xâu \(S_1, S_2, \ldots, S_q\) có không quá \(300\) ký tự. Tổng độ dài các xâu này không quá \(7500\).
• Subtask \(4\) (\(29\) điểm): Không có ràng buộc gì thêm.

Example

5 2 5
doran oner faker gumayusi keria
5 2
kiin
canyon
chovy
ruler
duro

3
3
1
3
2

Hôm nay Lan tìm hiểu về lý thuyết số học. Bạn ấy cảm thấy vô cùng thích thú khi tìm hiểu về chủ đề phân tích một số ra thừa số nguyên tố. Mỗi số nguyên dương \(x\) bất kỳ đều có thể được biểu diễn dưới dạng tích của các số nguyên tố, và biểu diễn này là duy nhất.

Để khám phá kiến thức mới này, Lan tiến hành vẽ ``cây phân tích thừa số nguyên tố''. Đây là một cây được cố định gốc, và mỗi nút trên cây có chứa một số nguyên dương. Cây cần thỏa mãn các điều kiện sau:

• Giá trị của nút gốc là một số nguyên dương lớn hơn \(1\).
• Nếu một nút là lá, giá trị của nó phải là một số nguyên tố.
• Nếu một nút khác lá, giá trị của nó phải bằng tích giá trị của các con của nó.

Lan có một dãy số yêu thích \(a_1, a_2, \ldots, a_n\). Lan muốn tạo ra một cây phân tích chứa tất cả các giá trị trong dãy số này. Nói cách khác, trên cây cần có \(n\) nút đôi một phân biệt sao cho giá trị của chúng lần lượt là \(a_1, a_2, \ldots, a_n\). Chỉ có điều, cây của Lan thường rất lớn. Bạn hãy giúp Lan xây dựng một cây phân tích hợp lệ có số đỉnh nhỏ nhất nhé.

Input

• Dòng thứ nhất chứa số nguyên \(n\) \((1 \leq n \leq 15)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((2 \le a_i \le 10^{15})\).

Output

Gồm một dòng duy nhất chứa số đỉnh nhỏ nhất của một cây phân tích chứa toàn bộ giá trị trong \(a\).

Scoring

• Subtask \(1\) (\(8\) điểm): \(n = 1\)
• Subtask \(2\) (\(18\) điểm): Tất cả các số \(a_1, a_2, \ldots, a_n\) đều là số nguyên tố.
• Subtask \(3\) (\(14\) điểm): Tồn tại \(n\) số nguyên tố \(p_1, p_2, \ldots, p_n\) và \(n\) số nguyên dương \(e_1, e_2, \ldots, e_n\) sao cho \(a_i = p_i^{e_i}\) với mọi \(i\) từ \(1\) đến \(n\).
• Subtask \(4\) (\(20\) điểm): \(n \leq 5\)
• Subtask \(5\) (\(22\) điểm): \(n \leq 10\)
• Subtask \(6\) (\(18\) điểm): Không có ràng buộc gì thêm.

Example

3
21 6 24

10