Hoàn thành công việc
Đề bài
Mô tả
Tuệ được giao công việc, đánh số từ đến . Mỗi ngày, Tuệ làm các công việc còn dang dở từ những ngày trước theo quy tắc sau:
- Công việc đầu tiên trong ngày: Tuệ được chọn một công việc bất kỳ chưa hoàn thành và bắt đầu làm.
- Nếu đã chọn công việc , sau khi hoàn thành công việc , công việc tiếp theo được chọn phải thỏa mãn (và chưa hoàn thành).
- Nếu sau công việc không còn công việc nào hợp lệ để chọn, Tuệ phải đợi đến ngày hôm sau mới làm tiếp.
Để nhận được lương, Tuệ phải hoàn thành cả công việc, vì vậy Tuệ muốn làm xong tất cả trong ít ngày nhất có thể. Hãy viết chương trình xác định số ngày ít nhất cần thiết để Tuệ hoàn thành mọi công việc, và với mỗi ngày, đưa ra thứ tự các công việc được làm trong ngày đó.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên ().
- Dòng thứ hai chứa số nguyên ().
Dữ liệu ra
- Dòng đầu tiên in số nguyên : số ngày ít nhất cần thiết để hoàn thành cả công việc.
- dòng tiếp theo: dòng thứ bắt đầu bằng số , tiếp theo là số là các công việc được hoàn thành trong ngày thứ , theo đúng thứ tự làm. Nếu có nhiều cách hoàn thành trong số ngày ít nhất, in ra cách bất kỳ.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 2 2 4 4 |
2 2 2 4 2 1 3 |
Ngày thứ nhất làm công việc rồi (vì ). Ngày thứ hai làm công việc rồi (vì ). |
| 5 5 0 1 2 3 |
1 5 5 4 3 2 1 |
Làm tất cả trong một ngày: , , , . |
Bình luận