Nắp cống và đồng xu
Đề bài
Mô tả
Có nắp cống xếp thành một hàng ngang, đánh số từ đến từ trái sang phải. Trên mỗi nắp cống có đúng một viên đá, và dưới mỗi nắp cống có đúng một đồng xu. Ban đầu, Nastya đứng cạnh nắp cống thứ .
Trong mỗi lượt, Nastya có thể thực hiện đúng một trong các hành động sau (mỗi hành động tính là một lượt):
- Nếu nắp cống mà Nastya đang đứng cạnh có ít nhất một viên đá, ném đúng một viên đá từ nắp đó sang một nắp cống khác bất kỳ (xa hay gần đều được).
- Di chuyển sang nắp cống kề bên (trái hoặc phải).
- Nếu nắp cống Nastya đang đứng cạnh không còn viên đá nào, mở nắp và lấy đồng xu bên dưới. Sau khi lấy, nắp được đóng lại ngay (không tốn thêm lượt).
Nastya cần lấy toàn bộ đồng xu. Hãy tính số lượt tối thiểu cần thực hiện.
Dữ liệu vào
Một dòng chứa hai số nguyên và — số nắp cống và vị trí ban đầu của Nastya.
Dữ liệu ra
In ra một số nguyên duy nhất — số lượt tối thiểu cần thiết để lấy hết tất cả đồng xu.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 | 6 | Ném viên đá ở nắp sang nắp (1 lượt), mở nắp lấy xu (1 lượt), đi sang nắp (1 lượt), ném từng viên trong viên ở nắp sang nắp (2 lượt), mở nắp lấy xu (1 lượt). Tổng lượt. |
| 4 2 | 13 | Chiến lược tối ưu là gom hết đá về một đầu rồi mở dần các nắp đã sạch. |
| 5 1 | 15 | Khi hoặc , đáp án bằng . |
Bình luận