| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2012 - Hay Bales | 100 (p) | 4.0s | 512M |
| 2 | USACO 2012 - Cow Photography (Bronze Level) | 100 (p) | 4.0s | 512M |
| 3 | USACO 2012 - Escaping the Farm | 100 (p) | 4.0s | 512M |
Đàn bò lại giở trò! Farmer John đã cẩn thận sắp xếp \(N\) đống kiện cỏ khô (\(1 \leq N \leq 10\,000\)), mỗi đống có cùng chiều cao. Tuy nhiên, khi ông không để ý, đàn bò chuyển một số kiện cỏ khô giữa các đống, khiến chiều cao của chúng không còn nhất thiết bằng nhau. Cho chiều cao mới của tất cả các đống, hãy giúp Farmer John xác định số kiện cỏ khô ít nhất mà ông cần di chuyển để khôi phục tất cả các đống về chiều cao ban đầu bằng nhau.
Dòng đầu tiên chứa số lượng đống \(N\) (\(1 \leq N \leq 10\,000\)).
Mỗi dòng trong \(N\) dòng tiếp theo chứa số kiện cỏ khô trong một đống, là một số nguyên trong khoảng \(1 \ldots 10\,000\).
In một số nguyên là số kiện cỏ khô ít nhất cần di chuyển để khôi phục các đống về cùng một chiều cao.
Ví dụ 1
4
2
10
7
17Có 4 đống với chiều cao lần lượt là 2, 10, 7 và 1.
Bằng cách di chuyển 7 kiện cỏ khô (3 kiện từ đống 2 sang đống 1, 2 kiện từ đống 2 sang đống 4 và 2 kiện từ đống 3 sang đống 4), ta có thể làm cho mọi đống đều có chiều cao 5.
USACO 2011 December Contest, Bronze Division — Hay Bales. Tác giả đề: Brian Dean, 2011.
Hôm nay những chú bò đặc biệt tinh nghịch! Nông dân John chỉ muốn chụp một bức ảnh những chú bò đang đứng thành hàng, nhưng chúng cứ di chuyển ngay trước khi ông kịp bấm máy.
Cụ thể, \(N\) (\(1 \le N \le 20\,000\)) chú bò của FJ được đánh số hiệu từ \(1\) đến \(N\). FJ muốn chụp những chú bò đứng thành hàng theo một thứ tự rất cụ thể, được biểu diễn bởi nội dung của mảng \(A[1..N]\), trong đó \(A[j]\) là số hiệu của chú bò thứ \(j\) trong thứ tự này. Ông xếp những chú bò theo đúng thứ tự đó, nhưng ngay trước khi ông kịp nhấn nút chụp ảnh, có nhiều nhất một chú bò chuyển sang một vị trí mới trong hàng. Chính xác hơn, hoặc không có chú bò nào di chuyển, hoặc một chú bò rời vị trí hiện tại rồi chen trở lại vào một vị trí mới trong hàng. Dù bực mình nhưng không nản chí, FJ lại xếp những chú bò theo thứ tự trong \(A\); tuy nhiên, ngay trước lúc ông kịp chụp, lại có nhiều nhất một chú bò (khác với chú bò đầu tiên) chuyển sang một vị trí mới trong hàng.
Quá trình trên lặp lại cho đến khi FJ chụp tổng cộng năm bức ảnh rồi bỏ cuộc. Cho biết nội dung của từng bức ảnh, hãy khôi phục thứ tự dự định ban đầu \(A\). Mỗi bức ảnh cho thấy một thứ tự của đàn bò thu được từ thứ tự ban đầu trong \(A\) sau khi có nhiều nhất một chú bò chuyển sang vị trí mới. Hơn nữa, nếu một chú bò tự chuyển sang vị trí mới trong một bức ảnh thì nó không chủ động di chuyển trong bất kỳ bức ảnh nào khác (tất nhiên, vị trí của nó vẫn có thể thay đổi do những chú bò khác di chuyển).
Ví dụ 1
5
1
2
3
4
5
2
1
3
4
5
3
1
2
4
5
4
1
2
3
5
5
1
2
3
41
2
3
4
5Có \(5\) chú bò mang số hiệu \(1\), \(2\), \(3\), \(4\) và \(5\). Trong mỗi bức ảnh trong số \(5\) bức ảnh, một chú bò khác nhau chuyển lên đầu hàng (mặc dù chúng có thể chuyển đến bất kỳ vị trí nào khác nếu muốn).
Thứ tự ban đầu chính xác \(A[1..5]\) là \(1,2,3,4,5\).
USACO 2011 December Contest, Bronze Division — Cow Photography (Bronze Level)
Tác giả đề: Brian Dean, 2011.
Những chú bò đã vạch ra một kế hoạch táo bạo để thoát khỏi sự kiểm soát của Nông dân John. Chúng đã xoay xở kiếm được một chiếc bè bơm hơi nhỏ; dưới màn đêm che phủ, một nhóm bò sẽ lên bè và chèo qua con sông giáp với trang trại. Kế hoạch có vẻ hoàn hảo, cho đến khi những chú bò nhận ra rằng chiếc bè bơm hơi nhỏ của chúng có thể không chịu được nhiều trọng lượng!
\(N\) chú bò (\(1 \le N \le 20\)) có trọng lượng \(w_1, \ldots, w_N\). Để xác định một nhóm bò có đủ nhẹ để bè không bị chìm hay không, những chú bò cộng tất cả trọng lượng trong nhóm lại. Đáng tiếc là bò vốn nổi tiếng tính toán kém; nếu phép cộng trọng lượng của các chú bò trong một nhóm phát sinh bất kỳ lần nhớ nào (theo phép cộng thập phân thông thường), chúng sẽ bỏ cuộc và kết luận rằng nhóm đó hẳn quá nặng để dùng bè. Mọi nhóm có thể cộng các trọng lượng mà không phát sinh lần nhớ nào đều được coi là đủ nhẹ để lên bè.
Hãy giúp những chú bò xác định kích thước của nhóm lớn nhất mà chúng tin rằng có thể lên bè (tức là nhóm lớn nhất có thể cộng các trọng lượng mà không phát sinh lần nhớ nào).
Ví dụ 1
5
522
6
84
7311
193Có \(5\) chú bò với trọng lượng lần lượt là \(522\), \(6\), \(84\), \(7311\) và \(19\).
Ba trọng lượng \(522\), \(6\) và \(7311\) có thể được cộng lại mà không phát sinh lần nhớ nào:
522
6
+ 7311
------
7839
USACO 2011 December Contest, Bronze Division — Escaping the Farm
Tác giả đề: Brian Dean và Kalki Seksaria, 2011.