USACO 2018 - Teleportation
Xem PDFMột trong những công việc đồng áng mà bác nông dân John ghét nhất là vận chuyển những lượng lớn phân bò. Để đơn giản hóa quá trình này, ông nghĩ ra một phát minh xuất sắc: máy dịch chuyển phân bò! Thay vì chở phân giữa hai điểm bằng chiếc xe kéo phía sau máy kéo, ông có thể dùng máy dịch chuyển phân để đưa phân tức thời từ vị trí này sang vị trí khác.
Trang trại của bác nông dân John nằm dọc theo một con đường thẳng rất dài, nên mỗi vị trí trong trang trại có thể được mô tả đơn giản bằng vị trí của nó trên con đường này (tương ứng với một điểm trên trục số). Một máy dịch chuyển được mô tả bởi hai số \(x\) và \(y\): phân được đưa đến vị trí \(x\) có thể được dịch chuyển tức thời đến vị trí \(y\), hoặc ngược lại.
Bác nông dân John muốn vận chuyển phân từ vị trí \(a\) đến vị trí \(b\), và ông đã xây một máy dịch chuyển có thể hữu ích trong quá trình này (dĩ nhiên, ông không cần dùng máy dịch chuyển nếu nó không giúp ích). Hãy giúp ông xác định tổng quãng đường nhỏ nhất mà ông phải dùng máy kéo để chở phân.
Dữ liệu vào
Dòng đầu tiên và duy nhất chứa bốn số nguyên cách nhau bởi dấu cách: \(a\) và \(b\) mô tả vị trí bắt đầu và kết thúc, tiếp theo là \(x\) và \(y\) mô tả máy dịch chuyển. Mọi vị trí đều là số nguyên trong khoảng \(0 \ldots 100\) và không nhất thiết đôi một khác nhau.
Dữ liệu ra
In ra một số nguyên duy nhất là quãng đường nhỏ nhất mà bác nông dân John phải dùng máy kéo để chở phân.
Ví dụ
Ví dụ 1
Input
3 10 8 2
Output
3
Giải thích
Trong ví dụ này, chiến lược tốt nhất là chở phân từ vị trí \(3\) đến vị trí \(2\), dịch chuyển nó đến vị trí \(8\), rồi chở tiếp đến vị trí \(10\). Vì vậy, tổng quãng đường cần dùng máy kéo là \(1 + 2 = 3\).
Nguồn
USACO 2018 February Contest, Bronze — Teleportation
Tác giả bài toán: Brian Dean.
Kỳ thi:
- USACO 2018 - Tháng 2 - Hạng Đồng (1 Tháng 2., 2018)
Bình luận