Sắp xếp lỗ sâu
Nộp bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Python 3
5.0s
Giới hạn bộ nhớ:
256M
Đầu vào:
stdin
Đầu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, Go, Java, Kotlin, Pascal, Python, Scratch
- con bò ở sai vị trí (hoán vị ). Có lỗ sâu, mỗi lỗ nối hai vị trí với độ rộng . Hai con bò ở hai đầu lỗ sâu có thể hoán đổi vị trí. Tìm giá trị lớn nhất sao cho chỉ dùng lỗ sâu có độ rộng cũng đủ để đưa mọi bò về đúng vị trí. In nếu đã đúng vị trí.
Dữ liệu vào
- Dòng đầu: và .
- Dòng thứ hai: hoán vị .
- dòng tiếp: , , .
Dữ liệu ra
- lớn nhất, hoặc .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 3 2 1 4 1 2 9 1 3 7 2 3 10 2 4 3 |
9 | Dùng lỗ rộng ≥9: {1-2(9), 2-3(10)}. Bò 1,2,3 liên thông → sắp xếp được. |
Bình luận