| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2014 - Ski Course Design | 100 (p) | 4.0s | 512M |
| 2 | USACO 2014 - Bessie Slows Down | 100 (p) | 4.0s | 512M |
| 3 | USACO 2014 - Balanced Teams | 100 (p) | 4.0s | 512M |
Farmer John có \(N\) ngọn đồi trên trang trại (\(1 \le N \le 1\,000\)), mỗi ngọn có độ cao nguyên trong đoạn từ \(0\) đến \(100\). Vào mùa đông, do những ngọn đồi này có rất nhiều tuyết, FJ thường xuyên tổ chức một trại huấn luyện trượt tuyết.
Không may, FJ vừa biết về một loại thuế mới sẽ được áp dụng vào năm sau đối với những trang trại dùng làm trại huấn luyện trượt tuyết. Tuy nhiên, sau khi đọc kỹ luật, ông phát hiện định nghĩa chính thức của một trại trượt tuyết yêu cầu chênh lệch giữa ngọn đồi cao nhất và thấp nhất trên khu đất phải lớn hơn hẳn \(17\). Vì vậy, nếu hạ thấp những ngọn đồi cao nhất và đắp thêm để nâng những ngọn đồi thấp hơn, FJ có thể tránh phải nộp thuế miễn là chênh lệch mới giữa ngọn đồi cao nhất và thấp nhất không quá \(17\).
Nếu chi phí để thay đổi độ cao của một ngọn đồi đi \(x\) đơn vị là \(x^2\) đơn vị tiền, FJ phải trả ít nhất bao nhiêu? FJ chỉ chấp nhận thay đổi độ cao của mỗi ngọn đồi một lượng nguyên.
In ra số tiền nhỏ nhất FJ cần trả để điều chỉnh độ cao các ngọn đồi sao cho chênh lệch giữa độ cao lớn nhất và nhỏ nhất không quá \(17\) đơn vị.
Ví dụ 1
5
20
4
1
24
2118Trang trại của FJ có \(5\) ngọn đồi với độ cao \(1\), \(4\), \(20\), \(21\) và \(24\).
FJ giữ nguyên các ngọn đồi cao \(4\), \(20\) và \(21\). Ông đắp thêm cho ngọn đồi cao \(1\) để nâng nó lên độ cao \(4\), tốn \(3^2=9\). Ông hạ ngọn đồi cao \(24\) xuống độ cao \(21\), cũng tốn \(3^2=9\).
USACO 2014 January Contest, Bronze — Problem 1: Ski Course Design
Tác giả: Brian Dean, 2014.
Cô bò Bessie đang thi đấu môn trượt tuyết băng đồng tại Thế vận hội Moolympic mùa đông. Ban đầu, cô di chuyển với vận tốc \(1\) mét mỗi giây. Tuy nhiên, theo thời gian cô ngày càng mệt và bắt đầu chậm lại. Mỗi lần Bessie chậm lại, vận tốc của cô giảm: sau lần đầu tiên, cô di chuyển với vận tốc \(1/2\) mét mỗi giây; sau hai lần, cô di chuyển với vận tốc \(1/3\) mét mỗi giây; và cứ tiếp tục như vậy.
Bạn được cho biết thời điểm và vị trí Bessie chậm lại dưới dạng một chuỗi sự kiện. Một sự kiện như
T 17
có nghĩa là Bessie chậm lại tại một thời điểm cụ thể, ở đây là sau khi cuộc đua bắt đầu \(17\) giây. Một sự kiện như
D 10
có nghĩa là Bessie chậm lại tại một khoảng cách cụ thể tính từ điểm xuất phát, trong trường hợp này là \(10\) mét.
Cho danh sách \(N\) sự kiện như vậy (\(1 \le N \le 10\,000\)), hãy tính thời gian tính bằng giây để Bessie đi hết một kilômét. Làm tròn đáp án đến số giây nguyên gần nhất; \(0{,}5\) được làm tròn lên \(1\).
T x hoặc D x, lần lượt biểu thị một sự kiện theo thời gian hoặc theo khoảng cách. Trong cả hai trường hợp, \(x\) là một số nguyên và sự kiện được đảm bảo xảy ra trước khi Bessie đi đủ tổng quãng đường một kilômét. Nhiều sự kiện có thể xảy ra đồng thời, khiến Bessie chậm đi đáng kể cùng một lúc. Các sự kiện có thể không được liệt kê theo thứ tự.In ra tổng thời gian cần thiết để Bessie đi được \(1\) kilômét, làm tròn đến số giây nguyên gần nhất với trường hợp đúng nửa giây được làm tròn lên.
Ví dụ 1
2
T 30
D 102970Bessie chậm lại tại thời điểm \(t=30\) và tại khoảng cách \(d=10\).
Bessie đi \(10\) mét đầu tiên với vận tốc \(1\) mét/giây, mất \(10\) giây. Sau đó cô chậm lại còn \(1/2\) mét/giây, nên mất \(20\) giây để đi \(10\) mét tiếp theo. Khi ấy cô đạt mốc thời gian \(30\) giây và lại chậm đi, còn \(1/3\) mét/giây. Vì vậy, \(980\) mét còn lại mất \(980 \cdot 3=2940\) giây. Tổng thời gian là \(10+20+2940=2970\) giây.
USACO 2014 January Contest, Silver — Problem 1: Bessie Slows Down
Tác giả: Brian Dean, 2014.
Tổng cộng có \(12\) cô bò của Farmer John tham dự Thế vận hội Moolympic mùa đông năm nay, mỗi cô có một mức kỹ năng nguyên từ \(1\) đến \(1\,000\,000\).
Farmer John muốn chia họ thành \(4\) đội, mỗi đội \(3\) cô bò, sao cho các đội tương đối "cân bằng" về tổng kỹ năng; mức kỹ năng của một đội chính là tổng mức kỹ năng của các cô bò trong đội. Cụ thể, ông muốn tối thiểu hóa \(S-s\), trong đó \(S\) và \(s\) lần lượt là mức kỹ năng lớn nhất và nhỏ nhất trong số các đội. Nhờ vậy, chênh lệch giữa đội giỏi nhất và đội kém nhất sẽ nhỏ nhất có thể.
Hãy giúp Farmer John xác định giá trị nhỏ nhất có thể của \(S-s\).
Gồm \(12\) dòng, mỗi dòng chứa mức kỹ năng của một cô bò.
In ra giá trị nhỏ nhất có thể của \(S-s\).
Ví dụ 1
1
2
3
4
5
6
7
8
9
10
11
121Một cách chia đội là \((12,1,7)\), \((9,8,3)\), \((10,5,4)\) và \((11,2,6)\). Hai đội đầu có mức kỹ năng \(20\), còn hai đội sau có mức kỹ năng \(19\).
USACO 2014 January Contest, Bronze — Problem 3: Balanced Teams
Tác giả: Brian Dean, 2014.