Trại Hè Miền Bắc 2022 TT

Cho một bảng kí tự kích thước \(M * N\), chỉ gồm hai kí tự `\(X\)` và `\(.\)`.

Yêu cầu: Tìm hình chữ nhật có chu vi lớn nhất thỏa mãn:

• Các cạnh của hình chữ nhật song song với các cạnh của bảng kí tự.
• Chỉ chứa kí tự `\(.\)`.
• Hình chữ nhật có chu vi lớn nhất.

Input

• Dòng đầu chứa hai số nguyên dương \(M,N (M,N \leq 400)\);
• Dòng thứ \(i\) trong số \(M\) dòng tiếp theo chứa \(N\) kí tự \(A_{i,1},A_{i,2},\ldots,A_{i,N} (A_{i,j}=\)`\(X\)` hoặc `\(.\)`\()\)

Output

• In ra duy nhất một số là chu vi hình chữ nhật lớn nhất tìm được.

Example

2 2
..
.. 

8

4 4
X.XX
X..X
..X.
..XX 

10

3 3
X.X
.X.
X.X 

4

Crab vừa rộng mô hình dịch vụ sang chuyển phát hàng hóa khi xe đang rảnh. Có \(n\) gói hàng, gói thứ \(i\) muốn chuyển từ vị trí \(i\) đến vị trí \(i + n\). Cần lập lịch cho xe xuất phát từ vị trí \(0\), chuyển hết các gói hàng và quay lại vị trí xuất phát. Sức chứa của xe là đủ lớn, do đó gói hàng thứ \(i\) sẽ được chuyển nếu ít nhất một lần, lộ trình của xe có đi qua \(i\) trước khi đi qua \(i+n\). Ví dụ với \(n = 3\), lộ trình sau là thỏa mãn: \(0-1-2-1-5-3-6-4-0\)

Cho biết độ dài tuyến đường đi lại giữa mọi cặp vị trí, hãy tìm lộ trình của taxi có tổng độ dài các tuyến đường đi qua là nhỏ nhất. Lưu ý, các tuyến đường trong thành phố là đường một chiều nên khoảng cách từ \(x\) đến \(y\) có thể khác với khoảng cách từ \(y\) đến \(x\), và có thể đường đi ngắn nhất \(x\) và \(y\) không phải là đường đi trực tiếp giữa chúng. Nếu có nhiều lộ trình thỏa mãn có cùng độ dài nhỏ nhất, in ra một lộ trình bất kỳ

Input

• Dòng 1: \(n\)
• Tiếp theo là \(2n+1\) dòng, số thứ \(j\) trên dòng \(i\) là \(c_{i,j}\): độ dài tuyến đường nối \(i\) với \(j\)

Output

• Dòng đầu tiên chứa tổng độ dài của lộ trình tìm được
• Dòng tiếp theo chứa số vị trí sẽ đi qua
• Dòng tiếp theo ghi danh sách các vị trí sẽ đi qua theo thứ tự trong lộ trình

Scoring

• \(1 \leq n \leq 10\). \(1 \leq c_{i,j} \leq 1000\)
• Subtask 1: \(n \leq 5\)
• Subtask 2: \(c_{i,j} + c_{j,k} \geq c_{i,k}\), \(\forall\) \(0 \leq i, j, k \leq 2n\)
• Subtask 3: Ràng buộc gốc

Example

3
0 4 2 3 5 4 4
4 0 7 5 2 3 1
3 2 0 1 2 1 9
2 3 5 0 9 8 3
2 1 4 6 0 9 1
9 8 1 4 2 0 8
1 2 3 2 5 4 0

12
9
0 2 5 2 3 1 4 6 0

Một chuỗi số là một chuỗi kí tự chỉ gồm các chữ số \(1,2,\ldots,9\).

Có \(N\) chuỗi số, chuỗi số thứ \(i\) kí hiệu là \(A_i\) và có chi phí khi dùng một lần là \(W_i\). Hay nói cách khác, bài toán này cho phép bạn sử dụng vô số lần, nếu dùng đúng \(T\) lần thì chi phí bạn phải bỏ ra là \(T \times W_i\).

Yêu cầu: Cho một số nguyên dương \(M\). Bạn hãy tìm cách sử dụng \(N\) chuỗi số này và ghép lại theo một thứ tự bất kì và bao nhiêu lần tùy thích để có được một số nguyên dương chia hết cho \(M\) và mất chi phí ít nhất.

Input

• Dòng đầu chứa hai số nguyên dương \(N,M (N \leq 50, M \leq 1000)\);
• Dòng thứ \(i\) trong số \(N\) dòng tiếp theo chứa một xâu gồm các kí tự số \(A_i\) và chi phí \(W_i\) (\(|A_i |\leq 1000, 1\leq W_i \leq 1000\)).

