LQDOJ CUP 2023 - Round 2

Vào thời trung cổ, vùng đất LQDOJ đã bị một đợt sóng thần quét qua làm hư hại rất nhiều nhà cửa, ruộng vườn. Trong đó có tòa lâu đài của lãnh chúa vùng đất. Do đó lãnh chúa đã ra lệnh khẩn cấp chọn vị trí để xây lâu đài mới của mình.

Vùng đất giờ đây có dạng một bảng hình chữ nhật kích thước \(r \times c\) gồm các ô đất hình vuông. Ô đất ở hàng \(i\) \((1 \leq i \leq r)\), cột \(j\) \((1 \leq j \leq c)\) được gọi là ô \((i, j)\) và đất nơi đây có độ cao \(h_{i,j}\) so với mực nước biển. Tòa lâu đài sẽ được xây trên một khu đất hình chữ nhật \((x, y, u, v)\) (với \((x , y)\) là tọa độ góc trái trên và \((u, v)\) là tọa độ góc phải dưới trong đó \(1 \leq x \leq u \leq r\) và \(1 \leq y \leq v \leq c\)) sao cho các ô đất thuộc khu đất này có cùng độ cao.

Lãnh chúa muốn biết có bao nhiêu cách chọn khu đất thỏa mãn yêu trên cầu để xây lâu đài. Hai cách chọn được xem là khác nhau khi và chỉ khi tồn tại một ô đất thuộc khu đất trong cách chọn này nhưng không thuộc khu đất trong cách chọn kia.

Yêu cầu: Bạn hãy giúp lãnh chúa đếm xem ngài có bao nhiêu cách chọn khu đất thỏa mãn yêu cầu nêu trên.

Input

• Dòng đầu tiên chứa hai số nguyên \(r\) và \(c\) \((1 \leq r, c \leq 2000)\) lần lượt số hàng và số cột của bảng hình chữ nhật mô tả vùng đất.
• Trong \(r\) dòng tiếp theo, dòng thứ \(i\) chứa \(c\) số nguyên \(h_{i, 1}, h_{i, 2}, \ldots, h_{i, c}\) \((1 \leq h_{i,j} \leq 10^{9})\) mô tả độ cao các ô vuông đất tại hàng thứ \(i\).

Output

