Vạch chia trên thước
Đề bài
Mô tả
Một chiếc thước dài xăng-ti-mét có vạch chia, đánh số từ đến theo thứ tự từ đầu thước đến cuối thước. Vạch thứ nằm cách đầu thước xăng-ti-mét, trong đó (đầu thước) và (cuối thước).
Chiếc thước được coi là đo được khoảng cách nếu tồn tại hai vạch và () sao cho .
Cần dùng thước này để đo hai khoảng cách và (với ). Bạn được phép khắc thêm các vạch mới tại vị trí nguyên bất kỳ trong đoạn từ đến .
Hãy tìm số vạch ít nhất cần khắc thêm để chiếc thước đo được cả hai khoảng cách và , đồng thời chỉ ra vị trí của các vạch đó.
Nếu có nhiều đáp án cùng đạt số vạch ít nhất, in ra đáp án bất kỳ.
Dữ liệu vào
- Dòng đầu chứa bốn số nguyên dương , , , .
- Dòng thứ hai chứa số nguyên là vị trí các vạch chia có sẵn.
Dữ liệu ra
- Dòng đầu in ra một số nguyên không âm là số vạch ít nhất cần khắc thêm.
- Dòng thứ hai in ra số nguyên () là vị trí các vạch cần khắc thêm, theo thứ tự tuỳ ý. Nếu thì dòng này để trống hoặc bỏ qua.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 250 185 230 0 185 250 |
1 230 |
Khoảng cách đã đo được nhờ cặp vạch và , nhưng thì chưa. Khắc thêm vạch tại là đủ (khắc tại cũng cho đáp án hợp lệ). |
| 2 300 185 230 0 300 |
2 185 230 |
Thước chỉ có hai vạch đầu và cuối nên chưa đo được khoảng cách nào ngoài . Không một vạch đơn lẻ nào giúp đo được đồng thời và , nên cần khắc thêm hai vạch. |
| 4 250 185 230 0 20 185 250 |
0 | Cặp cho khoảng cách , cặp cho khoảng cách , nên không cần khắc thêm vạch nào. |
Bình luận