LQDOJ CUP 2022 - Round 7

Dũng luôn có một phong cách rất đặc biệt trong cách lập trình cũng như cách anh ấy mã hóa dữ liệu. Đây là một cách mã hóa dữ liệu rất dị mà Dũng đã thiết kế:

• Đầu tiên, chương trình sẽ xây dựng một dãy \(a\) gồm \(n\) số nguyên;
• Tiếp theo, chương trình sẽ xây dựng một tập hợp gồm tất cả các dãy con phân biệt khác rỗng của \(a\) và được sắp xếp tăng dần theo thứ tự từ điển;
• Sau đó, chương trình sẽ chọn một số nguyên \(k\) bất kỳ rồi bắt đầu thực hiện mã hóa theo số nguyên này;
• Cuối cùng, chương trình sẽ đưa ra dãy \(a\) và dãy thứ \(k\) trong tập hợp.

Nhắc lại, dãy con của một dãy được tạo thành bằng cách xóa đi một số phần tử và giữ nguyên thứ tự của các phần tử còn lại. Và dãy \(x\) có thứ tự từ điển nhỏ hơn dãy \(y\) nếu \(x\) là một tiền tố của \(y\) (và \(x \neq y\)) hoặc tồn tại một vị trí \(i\) (\(1 \leq i \leq \min(|x|, |y|)\)) mà với mọi \(j\) (\(1 \leq j < i\)) \(x_j = y_j\) và \(x_i < y_i\).

Để giải mã, người dùng cần nhập vào số nguyên \(k\) mà chương trình đã chọn để mã hóa.

Sau khi thử nghiệm, Dũng nhận được hai dãy nhưng lại không biết cách nào để tìm lại số nguyên \(k\) nên đã đã nhờ đến bạn. Với kinh nghiệm của bản thân, hãy giúp Dũng tìm lại nhé.

Ngoài ra, dãy thứ \(k\) mà chương trình đưa ra có thể là không phải là dãy con của \(a\) do chương trình bị lỗi (Có thể do \(k\) âm chăng?).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1 \leq m \leq n \leq 5 \times 10^5\)) lần lượt là độ dài của dãy \(a\) và dãy thứ \(k\) trong tập hợp.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq n\)) mô tả dãy \(a\).
• Dòng tiếp theo chứa \(m\) số nguyên \(b_1, b_2, \ldots, b_m\) (\(1 \leq b_i \leq n\)) mô tả dãy thứ \(k\) trong tập hợp.

Output

• Trong trường hợp chương trình bị lỗi, hãy in \(-1\). Ngược lại, in ra \(k\) là số nguyên mà chương trinh đã chọn. Vì \(k\) có thể rất lớn nên bạn chỉ cần in phần dư của \(k\) khi chia cho \(10^9 + 7\), còn lại để Dũng tự lo.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 15\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 5 \times 10^3\) và tất cả số nguyên trong dãy \(a\) đôi một phân biệt.
• Subtask \(3\) (\(15\%\) số điểm): Tất cả số nguyên trong dãy \(a\) đôi một phân biệt.
• Subtask \(4\) (\(25\%\) số điểm): \(n \leq 5 \times 10^3\).
• Subtask \(5\) (\(15\%\) số điểm): không có ràng buộc gì thêm.

Example

4 2
3 1 3 1
3 1

6

4 2
3 1 3 1
3 2

-1

Nhân dịp sang năm mới, một chương trình xổ số được tổ chức với quy mô giải thưởng lên tới hàng tỷ đồng. Đây là cơ hội đổi đời của mỗi người và cũng chính là một cơ hội to lớn của bạn. Cách thức tham gia rất đơn giản, bạn chỉ mua các tờ vé số và nhận phần thưởng với những tấm vé số trúng giải. Đơn vị tổ chức đã bắt đầu mở bán vé số ở các đại lý trên toàn quốc. Mỗi tờ vé số sẽ có một dãy số gồm \(n\) số nguyên dương \(a_1, a_2,\ldots, a_n\) là một dãy hoán vị từ \(1\) đến \(n\). Một điều chưa từng có trong tiền lệ đó là: Đơn vị tổ chức sẽ cung cấp gợi ý về những tấm vé số đạt giải. Gợi ý là một mã QR có dạng một ma trận nhị phân kích thước \(n \times n\), ô ở hàng thứ \(i\) và cột thứ \(j\) có số \(b_{i,j}\).

