💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Đại Chiến Tinh Hệ
PLANETWAR
### 📌 Thông tin chung | Mục | Chi tiết | | :--- | :--- | | Tên File Input | PLANETWAR.INP | | Tên File Output | PLANETWAR.OUT | ### Bài toán Vào năm 3024, nhân loại bắt đầu cuộc chiến chinh phục các hành tinh của người ngoài hành tinh. Phe người sở hữu H hành tinh, phe ngoài hành tinh kiểm soát A hành tinh. Tại mỗi hành tinh của con người (i), ban đầu có n_i tàu Saber Tooth và mỗi năm sản xuất thêm m_i tàu. Tại mỗi hành tinh của người ngoài hành tinh (j), ban đầu có s_j voi ma mút Mammoth và mỗi năm sản xuất thêm p_j con. Commander Bradley Bennett đề ra chiến lược: Mỗi hành tinh người (i) sẽ được phân công tấn công duy nhất một hành tinh ngoài hành tinh (j). Ngược lại, mỗi hành tinh ngoài hành tinh (j) cũng chỉ bị tấn công bởi duy nhất một hành tinh người (i). Giả sử hành tinh người (i) xuất quân vào đầu năm T. Khi đó, số tàu mang đi là n_i + T * m_i. Thời gian di chuyển từ hành tinh (i) đến hành tinh (j) là D[i][j] năm. Tàu sẽ cập bến vào đầu năm (T + D[i][j]). Tại thời điểm này, số lượng voi ma mút tại hành tinh (j) là s_j + (T + D[i][j]) * p_j. Điều kiện chiến thắng tại một hành tinh: Số lượng tàu người không nhỏ hơn số lượng voi ma mút tại thời điểm cập bến. Yêu cầu: Tìm thời gian tối thiểu (năm) để tất cả A hành tinh ngoài hành tinh đều bị tiêu diệt. Nếu không thể tiêu diệt hết, in ra IMPOSSIBLE. ### Định dạng Đầu vào Dòng đầu tiên chứa hai số nguyên H và A (1 <= H, A <= 250). Dòng thứ hai chứa H cặp số nguyên n_i, m_i (0 <= n_i, m_i <= 40000). Dòng thứ ba chứa A cặp số nguyên s_j, p_j (0 <= s_j, p_j <= 40000). H dòng tiếp theo, mỗi dòng chứa A số nguyên D[i][j] (0 <= D[i][j] <= 40000) là thời gian di chuyển. Dữ liệu kết thúc bằng dòng chứa hai số 0. ### Định dạng Đầu ra Một số nguyên duy nhất là thời gian tối thiểu tìm được hoặc IMPOSSIBLE. ### Ví dụ Input: 2 1 2 3 0 3 2 2 2 2 0 0 Output: 6 ### Subtasks Subtask 1 (30%): H, A <= 10; Các giá trị thời gian <= 100. Subtask 2 (70%): H, A <= 250; Các giá trị thời gian <= 40000.
✅ Đã AC: 1 / 3 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