Output

• In ra duy nhất một số nguyên là kết quả tìm được hoặc in ra \(-1\) nếu không có phương án.

Example

2 2
123 2
13 10

-1

2 6
2 20
77 6

32

Cho một dãy \(N\) số nguyên dương \(A_1,A_2,…,A_N\). Một thao tác thay đổi là việc chọn một phần tử \(a_i (1\leq i \leq N)\) và thay thế \(A_i=A_i+1\).

Yêu cầu: Bạn cần trả lời \(q\) truy vấn. Mỗi truy vấn cho bạn một dãy con liên tiếp trong đoạn từ \(l\rightarrow r\) và yêu cầu tính xem số lượng thao tác thay đổi tối thiểu để cho dãy con đã cho thành dãy không giảm.

Input

• Dòng đầu chứa hai số nguyên dương \(N,q\) \((1\leq N,q \leq 2 \times 10^5)\);
• Dòng tiếp theo gồm \(N\) số nguyên dương \(A_1,A_2,…,A_n\) \((A_i\leq 10^9)\).
• \(q\) dòng cuối cùng, mỗi dòng gồm 2 số nguyên dương \(l, r\) \((1\leq l \leq r \leq n)\) biểu thị cho dãy con từ \(l\) đến \(r\).

Output

• In ra \(q\) dòng, mỗi dòng chứa một số nguyên không âm là kết quả bài toán của truy vấn tương ứng.

Example

5 3
2 10 4 2 5
3 5
2 2
1 4

2
0
14

Cho \(n\) xâu \(s_1,s_2,\ldots,s_n\). Chi phí để sử dụng xâu \(s_i\) là \(c_i\).
Lưu ý: Có thể sử dụng xâu \(s_i\) nhiều lần và chi phí là \(c_i\) nhân với số lần dùng.

Yêu cầu: Tìm chi phí tối thiểu để sử dụng các xâu \(s_i\) ghép lại với nhau thành xâu đối xứng.

Input

• Dòng đầu chứa duy nhất một số nguyên dương \(n\) (\(1\leq n \leq 50\)) là số lượng xâu.
• Dòng thứ \(i\) trong số \(n\) dòng tiếp theo chứa xâu \(s_i\) và số nguyên \(c_i\) là xâu thứ i và chi phí để sử dụng (1 \(\leq |s_i| \leq 20; 1\leq c_i \leq 10^9\)).

Output

• In ra chi phí tối thiểu, in \(-1\) nếu không tạo được xâu đối xứng.

Example

3
ba 3
abc 4
cbaa 5

7

2
abcab 5
cba 3

11

2
abc 1
ab 2

-1

Thành vẽ một cây (đồ thị vô hướng liên thông không có chu trình) với \(N\) nút được đánh số từ 1 đến \(N\) và muốn tô màu các nút của cây bằng màu đen hoặc trắng. Trên cây, hai nút có thể ghép đôi với nhau khi và chỉ khi chúng thỏa mãn các điều kiện sau:

• cả hai cùng được tô bởi màu trắng, và
• hoặc là có cạnh nối trực tiếp giữa chúng hoặc là có thể nối chúng bởi một đường đi đơn chỉ gồm toàn nút màu đen ngoại trừ hai nút đầu mút là màu trắng.

Yêu cầu: hãy giúp Thành tô màu các nút của cây bằng màu đen hoặc trắng sao cho số lượng cặp nút có thể ghép đôi với nhau là lớn nhất.

Input

Dòng đầu tiên chứa một số nguyên dương \(T\) (\(T\leq 10\)) là số lượng bộ test, mỗi bộ test chứa thông tin về một cây cần tô màu có cấu trúc như sau:

• Dòng thứ nhất chứa một số nguyên dương \(N\) (\(N \leq 5000\)) là số lượng nút của cây;
• Mỗi dòng trong số \(N-1\) dòng tiếp theo chứa hai số nguyên \(x\) \(y\) cách nhau bởi dấu cách cho biết có cạnh nối trực tiếp giữa hai nút \(x\) và \(y\).

Output

• Ghi ra \(T\) dòng, mỗi dòng một số nguyên là kết quả tìm được tương ứng với các bộ test trong dữ liệu vào.

Scoring

• Subtask \(1\): \(T=1\) và \(N\leq 15\)
• Subtask \(2\): \(T=1\) và \(N\leq 20\)
• Subtask \(3\): \(N\leq 500\) và mỗi cây trong dữ liệu vào có đúng 2 lá
• Subtask \(4\): \(N\leq 500\)
• Subtask \(5\): Không có ràng buộc gì thêm

Example

2
8
1 2
2 3
2 4
4 5
5 6
6 7
6 8
2
1 2

7
1