2. LQDOJ Cup 2025 - Round #6 - Liên minh tối thượng
Atlantis không chỉ là một thành phố, nó là một nền văn minh vĩ đại. Dù đã bị nhấn chìm dưới đại dương, nó chưa từng bị quên lãng trong ký ức của loài người. Dưới độ sâu hàng ngàn km, hòn đảo này tỏa sáng rực rỡ như một viên ngọc lam khổng lồ được tạc từ pha lê và hợp kim không tên. Atlantis nổi tiếng với những tòa tháp cao đồ sộ được thiết kế theo trăm ngàn hình thù kỳ ảo thách thức mọi giới hạn vật lý. Toàn bộ thành phố được bao bọc trong một mái vòm năng lượng plasma trong suốt, tạo ra một bầu khí quyển nhân tạo hoàn hảo, nơi những sinh vật biển kỳ dị nhất cũng phải nép mình trước sự vĩ đại của con người.
Nhưng nó chẳng là gì so với vương quốc Uchiha -- biểu tượng của một sức mạnh quân sự lỗi lạc (lỗi thời và lạc hậu), một vùng đất mà mọi người chung sống với nhau bằng những cái liếc mắt đầy thân thiện. Người dân trong vương quốc đều mắc một căn bệnh kỳ lạ, mắt của họ đỏ như cà chua mỗi khi tới tuổi dậy thì. Nhưng cũng nhờ những đôi "hắc nhãn" ấy mà mỗi người đều có nhũng năng lực kỳ bí. Để tránh xung đột sức mạnh, quốc vương đã chia đất nước thành các khu vực, mỗi khu vực là một ngôi làng -- nơi chung sống của một nhóm người sở hữu cùng một loại năng lực. Bản đồ vương quốc Uchiha có dạng hình chữ nhật gồm \(m\) hàng và \(n\) cột mà mỗi ô là một ngôi làng. Các hàng được đánh số từ \(1\) đến \(m\) và các cột được đánh số từ \(1\) đến \(n\). Ngôi làng ở hàng \(i\) và cột \(j\) được ký hiệu là \((i, j)\). Người dân của ngôi làng này có chỉ số sức mạnh là \(A_{i, j}\). Để thuận tiện cho việc đi lại, quốc vương đã cho xây dựng một số con đường. Giữa hai ngôi làng \((x, y)\) và \((u, v)\) có một con đường kết nối trực tiếp khi và chỉ khi \(|x - u| + |y - v| = 1\).
Hôm nay là một ngày thiêng liêng của toàn bộ người dân Uchiha, ngày kỷ niệm \(30^{30}\) vương quốc phồn thịnh này ra đời. Để thị uy với các vương quốc khác, quốc vương đã chọn ra một số ngôi làng tham gia đội diễu binh diễu hành trong lễ kỷ niệm. Các ngôi làng được chọn cần thỏa mãn các điều kiện sau:
- Tập hợp các ngôi làng được chọn tạo thành một khu vực liên thông.
- Tồn tại ít nhất hai ngôi làng có chỉ số sức mạnh khác nhau.
- Nếu ta liệt kê các giá trị phân biệt của chỉ số sức mạnh của những ngôi làng được chọn và sắp xếp chúng theo thứ tự tăng dần, ta được một cấp số nhân có công bội là số nguyên dương không quá \(30\).
Một tập hợp \(S\) các ngôi làng được gọi là khu vực liên thông khi và chỉ khi từ mọi cặp ngôi làng \((x_1, y_1)\) và \((x_2, y_2)\) thuộc \(S\), tồn tại cách di chuyển giữa hai ngôi làng này mà chỉ đi qua các ngôi làng thuộc \(S\).
Một dãy số \(a_1, a_2, \ldots, a_k\) được gọi là cấp số nhân khi và chỉ khi tồn tại số \(q\) sao cho \(a_i = q \cdot a_{i - 1}\) với mọi \(1 \leq i < k\).
Để buổi lễ diễu binh được thật sự hoành tráng, quốc vương muốn số ngôi làng được lựa chọn là càng lớn càng tốt. Các bạn hãy giúp quốc vương tìm số ngôi làng tối đa có thể chọn nhé.
Dữ liệu
Vào từ file văn bản league.inp:
- Dòng đầu tiên chứa hai số nguyên \(m\) và \(n\) \((1 \leq m, n \leq 1000)\).
- Trong \(m\) dòng còn lại, dòng thứ \(i\) chứa \(n\) số nguyên \(A_{i, 1}, A_{i, 2},\cdots, A_{i, n}\) \((1 \le A_{ij} \le 10^{18})\).
Kết quả
Ghi ra file văn bản league.out:
- In ra một dòng duy nhất là số lượng ngôi làng của liên minh mà quốc vương đã chọn.
Ràng buộc
- Subtask \(1\) (\(25\) điểm): \(1 \le m, n \le 100\)
- Subtask \(2\) (\(25\) điểm): \(1 \le m, n \le 500\) và mọi chỉ số sức manh \(A_{i, j}\) đều thỏa mãn tính chất: có đúng một ước nguyên tố và ước nguyên tố này không quá \(100\).
- Subtask \(3\) (\(50\) điểm): Không có ràng buộc gì thêm.
Ví dụ
Ví dụ 1
league.inp
6 7
1 2 4 9 7 11 1
6 8 16 10 19 19 1
10 8 5 4 2 15 1
13 2 5 6 5 12 1
15 2 4 5 6 11 1
17 19 8 32 8 17 1league.out
12Giải thích
Vùng màu đỏ trong bảng thể hiện các ngôi làng được chọn:
