Du lịch
Đề bài
Mô tả
Ở một đất nước xa xôi có một du khách tên Thanh, người mong muốn đạp xe du lịch khắp đất nước. Đất nước có thành phố, đánh số từ đến . Mỗi thành phố hoặc không có điểm tham quan nào mà Thanh muốn ghé, hoặc có đúng điểm tham quan mà Thanh muốn ghé.
Thanh đã sắp xếp một lộ trình đi qua tất cả các thành phố: thành phố thứ trên lộ trình là , thành phố thứ là , và chuyến đi kết thúc khi đến thành phố . Thanh muốn hoàn thành chuyến đi trong đúng tháng (), nên cần lên kế hoạch hợp lý.
Khi Thanh đến một thành phố, nếu thành phố đó có điểm tham quan mà anh muốn ghé, anh nhận được điểm vui; ngược lại anh nhận điểm buồn. Một tháng đủ để anh đi qua bao nhiêu thành phố tùy ý, nhưng anh cũng muốn nghỉ ngơi một chút. Thanh luôn nghỉ tại thành phố cuối cùng anh đến trong tháng đó (nếu thành phố này có điểm tham quan, anh luôn tham quan trước khi nghỉ). Thanh muốn mỗi tháng đều có kế hoạch đi, tức là mỗi tháng anh đến ít nhất một thành phố mới.
Thanh cần lập một lịch trình đi và nghỉ, tức là một dãy , trong đó là số hiệu thành phố nơi Thanh nghỉ trong tháng thứ . Vì chuyến đi kết thúc sau tháng cuối cùng nên . Ví dụ: , , , nghĩa là: tháng anh đến thành phố và , nghỉ ở thành phố ; tháng anh đến thành phố và , nghỉ ở thành phố ; tháng anh đến thành phố và nghỉ ở đó. Có nhiều lịch trình như vậy.
Với một lịch trình , gọi là giá trị tuyệt đối của hiệu giữa số điểm vui và số điểm buồn nhận được trong tháng thứ . Giá trị lớn nhất trong dãy được gọi là .
Thanh muốn chọn lịch trình có nhỏ nhất. Có thể có nhiều lịch trình cùng đạt nhỏ nhất; khi đó anh muốn chọn lịch trình có thứ tự từ điển nhỏ nhất. So sánh thứ tự từ điển của hai dãy là so sánh tại vị trí khác nhau đầu tiên, chẳng hạn .
Dữ liệu vào
- Dòng đầu tiên gồm hai số nguyên dương và : số thành phố và số tháng du lịch.
- dòng tiếp theo, dòng thứ gồm hai số nguyên và : là số hiệu thành phố thứ trên lộ trình; nếu thành phố có điểm tham quan Thanh thích, nếu không. Các giá trị đôi một khác nhau, tức là là một hoán vị của .
Dữ liệu ra
In ra trên một dòng số nguyên dương : lịch trình tìm được.
Ràng buộc
- ,
- là một hoán vị của ;
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 8 3 2 0 3 1 4 1 1 0 5 0 6 1 7 1 8 0 |
1 6 8 | Tháng có điểm vui và điểm buồn, tháng có điểm vui và điểm buồn, tháng có điểm vui và điểm buồn, nên , nhỏ nhất có thể. Các lịch trình đạt được là , , ; nhỏ nhất theo thứ tự từ điển là . |
| 5 3 3 1 2 1 4 0 1 1 5 1 |
3 1 5 | Ví dụ bổ sung. Tổng điểm vui trừ điểm buồn là nên ; lịch trình chia thành các tháng , , với . |
Bình luận