• In ra số cách chọn khu đất để xây lâu đài cho lãnh chúa.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(r, c \leq 50\).
• Subtask \(2\) (\(40\%\) số điểm): \(r, c \leq 500\).
• Subtask \(3\) (\(20\%\) số điểm): \(h_{i, j} \leq 10\).
• Subtask \(4\) (\(10\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 3
1 1 1
2 2 2
3 3 3

18

5 6
1 1 1 1 5 5
1 1 1 5 5 4
3 2 2 2 2 4
3 3 2 2 2 4
3 3 2 2 2 4

91

Minh đang chơi Roller - một trò chơi nhỏ bên trong trò Fancade. Trò chơi như sau: Cho một nhân vật có dạng một khối hình 3D kích thước \(1 \times 2 \times 1\) nằm trong một bảng hình chữ nhật. Cần phải tìm cách di chuyển nhân vật này bằng cách lật, hoặc lăn nó, sao cho mọi ô trong hình chữ nhật đều được "tô điểm với nhiều sắc màu rực rỡ" bằng cách được đi qua ít nhất một lần.

Là một người yêu thích Tin học, Minh đã nhận ra đây là một bài toán có thể lập trình được. Cậu phát biểu lại nó như sau:
Có một bảng hình chữ nhật kích thước \(n\times m\), tức gồm \(n\) dòng và \(m\) cột. Các hàng của bảng được đánh số từ \(1\) tới \(n\) theo thứ tự từ trên xuống. Các cột được đánh số từ \(1\) tới \(m\) theo thứ tự từ trái sang. Cho khối 3D kích thước \(1 \times 2 \times 1\) ban đầu nằm trên ô \((x, y)\) của bảng này (ô ở dòng \(x\), cột \(y\)). Bảng này có \(k\) ô cấm, không đi vào được. Có thể di chuyển khối này theo phép lật/lăn trong không gian \(3\) chiều, theo \(4\) hướng: trên (U), dưới (D), trái (L), phải (R) (lưu ý các hướng này mang tính tương đối, khi ta giả sử đang nhìn từ trên xuống và đối diện với bảng hình chữ nhật hai chiều). Xem minh họa qua hình sau:

Trong mọi thời điểm, khối hình này không được nằm lên các ô cấm. Ngoài ra, toàn bộ khối hình phải nằm trọn vẹn trong bảng hình chữ nhật. Các ô được nằm lên sẽ được đánh dấu. Hỏi có thể đánh dấu được tất cả mọi ô (trừ ô cấm) hay không với giới hạn số nước đi là \(L\)?

Minh chỉ muốn tận hưởng thành quả - chương trình giải trò chơi tự động chứ không muốn trải qua công đoạn lập trình vất vả. Bạn ấy nhờ các thí sinh của LQDOJ CUP 2023 trợ giúp. Các bạn hãy giải quyết bài toán trên nhé.

Yêu cầu: Cho biết kích thước bảng, vị trí các ô cấm, vị trí ban đầu của khối hình. Hãy in ra một chuỗi các nước đi tương ứng. Nếu không tồn tại cách để đánh dấu toàn bộ ô (trừ ô cấm), hoặc không tồn tại chuỗi các bước đi dài không quá \(L\) bước thỏa mãn, in ra -1.

Input

• Dòng đầu tiên chứa bốn số nguyên \(n,m,k, L\) \((1 \leq n, m \leq 500, 0 \leq k \leq n \times m, 1 \leq L \leq 15 \times 10^{5})\) lần lượt là kích thước của bảng hình chữ nhật, số ô cấm và giới hạn số nước đi.
• Dòng tiếp theo chứa ba số nguyên \(x_{0}, y_{0}, d\) \((1 \leq x_{0} \leq n, 1 \leq y_{0} \leq m)\) với ý nghĩa: tọa độ ban đầu của ô nằm ở phía trên cùng bên trái tiếp xúc với bảng hình chữ nhật của khối hình là \((x_{0},y_{0})\), còn \(d \in \{0, 1, 2\}\) tương ứng với hướng của khối hình: \(0\): hướng lên \((1\times 1)\), \(1\): nằm sang phải \((1\times 2)\), \(2\): nằm xuống dưới \((2 \times 1)\).
• Trong \(k\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_{i}\) và \(y_{i}\) \((1 \leq x_{i} \leq n, 1 \leq y_{i} \leq m)\) thể hiện tọa độ của một ô bị cấm.

Output

• Một dòng duy nhất chứa kết quả. In ra -1 hoặc một xâu chỉ gồm 4 kí tự UDLR tương ứng với các nước đi - lật theo hướng trên/dưới/trái/phải nếu nhìn từ trên xuống (theo bảng hình chữ nhật) (xem hình số 2 để hiểu rõ hơn).
• Có thể có nhiều cách đi hợp lệ khác nhau. Bạn chỉ cần đưa ra một phương án thỏa mãn các ràng buộc của đề bài thì sẽ được tính là đúng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \times m \leq 20, k = 0, L = 400\) và dữ liệu đảm bảo luôn tồn tại chuỗi nước đi thỏa mãn không quá \(13\) bước.
• Subtask \(2\) (\(30\%\) số điểm): \(n\) chia \(3\) dư \(1\), \((m + 1)\) không chia hết cho \(3\), \(k = 0, L = \left\lfloor \frac{2 \times n \times m}{3} \right \rfloor, x_{0} = y_{0} = 1, d = 0\).
• Subtask \(3\) (\(20\%\) số điểm): \(n, m \leq 50, L = 15 \times 10^{5}\).
• Subtask \(4\) (\(30\%\) số điểm): \(L \geq 6 \times n \times m\).

Example

Test 1

Input

3 3 1 54
3 3 0
1 3

Output

LUUDR

Note

Sau đây là ví dụ một chuỗi các nước đi thỏa mãn (tương ứng với xâu LUUDR):

Sau đây là góc nhìn từ trên xuống:

Ô màu đỏ là ô cấm. Ô màu vàng là ô mà khối hình đang nằm đè lên tại thời điểm đang xét (sau một nước đi). Ô màu xanh là những ô đã được đánh dấu trước đó.

Mùa sầu riêng đã đến, những con sóc rất thích hái những quả sầu riêng mang về để giữ trữ vào mùa đông.

Cho một cây cầu riêng gồm \(n\) quả và \(n - 1\) cành, hai đầu của mỗi cành được nối với những quả sầu riêng. Từ một quả bất kỳ, sóc có thể di chuyển qua tất cả những quả khác bằng cách dùng các cành cây đó. Khoảng cách giữa hai quả sầu riêng được cho là số cành ít nhất được dùng để sóc có thể di chuyển từ quả này sang quả kia.

Mẹ sóc giao nhiệm vụ cho sóc là chọn nhiều quả sầu riêng nhất sao cho khoảng cách giữa hai quả bất kỳ được chọn luôn lớn hơn hoặc bằng \(d\). Vì số quả quá lớn nên sóc không thể tính được, các bạn hãy tính hộ sóc nhé!

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(d\) \((1 \leq n, d \leq 2 \times 10^5)\) là số quả của cây sầu riêng.
• Trong \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \leq u, v \leq n)\) thể hiện một cành của cây.

Output

• In ra một số nguyên duy nhất là số quả sầu riêng lớn nhất được chọn sao cho khoảng cách giữa hai quả bất kỳ được chọn luôn lớn hơn hoặc bằng \(d\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 5000\).
• Subtask \(3\) (\(20\%\) số điểm): \(d \leq 20\).
• Subtask \(4\) (\(20\%\) số điểm): Cây là cây nhị phân cân bằng, gốc tại đỉnh \(1\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

5 100
1 3
2 1
4 2
5 4

Output

1

Note

Do \(d\) rất lớn nên ta không thể nào chọn được nhiều hơn \(1\) quả. Lúc này, ta có thể chọn bất kỳ quả nào.

Test 2

Input

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

Output

5

Note

Ta có thể chọn được nhiều nhất \(5\) quả và hình trên là một trong những cách chọn.