In tài liệu
Đề bài
Mô tả
Khi in tài liệu, tiến sĩ Lecter nhận ra các trang ông in ra hoàn toàn lộn xộn. Tài liệu có trang, đánh số từ đến . Đã có tổng cộng tờ giấy được in, tờ thứ chứa nội dung của hai trang và , mỗi trang ở một mặt của tờ giấy (tờ giấy có thể lật tùy ý nên trang hoặc trang đều có thể đứng trước). Vì việc in rất tốn thời gian và số tờ giấy trắng còn lại có hạn, tiến sĩ Lecter muốn tìm số tờ giấy ít nhất cần in thêm (mỗi tờ in hai trang tùy chọn lên hai mặt) để có thể sắp xếp một tập con các tờ giấy thành một tài liệu dùng được. Vì tài liệu này chỉ do tiến sĩ Lecter sử dụng, chỉ cần tồn tại dãy chỉ số sao cho trang thứ trong tài liệu (đọc lần lượt từng mặt của các tờ theo thứ tự đã xếp) có nội dung trang số () là tài liệu dùng được.
Ví dụ, với , và hai tờ đã in: tờ thứ nhất chứa hai trang , tờ thứ hai chứa hai trang . Khi đó tiến sĩ Lecter chỉ cần in thêm một tờ chứa các trang . Xếp các tờ theo thứ tự , ông có một tài liệu dùng được (các trang thứ của tài liệu tạo thành dãy đầy đủ các trang ).
Yêu cầu: Hãy giúp tiến sĩ Lecter tìm số tờ giấy ít nhất cần in thêm để tạo được một tài liệu dùng được.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và (, ).
- Dòng thứ trong dòng tiếp theo chứa hai số nguyên và ().
Dữ liệu ra
In ra một số nguyên là số tờ giấy ít nhất cần in thêm để tạo được một tài liệu dùng được.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 2 1 4 3 3 |
1 | In thêm tờ và xếp các tờ theo thứ tự . |
| 3 2 3 2 2 2 |
1 | Không dùng tờ . Lật tờ thành , in thêm một tờ chứa hai trang (hoặc , cũng được) và đặt nó trước tờ . |
| 5 3 2 3 4 5 1 4 |
0 | Không cần in thêm: xếp các tờ có sẵn theo thứ tự . |
Bình luận