💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Đường Đi Nguyên Tố
PRIMEPATH
### 📌 Thông tin chung | Mục | Chi tiết | | :--- | :--- | | **Tên Bài Toán** | Đường Đi Nguyên Tố (Prime Path) | | **Nguồn** | Thuật toán đồ thị / Số học / Segmented Sieve. | | **Tên File Input** | `PRIMEPATH.INP` | | **Tên File Output** | `PRIMEPATH.OUT` | --- ### 📝 Bài toán Cho một lưới số nguyên dương $A$ kích thước $N \times M$. Mỗi ô chứa một giá trị $A[i][j]$ với $0 \le A[i][j] \le 10^{12}$. Bạn đứng ở ô $(1, 1)$ và muốn đi đến ô $(N, M)$. * Bạn chỉ được đi vào các ô có giá trị là số nguyên tố. * Bạn có thể di chuyển theo 4 hướng: Trái, Phải, Lên, Xuống (sang các ô kề cạnh). Yêu cầu: Tìm độ dài đường đi ngắn nhất từ $(1, 1)$ đến $(N, M)$. Quy ước: Nếu ô $(1, 1)$ hoặc ô $(N, M)$ không phải là số nguyên tố, hoặc không tồn tại đường đi, hãy in ra $-1$. --- ### 📥 Định dạng Đầu vào Dữ liệu vào từ file `PRIMEPATH.INP`: * Dòng 1: Hai số nguyên $N, M$ — kích thước lưới. * $N$ dòng tiếp theo: mỗi dòng gồm $M$ số nguyên $A[i][j]$. Giới hạn: * $1 \le N, M \le 2000$. * $1 \le N \times M \le 4 \times 10^6$. * $0 \le A[i][j] \le 10^{12}$. --- ### 📤 Định dạng Đầu ra Ghi ra file `PRIMEPATH.OUT` một số duy nhất: 1. Độ dài đường đi ngắn nhất, hoặc 2. $-1$ nếu không thể đi được. --- ### ✨ Ví dụ | Input | Output | | :--- | :--- | | `3 4` <br> `2 4 5 7` <br> `11 6 8 13` <br> `17 19 23 29` | `6` | --- ### 🏷 Ràng buộc – Subtask theo thuật toán kiểm tra số nguyên tố | Tỷ lệ điểm | Ràng buộc | | :--- | :--- | | $10\%$ | $A[i][j] \le 10^6$; $N \times M \le 10^5$ | | $25\%$ | $A[i][j] \le 10^7$ | | $30\%$ | Giá trị các ô trong mỗi test nằm trong đoạn $[L, R]$, $R - L \le 10^6$ | | $35\%$ | $A[i][j] \le 10^{12}$ không ràng buộc theo đoạn | ---
✅ Đã AC: 0 / 1 submissions
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng