💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Phân phối Quà Giáng Sinh
GEN013
### 📌 Thông tin chung | Mục | Chi tiết | | :--- | :--- | | **Tên File Input** | `BAI4.INP` | | **Tên File Output** | `BAI4.OUT` | Các bài làm online các bạn chỉ cần dùng luồng vào/ra chuẩn --- ### 📝 Bài toán Ông già Noel có tổng cộng $A+B+C$ túi quà để lấp đầy, trong đó: * $A$ túi dành riêng cho miền núi (chỉ chứa quà loại N hoặc C). * $B$ túi dành riêng cho miền đồng bằng (chỉ chứa quà loại B hoặc C). * $C$ túi quà đặc biệt (có thể dùng cho cả núi và đồng bằng). Có $M$ món quà có sẵn. Mỗi món quà thứ $i$ được mô tả bởi giá sản xuất $v_i$ và loại: * 'N': Dành riêng cho miền núi. * 'B': Dành riêng cho miền đồng bằng. * (Giả định rằng các món quà không được gán loại 'C', mà 'C' chỉ là loại túi đặc biệt có thể chứa cả 'N' và 'B'. * **Dựa trên ví dụ, ta giả định mỗi món quà chỉ lấp đầy một túi quà**). **Mục tiêu:** 1. **Tối đa hóa** số lượng túi quà được lấp đầy (mỗi túi chứa một món quà). 2. Trong số các phương án tối đa hóa số túi, **tối thiểu hóa** tổng chi phí sản xuất của các món quà được chọn. Tổng số túi tối đa có thể lấp đầy là $\min(M, A+B+C)$. --- ### 📥 Định dạng Đầu vào Dữ liệu vào từ file `BAI4.INP`: * Dòng 1: Ba số nguyên $A, B, C$ (số lượng túi miền núi, đồng bằng, đặc biệt). * Dòng 2: Số nguyên $M$ (số món quà có sẵn). * $M$ dòng tiếp theo: Mỗi dòng mô tả món quà thứ $i$ với giá sản xuất $v_i$ và loại ('N' hoặc 'B'). Giới hạn (Không được cho rõ, nhưng từ Subtask ta suy luận): * $A, B, C$ là các số nguyên dương. * $M$ có thể lên đến vài nghìn. * $v_i$ là giá sản xuất. --- ### 📤 Định dạng Đầu ra Ghi ra file `BAI4.OUT` hai số nguyên trên một dòng: * Số túi quà được lấp đầy (số món quà được sử dụng). * Tổng chi phí sản xuất nhỏ nhất. --- ### ✨ Ví dụ | Dữ liệu | Kết quả | | :--- | :--- | | `2 1 1` <br> `4` <br> `5 N` <br> `6 B` <br> `3 B` <br> `7 B` | `3 14` | Giải thích: Tối đa lấp được 3 túi. $A=2, B=1, C=1$. Món quà $N$ (giá 5) được dùng cho túi $A$. Món quà $B$ giá 3 và 6, ta chọn 2 món $B$ rẻ nhất (giá 3 và 6) cho túi $B$ và $C$. Tổng chi phí: $5+3+6 = 14$. --- ### 🏷 Subtask | Subtask | Ràng buộc | Số điểm ước tính | | :--- | :--- | :--- | | 1 | $A=0, B=0$ | $15\%$ | | 2 | $C=0$ | $15\%$ | | 3 | $M \le 20$ | $20\%$ | | 4 | $M \le 1000$ | $30\%$ | | 5 | Không có ràng buộc bổ sung (Giả định $M$ lớn) | $20\%$ | ---
✅ Đã AC: 2 / 8 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