| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2012 - Large Banner | 100 (p) | 4.0s | 512M |
| 2 | USACO 2012 - Haybale Restacking | 100 (p) | 4.0s | 512M |
| 3 | USACO 2012 - Cows in a Skyscraper | 100 (p) | 4.0s | 512M |
Bessie đang trở về sau một chuyến đi dài ở nước ngoài tới đảo Guernsey, và Farmer John muốn treo một tấm biểu ngữ "Chào mừng về nhà" thật đẹp để đón cô. Cánh đồng của Farmer John có kích thước nguyên \(M \times N\) (\(1 \leq M, N \leq 100\,000\)), và ông đã dựng một cột tại mọi điểm có tọa độ nguyên trong cánh đồng (nếu ta gán một hệ tọa độ cho cánh đồng sao cho \((0,0)\) là góc dưới bên trái và \((M,N)\) là góc trên bên phải). Trong số \((M+1) \times (N+1)\) điểm này, Farmer John phải chọn hai điểm làm hai đầu của tấm biểu ngữ.
Vốn là người cầu toàn, Farmer John yêu cầu tấm biểu ngữ phải hoàn toàn thẳng. Điều này có nghĩa là với hai cột ông chọn, không được có bất kỳ cột nào khác nằm trên đoạn thẳng mà tấm biểu ngữ tạo thành giữa chúng. Ngoài ra, Farmer John muốn tấm biểu ngữ có độ dài ít nhất \(L\) và nhiều nhất \(H\) (\(1 \leq L \leq H \leq 150\,000\)). Farmer John cần bạn giúp tìm xem có bao nhiêu cách treo biểu ngữ. Tấm biểu ngữ có thể đảo chiều, nên việc hoán đổi hai đầu của nó vẫn được tính là cùng một cách treo. Vì con số này có thể rất lớn, Farmer John chỉ muốn biết kết quả modulo \(B\) (\(1 \leq B \leq 1\,000\,000\,000\)).
Xét ví dụ dưới đây với \(M=2\) và \(N=2\):
* * *
* * *
* * *
Farmer John muốn độ dài của tấm biểu ngữ nằm trong đoạn từ 1 đến 3, kể cả hai đầu. Mọi cách chọn cột đều thỏa mãn yêu cầu về độ dài này, nhưng lưu ý rằng không thể chọn tám cặp sau:
Do đó, tổng cộng có \(\binom{9}{2}-8=28\) cách chọn vị trí.
Dòng đầu tiên chứa năm số nguyên cách nhau bởi dấu cách: \(M\), \(N\), \(L\), \(H\) và \(B\).
In ra một số nguyên biểu thị số tấm biểu ngữ có thể treo (modulo \(B\)).
Ví dụ 1
2 2 1 3 10028USACO 2012 March Contest, Gold Division — Large Banner. Tác giả đề: Nathan Pinsker (2010).
Farmer John vừa đặt mua một lượng lớn kiện cỏ khô. Ông muốn sắp xếp chúng thành \(N\) đống (\(1 \leq N \leq 100\,000\)) đặt theo vòng tròn, trong đó đống \(i\) chứa \(B_i\) kiện cỏ. Không may, người lái xe tải giao cỏ đã không chú ý lắng nghe khi Farmer John cung cấp thông tin này và chỉ nhớ rằng phải để cỏ thành \(N\) đống xếp theo vòng tròn. Sau khi giao hàng, Farmer John nhận thấy đống \(i\) chứa \(A_i\) kiện cỏ. Dĩ nhiên, tổng các giá trị \(A_i\) bằng tổng các giá trị \(B_i\).
Farmer John muốn chuyển các kiện cỏ từ cách sắp xếp hiện tại (được mô tả bởi các giá trị \(A_i\)) sang cách sắp xếp đích mong muốn (được mô tả bởi các giá trị \(B_i\)). Để chuyển một kiện cỏ từ một đống sang một đống cách nó \(x\) bước quanh vòng tròn, ông phải tốn \(x\) đơn vị công sức. Hãy giúp ông tính lượng công sức ít nhất cần bỏ ra.
In ra lượng công sức nhỏ nhất mà Farmer John cần bỏ ra.
Ví dụ 1
4
7 1
3 4
9 2
1 1313Có 4 đống xếp quanh một vòng tròn. Ban đầu, các đống lần lượt chứa 7, 3, 9 và 1 kiện cỏ. Farmer John muốn di chuyển cỏ sao cho các đống lần lượt chứa 1, 4, 2 và 13 kiện.
Cần ít nhất 13 đơn vị công sức: chuyển 6 kiện từ đống 1 sang đống 4, chuyển 1 kiện từ đống 3 sang đống 2 và chuyển 6 kiện từ đống 3 sang đống 4.
USACO 2012 March Contest, Gold Division — Haybale Restacking. Tác giả đề: Brian Dean (2012).
Một sự thật ít người biết về Bessie và những người bạn là chúng rất thích thi leo cầu thang. Một sự thật được biết đến rộng rãi hơn là bò thực sự không thích đi xuống cầu thang. Vì vậy, sau khi đàn bò đua xong lên đỉnh tòa nhà chọc trời yêu thích, chúng gặp phải một vấn đề. Từ chối đi cầu thang xuống, đàn bò buộc phải dùng thang máy để trở về tầng trệt.
Thang máy có tải trọng tối đa là \(W\) pound (\(1 \le W \le 100\,000\,000\)), và con bò \(i\) nặng \(C_i\) pound (\(1 \le C_i \le W\)). Hãy giúp Bessie tìm cách đưa tất cả \(N\) con bò (\(1 \le N \le 18\)) xuống tầng trệt bằng số chuyến thang máy ít nhất. Tổng khối lượng của những con bò trong mỗi chuyến thang máy không được lớn hơn \(W\).
Ví dụ 1
4 10
5
6
3
73
2 1 3
1 2
1 4Có bốn con bò nặng lần lượt 5, 6, 3 và 7 pound. Thang máy có tải trọng tối đa là 10 pound.
Ta có thể cho con bò nặng 3 pound đi cùng thang máy với bất kỳ con bò nào khác, nhưng ba con bò còn lại quá nặng để có thể đi chung với nhau. Trong lời giải trên, chuyến thang máy thứ nhất gồm bò số 1 và số 3, chuyến thứ hai gồm bò số 2, còn chuyến thứ ba gồm bò số 4. Với dữ liệu vào này còn có một số lời giải khác.
USACO 2012 March Contest, Gold Division — Cows in a Skyscraper
Tác giả: Mark Gordon, Neal Wu, Fatih Gelgi, 2012.