Bữa tối của An và Bình
Đề bài
Mô tả
Thành phố có đường ngang và đường dọc. Tại mỗi giao lộ giữa một đường ngang và một đường dọc có đúng một nhà hàng. Chi phí một bữa tối tại nhà hàng nằm ở giao lộ của đường ngang thứ và đường dọc thứ là .
An và Bình chọn nhà hàng theo quy tắc sau: An chọn đường ngang trước, sau đó Bình chọn đường dọc. An muốn chi phí bữa tối lớn nhất có thể, còn Bình muốn chi phí nhỏ nhất có thể. Cả hai đều chơi tối ưu, và An biết rõ rằng sau lựa chọn của mình thì Bình sẽ tìm cách giảm chi phí xuống thấp nhất.
Hãy tìm chi phí bữa tối cuối cùng.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên và : số đường ngang và số đường dọc.
- dòng tiếp theo, dòng thứ chứa số nguyên .
Dữ liệu ra
In ra một số nguyên duy nhất: chi phí bữa tối của An và Bình.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 4 4 1 3 5 2 2 2 2 5 4 5 1 |
2 | Nếu An chọn đường ngang 1, Bình chọn nhà hàng giá 1. Nếu An chọn đường ngang 3, Bình cũng chọn được nhà hàng giá 1. Chọn đường ngang 2 thì mọi nhà hàng đều giá 2, nên An chọn đường ngang 2 và đáp án là 2. |
| 3 3 1 2 3 2 3 1 3 1 2 |
1 | Mỗi đường ngang đều chứa một nhà hàng giá 1, nên dù An chọn thế nào Bình cũng ép được chi phí về 1. |
| 2 2 1 2 3 4 |
3 | An chọn đường ngang 2 (giá nhỏ nhất trên đó là 3) thay vì đường ngang 1 (giá nhỏ nhất là 1). Lưu ý thứ tự chọn là quan trọng: nếu Bình chọn trước thì kết quả sẽ là 2. |
Bình luận