Thông tin được cung cấp thêm như sau: Trên mỗi dãy hoán vị, một thao tác thay đổi được thực hiện bằng cách chọn một chỉ số \(i\) (\(1<i<n\)) và gán \(a_i\) bằng trung vị của dãy \(\{a_{i-1}, a_i, a_{i+1}\}\). Trên ma trận gợi ý, giá trị \(b_{i,j} = 1\) nếu có thể tạo ra \(a_i = j\) sau một số thao tác thay đổi, ngược lại giá trị \(b_{i,j} = 0\). Những tấm vé số đạt giải nếu có dãy hoán vị thỏa mãn ma trận gợi ý mà đơn vị tổ chức cung cấp.

Nhắc lại, trung vị của một dãy là phần tử ở giữa sau khi dãy đã được sắp xếp theo thứ tự tăng dần. Ví dụ, trung vị của dãy \(\{5, 2, 3\}\) là \(3\).

Từ những thông tin gợi ý cung cấp, hãy tìm ra một tấm vé số đạt giải và đi lĩnh thưởng.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq n \leq 5000\)).
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa chứa \(n\) số nguyên \(b_{i,1}, b_{i,2},\ldots, b_{i,n}\) (\(0 \leq b_{i,j} \leq 1\)) mô tả hàng thứ \(i\) của ma trận gợi ý.

Output

• In ra một dãy hoán vị từ \(1\) đến \(n\) thỏa mãn ma trận gợi ý. Nếu có nhiều đáp án thỏa mãn, chỉ cần in ra một đáp án bất kỳ.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \leq 10\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 50\).
• Subtask \(3\) (\(25\%\) số điểm): \(n \leq 400\).
• Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
10000
00111
00110
00110
01000

1 5 3 4 2

Quis vừa phát minh ra một robot cắt cỏ mới. Nó sử dụng trí tuệ nhân tạo để đưa ra quyết định là nên cắt ở đâu, diện tích bao nhiêu. Tuy nhiên, đáng buồn là do chưa đủ dữ liệu nên hiện tại robot chỉ có thể cắt một cách vô cùng ngẫu nhiên, hiệu suất không cao.

Trong hôm nay, robot đã cắt được \(n\) vùng trên bãi cỏ. Ta có thể coi bãi cỏ là một hình chữ nhật trên mặt phẳng, có độ dài bề ngang và bề dọc lần lượt là \(W\) và \(H\) đơn vị. Để dễ xác định vị trí mà robot đã cắt, ta đặt gốc tọa độ \(Oxy\) ở góc trái dưới của hình chữ nhật sao cho hai trục \(Ox\), \(Oy\) trùng với cạnh của hình chữ nhật.

Do cấu tạo đặc biệt, mỗi lần cắt cỏ, robot sẽ cắt toàn bộ cỏ trong một hình tam giác có tọa độ các đỉnh nguyên và nằm gọn trong bãi cỏ.

Nhằm đánh giá hiệu suất của buổi cắt cỏ ngày hôm nay (với \(n\) vùng đã được cắt), làm cơ sở để robot điều chỉnh và học tập, hãy tính diện tích trung bình mỗi lần cắt, được tính bằng cách lấy tổng diện tích cỏ đã được cắt, chia cho \(n\).

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(W\) và \(H\) (\(1 \le n \le 300\), \(1\le W, H \le 10^4\)) lần lượt là là số vùng cắt và kích thước bãi cỏ.
• Trong \(n\) dòng tiếp theo, mỗi dòng chứa sáu số nguyên \(x_1\), \(y_1\), \(x_2\), \(y_2\), \(x_3\) và \(y_3\) (\(0 \leq x_1, x_2, x_3 \leq W\), \(0 \leq y_1, y_2, y_3 \leq H\)), trong đó \((x_1, y_1)\), \((x_2, y_2)\), \((x_3, y_3)\) là tọa độ các đỉnh của vùng được cắt.
• Dữ liệu đảm bảo không có ba điểm nào thẳng hàng và các đỉnh có tọa độ phân biệt.

Output

• Một dòng duy nhất chứa một số thực là hiệu suất tính được.

Note

• Đáp án của bạn được coi là đúng nếu như chênh lệch giữa nó với đáp án của giám khảo không vượt quá \(10^{-6}\).
• Cụ thể, giả sử bạn đưa ra số \(a\), đáp án của test đó là \(b\) thì bạn đúng được test này khi và chỉ khi \(\frac{|a-b|}{\max(a,b)} \leq 10^{-6}\).

Scoring

• Subtask \(1\) (\(5\%\) số điểm): \(n = 1\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 14\).

• Subtask \(3\) (\(25\%\) số điểm): Các tam giác là tam giác vuông cân có hai cạnh song song với trục tọa độ, và chỉ thuộc vào một trong hai dạng sau:
  

• Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

1 5 5
0 0 3 0 0 4

6.000000152004

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

13.9219260464