| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2018 - Teleportation | 100 (p) | 4.0s | 512M |
| 2 | USACO 2018 - Hoofball | 100 (p) | 4.0s | 512M |
| 3 | USACO 2018 - Taming the Herd | 100 (p) | 4.0s | 512M |
Mộ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ò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.
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ụ 1
3 10 8 23Trong 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\).
USACO 2018 February Contest, Bronze — Teleportation
Tác giả bài toán: Brian Dean.
Để chuẩn bị cho giải đấu hoofball sắp tới, bác nông dân John đang huấn luyện \(N\) cô bò của mình (được đánh số thuận tiện từ \(1 \dots N\), với \(1 \leq N \leq 100\)) cách chuyền bóng. Tất cả các cô bò đứng dọc theo một đường thẳng rất dài ở một phía của chuồng, trong đó cô bò \(i\) đứng cách chuồng \(x_i\) đơn vị (\(1 \leq x_i \leq 1000\)). Mỗi cô bò đứng tại một vị trí khác nhau.
Khi bắt đầu buổi tập, bác nông dân John sẽ chuyền một số quả bóng cho những cô bò khác nhau. Khi cô bò \(i\) nhận được bóng, dù từ bác nông dân John hay từ một cô bò khác, cô sẽ chuyền bóng cho cô bò gần mình nhất (nếu có nhiều cô bò cùng cách cô một khoảng bằng nhau, cô sẽ chuyền bóng cho cô bò nằm xa nhất về bên trái trong số đó). Để tất cả các cô bò đều được luyện chuyền bóng ít nhất một chút, bác nông dân John muốn bảo đảm rằng mỗi cô bò sẽ cầm bóng ít nhất một lần. Hãy giúp ông tìm số quả bóng ít nhất cần phát lúc đầu để điều này có thể xảy ra, giả sử ông trao bóng cho một tập hợp bò ban đầu thích hợp.
Dòng đầu tiên chứa \(N\). Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách, trong đó số nguyên thứ \(i\) là \(x_i\).
In ra số quả bóng ít nhất mà bác nông dân John phải chuyền ban đầu cho đàn bò để mỗi cô bò đều có thể cầm bóng ít nhất một lần.
Ví dụ 1
5
7 1 3 11 42Trong ví dụ trên, bác nông dân John nên chuyền một quả bóng cho cô bò tại \(x=1\) và một quả bóng cho cô bò tại \(x=11\). Cô bò tại \(x=1\) sẽ chuyền bóng cho cô bò tại \(x=3\), sau đó quả bóng này sẽ qua lại giữa cô bò tại \(x=3\) và cô bò tại \(x=4\). Cô bò tại \(x=11\) sẽ chuyền bóng cho cô bò tại \(x=7\); cô bò này sẽ chuyền bóng cho cô bò tại \(x=4\), sau đó quả bóng cũng sẽ luân chuyển giữa cô bò tại \(x=3\) và cô bò tại \(x=4\). Nhờ vậy, mỗi cô bò đều sẽ được chuyền bóng ít nhất một lần (có thể bởi bác nông dân John hoặc bởi một cô bò khác).
Có thể thấy rằng không tồn tại một cô bò duy nhất mà nếu bác nông dân John chuyền bóng cho cô ấy lúc đầu thì cuối cùng mọi cô bò đều sẽ được chuyền bóng.
USACO 2018 February Contest, Bronze — Hoofball
Tác giả bài toán: Dhruv Rohatgi.
Vào sáng sớm, bác nông dân John thức giấc vì tiếng gỗ vỡ vụn. Lại là đàn bò, và chúng lại đang phá chuồng trốn ra ngoài!
Bác nông dân John đã quá chán ngán những vụ phá chuồng vào buổi sáng của đàn bò và quyết định rằng như thế là đủ: đã đến lúc phải mạnh tay. Ông đóng lên tường chuồng một bộ đếm theo dõi số ngày kể từ vụ phá chuồng gần nhất. Vì vậy, nếu một vụ phá chuồng xảy ra vào buổi sáng thì bộ đếm trong ngày đó sẽ là \(0\); nếu vụ phá chuồng gần nhất xảy ra \(3\) ngày trước thì bộ đếm sẽ hiển thị \(3\). Bác nông dân John ghi lại giá trị của bộ đếm mỗi ngày một cách cẩn thận.
Cuối năm đã đến và bác nông dân John sẵn sàng tính sổ. Lũ bò sẽ phải trả giá, ông nói! Nhưng thật bất ngờ, một số mục trong nhật ký của ông đã bị mất!
Bác nông dân John chắc chắn rằng ông bắt đầu ghi nhật ký đúng vào ngày xảy ra một vụ phá chuồng. Trong tất cả các chuỗi sự kiện phù hợp với những mục nhật ký còn lại, hãy giúp ông xác định số vụ phá chuồng nhỏ nhất và lớn nhất có thể đã xảy ra trong khoảng thời gian được ghi lại.
Dòng đầu tiên chứa một số nguyên \(N\) (\(1 \leq N \leq 100\)), biểu thị số ngày kể từ khi bác nông dân John bắt đầu ghi lại bộ đếm các vụ phá chuồng của đàn bò.
Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách. Số nguyên thứ \(i\) là \(-1\), cho biết mục nhật ký của ngày \(i\) bị mất, hoặc là một số nguyên không âm \(a_i\) (không quá \(100\)), cho biết bộ đếm ở ngày \(i\) có giá trị \(a_i\).
Nếu không tồn tại chuỗi sự kiện nào phù hợp với nhật ký không đầy đủ của bác nông dân John và với thông tin rằng đàn bò chắc chắn đã phá chuồng vào buổi sáng ngày \(1\), in ra số nguyên duy nhất \(-1\). Nếu có, in ra hai số nguyên cách nhau bởi dấu cách \(m\) rồi đến \(M\), trong đó \(m\) là số vụ phá chuồng nhỏ nhất trong mọi chuỗi sự kiện phù hợp và \(M\) là số vụ lớn nhất.
Ví dụ 1
4
-1 -1 -1 12 3Trong ví dụ này, ta có thể suy ra rằng một vụ phá chuồng buộc phải xảy ra vào ngày \(3\). Biết rằng một vụ phá chuồng cũng xảy ra vào ngày \(1\), điều duy nhất còn chưa chắc chắn là có vụ phá chuồng nào xảy ra vào ngày \(2\) hay không. Do đó, tổng cộng có từ \(2\) đến \(3\) vụ phá chuồng.
USACO 2018 February Contest, Bronze — Taming the Herd
Tác giả bài toán: Dhruv Rohatgi.