| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2019 - Sleepy Cow Herding | 100 (p) | 4.0s | 512M |
| 2 | USACO 2019 - The Great Revegetation | 100 (p) | 4.0s | 512M |
| 3 | USACO 2019 - Measuring Traffic | 100 (p) | 4.0s | 512M |
Ba cô bò từng đoạt giải của Farmer John là Bessie, Elsie và Mildred cứ luôn đi lang thang đến tận những nơi xa xôi của trang trại! Ông cần bạn giúp lùa chúng về đứng gần nhau.
Cánh đồng chính của trang trại dài và hẹp — ta có thể coi nó như một trục số, trên đó một con bò có thể đứng tại bất kỳ vị trí nguyên nào. Ba con bò hiện đang đứng tại các vị trí nguyên khác nhau, và Farmer John muốn di chuyển chúng sao cho chúng đứng tại ba vị trí liên tiếp (chẳng hạn các vị trí 6, 7 và 8).
Đáng tiếc, những con bò khá buồn ngủ và Farmer John rất khó thu hút sự chú ý để khiến chúng di chuyển. Tại bất kỳ thời điểm nào, ông chỉ có thể khiến một con bò di chuyển nếu nó đang ở một "đầu mút" (tức là có vị trí nhỏ nhất hoặc lớn nhất trong số tất cả các con bò). Khi di chuyển một con bò, ông có thể yêu cầu nó chuyển đến bất kỳ vị trí nguyên chưa bị chiếm nào, miễn là tại vị trí mới, nó không còn là một đầu mút. Có thể thấy rằng theo thời gian, những nước đi kiểu này thường đẩy các con bò ngày càng lại gần nhau hơn.
Hãy xác định số lần di chuyển ít nhất và nhiều nhất có thể thực hiện trước khi các con bò tụ lại tại ba vị trí liên tiếp.
Dữ liệu vào gồm một dòng chứa ba số nguyên cách nhau bởi dấu cách, cho biết vị trí của Bessie, Elsie và Mildred. Mỗi vị trí là một số nguyên trong phạm vi \(1 \ldots 10^9\).
Dòng đầu tiên chứa số lần di chuyển ít nhất Farmer John cần thực hiện để đưa các con bò lại gần nhau. Dòng thứ hai chứa số lần di chuyển nhiều nhất mà ông có thể thực hiện trước khi các con bò tụ lại với nhau.
Ví dụ 1
4 7 91
2Số lần di chuyển ít nhất là 1 — nếu Farmer John chuyển con bò ở vị trí 4 đến vị trí 8 thì các con bò sẽ đứng tại các vị trí liên tiếp 7, 8, 9. Số lần di chuyển nhiều nhất là 2. Chẳng hạn, có thể chuyển con bò ở vị trí 9 đến vị trí 6, sau đó chuyển con bò ở vị trí 7 đến vị trí 5.
USACO 2019 February Contest, Bronze — Sleepy Cow Herding
Tác giả: Matthew Fahrbach.
Một đợt hạn hán kéo dài đã khiến \(N\) đồng cỏ của Farmer John không còn chút cỏ nào. Tuy nhiên, mùa mưa sắp đến và đã tới lúc "phủ xanh trở lại".
Trong nhà kho, Farmer John có bốn thùng, mỗi thùng chứa một loại hạt giống cỏ khác nhau. Ông muốn gieo một trong các loại hạt giống này trên mỗi đồng cỏ. Là một người chăn bò sữa, Farmer John muốn bảo đảm mỗi con bò của mình có chế độ ăn đa dạng. Mỗi con trong số \(M\) con bò có hai đồng cỏ yêu thích, và ông muốn bảo đảm hai đồng cỏ ấy được trồng các loại cỏ khác nhau để mỗi con bò có thể lựa chọn giữa hai loại cỏ. Farmer John biết rằng không có đồng cỏ nào là nơi yêu thích của nhiều hơn \(3\) con bò.
Hãy giúp Farmer John chọn một loại cỏ cho mỗi đồng cỏ sao cho nhu cầu dinh dưỡng của tất cả các con bò đều được đáp ứng.
Dòng đầu tiên chứa \(N\) (\(2 \leq N \leq 100\)) và \(M\) (\(1 \leq M \leq 150\)). Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên trong phạm vi \(1 \ldots N\), mô tả cặp đồng cỏ yêu thích của một con bò của Farmer John.
In ra một số gồm \(N\) chữ số, trong đó mỗi chữ số nằm trong phạm vi \(1 \ldots 4\) và mô tả loại cỏ cần trồng trên từng đồng cỏ. Chữ số đầu tiên tương ứng với loại cỏ của đồng cỏ \(1\), chữ số thứ hai tương ứng với đồng cỏ \(2\), và cứ tiếp tục như vậy. Nếu có nhiều phương án hợp lệ, chỉ in số gồm \(N\) chữ số nhỏ nhất trong số đó.
Ví dụ 1
5 6
4 1
4 2
4 3
2 5
1 2
1 512133USACO 2019 February Contest, Bronze — The Great Revegetation
Tác giả: Dhruv Rohatgi.
Gần đây, lưu lượng xe trên tuyến đường cao tốc cạnh trang trại của Farmer John tăng mạnh, hoặc ít nhất Farmer John cảm thấy như vậy. Để biết chắc, ông muốn đo lưu lượng giao thông trên đường cao tốc bằng một bộ cảm biến, mỗi cảm biến có khả năng đo lưu lượng xe trên một đoạn đường.
Đáng tiếc, một ngày nọ khi đi qua chuồng bò, Farmer John vấp ngã và làm rơi hộp cảm biến vào một bể sữa lớn, khiến chúng không còn hoạt động tốt như trước. Thay vì đưa ra một giá trị lưu lượng chính xác duy nhất, giờ đây mỗi cảm biến xuất ra một khoảng giá trị có thể có. Chẳng hạn, một cảm biến có thể xuất ra khoảng \([7, 13]\), cho biết lưu lượng xe trên một đoạn đường không nhỏ hơn 7 và không lớn hơn 13.
Đường cao tốc chạy cạnh trang trại trong \(N\) dặm và xe trên đường chỉ đi theo một hướng, từ dặm 1 về phía dặm \(N\). Farmer John muốn lắp \(N\) cảm biến — mỗi đoạn dài 1 dặm của đường cao tốc có một cảm biến. Một số đoạn có đường dẫn nhập cho phép xe đi vào đường cao tốc; trong mỗi trường hợp như vậy, Farmer John sẽ lắp cảm biến trên đường dẫn nhập để đo (xấp xỉ) lượng xe đi vào. Một số đoạn có đường dẫn ra cho phép xe rời đường cao tốc; trong mỗi trường hợp như vậy, Farmer John sẽ lắp cảm biến trên đường dẫn ra. Mỗi đoạn có nhiều nhất một đường dẫn. Nếu một đoạn đường cao tốc không có đường dẫn nhập hay đường dẫn ra, Farmer John lắp cảm biến ngay trên đường cao tốc chính.
Với số liệu từ \(N\) cảm biến của Farmer John, hãy xác định những khoảng cụ thể nhất có thể mô tả lưu lượng xe ban đầu trên đường cao tốc trước dặm 1 và lưu lượng xe tiếp tục đi trên đường cao tốc sau dặm \(N\). Các khoảng này phải nhất quán với số liệu của cả \(N\) cảm biến.
Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 100\)). Mỗi dòng trong \(N\) dòng còn lại mô tả một đoạn đường dài 1 dặm, theo thứ tự từ dặm \(1\) đến dặm \(N\). Mỗi dòng chứa một chuỗi là on (nếu đoạn này có đường dẫn nhập), off (nếu có đường dẫn ra), hoặc none (nếu không có đường dẫn), theo sau là hai số nguyên trong phạm vi \(0 \ldots 1000\), biểu thị đầu mút dưới và đầu mút trên của khoảng đo từ cảm biến trên đoạn này. Nếu đoạn đường có một đường dẫn, số liệu cảm biến được đo trên đường dẫn đó. Nếu không, số liệu được đo trên đường cao tốc chính. Có ít nhất một đoạn đường cao tốc được ký hiệu là none.
Dòng đầu tiên chứa hai số nguyên biểu thị khoảng cụ thể nhất có thể của lưu lượng xe trước dặm 1. Dòng thứ hai chứa hai số nguyên biểu thị khoảng cụ thể nhất có thể của lưu lượng xe sau dặm \(N\). Dữ liệu luôn bảo đảm tồn tại một lời giải hợp lệ.
Ví dụ 1
4
on 1 1
none 10 14
none 11 15
off 2 310 13
8 12Trong ví dụ này, kết hợp số liệu từ đoạn 2 và đoạn 3 cho ta biết lưu lượng qua các đoạn này nằm trong khoảng \([11, 14]\), vì chỉ khoảng này nhất quán với cả hai số liệu \([10,14]\) và \([11,15]\). Ở dặm 1, chính xác 1 đơn vị lưu lượng đi vào từ một đường dẫn nhập, nên trước dặm 1, lưu lượng phải nằm trong khoảng \([10, 13]\). Ở dặm 4, từ 2 đến 3 đơn vị lưu lượng đi ra qua một đường dẫn ra, do đó khoảng lưu lượng có thể có sau đoạn này là \([8,12]\).
USACO 2019 February Contest, Bronze — Measuring Traffic
Tác giả: Brian Dean.