| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2015 - Bessie Goes Moo | 100 (p) | 4.0s | 512M |
| 2 | USACO 2015 - Trapped in the Haybales (Silver) | 100 (p) | 4.0s | 512M |
| 3 | USACO 2015 - Bessie's Birthday Buffet | 100 (p) | 4.0s | 512M |
Farmer John và cô bò Bessie thích trao đổi các câu đố toán học vào thời gian rảnh. Câu đố gần nhất FJ đưa cho Bessie khá khó và cô không giải được. Giờ đây, cô muốn trả đũa FJ bằng cách đưa cho ông một câu đố hóc búa.
Bessie đưa cho FJ biểu thức \((B+E+S+S+I+E)(G+O+E+S)(M+O+O)\), chứa bảy biến \(B,E,S,I,G,O,M\) (ký tự "\(O\)" là một biến, không phải chữ số không). Với mỗi biến, cô đưa cho FJ một danh sách gồm không quá 500 giá trị nguyên mà biến đó có thể nhận. Cô yêu cầu FJ đếm số cách khác nhau để gán giá trị cho các biến sao cho toàn bộ biểu thức có giá trị là một bội của 7.
Lưu ý rằng đáp án của bài toán này có thể quá lớn để lưu trong một số nguyên 32 bit, vì vậy bạn có thể sẽ cần dùng số nguyên 64 bit (chẳng hạn kiểu long long trong C hoặc C++).
Dòng đầu tiên chứa số nguyên \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa một biến và một giá trị mà biến đó có thể nhận. Mỗi biến xuất hiện trong danh sách ít nhất một lần và nhiều nhất 500 lần. Với cùng một biến, không có giá trị khả dĩ nào được liệt kê quá một lần. Mọi giá trị khả dĩ đều nằm trong khoảng từ \(-10^5\) đến \(10^5\).
In một số nguyên duy nhất: số cách FJ có thể gán giá trị cho các biến sao cho biểu thức trên có giá trị là một bội của 7.
Ví dụ 1
10
B 2
E 5
S 7
I 10
O 16
M 19
B 3
G 1
I 9
M 22Hai cách gán có thể là:
(B,E,S,I,G,O,M) = (2, 5, 7, 9, 1, 16, 19) -> 51,765
= (2, 5, 7, 9, 1, 16, 2 ) -> 34,510
USACO 2015 US Open, Silver — Bessie Goes Moo. Tác giả đề: Brian Dean, 2015.
Farmer John vừa nhận một lô gồm \(N\) kiện cỏ khô lớn (\(1 \le N \le 100{,}000\)) và đặt chúng tại nhiều vị trí khác nhau dọc theo con đường nối chuồng với nhà của ông. Mỗi kiện cỏ \(j\) có kích thước \(S_j\) và một vị trí phân biệt \(P_j\) cho biết nơi nó nằm trên con đường một chiều. Cô bò Bessie hiện đang ở vị trí \(B\), nơi không có kiện cỏ nào.
Bessie có thể tự do di chuyển dọc theo đường, kể cả đi tới đúng vị trí của một kiện cỏ, nhưng cô không thể đi xuyên qua vị trí này. Tuy nhiên, nếu chạy theo cùng một hướng trên quãng đường dài \(D\), cô sẽ đạt đủ tốc độ để phá xuyên qua và loại bỏ vĩnh viễn bất kỳ kiện cỏ nào có kích thước nhỏ hơn nghiêm ngặt \(D\). Dĩ nhiên, sau khi làm vậy, cô có thể có thêm không gian để lấy đà lao vào các kiện cỏ khác và tiếp tục phá chúng.
FJ hiện đang sơn lại nhà và chuồng, nên ông muốn chắc chắn rằng Bessie không thể đến được nơi nào trong hai nơi đó (bò và sơn còn ướt không phải là một sự kết hợp tốt!). Vì vậy, FJ muốn đảm bảo Bessie không bao giờ phá xuyên qua kiện cỏ ngoài cùng bên trái hoặc ngoài cùng bên phải, để cô vẫn bị giữ lại giữa các kiện cỏ. FJ có thể thêm cỏ vào đúng một kiện cỏ do ông chọn để giúp giữ Bessie mắc kẹt. Hãy giúp ông xác định lượng cỏ ít nhất cần thêm vào một kiện cỏ nào đó để đảm bảo Bessie vẫn bị mắc kẹt.
Dòng đầu tiên chứa \(N\) và vị trí ban đầu \(B\) của Bessie. Mỗi dòng trong \(N\) dòng tiếp theo mô tả một kiện cỏ, gồm hai số nguyên cho biết kích thước và vị trí của kiện cỏ. Mọi kích thước và vị trí đều nằm trong khoảng \(1 \ldots 10^9\).
In một số nguyên duy nhất: lượng cỏ ít nhất FJ cần thêm để ngăn Bessie thoát ra. In -1 nếu không thể ngăn Bessie thoát.
Ví dụ 1
5 7
8 1
1 4
3 8
12 15
20 204USACO 2015 US Open, Silver — Trapped in the Haybales (Silver). Tác giả đề: Brian Dean, 2015.
Nhân dịp sinh nhật cô bò Bessie, Farmer John cho cô toàn quyền ăn cỏ trên một trong những cánh đồng tốt nhất của ông.
Cánh đồng có \(N\) bãi cỏ (\(1 \le N \le 1000\)), được đánh số thuận tiện từ \(1 \ldots N\), và mỗi bãi có một giá trị chất lượng phân biệt. Nếu Bessie ăn cỏ có chất lượng \(Q\), cô nhận được \(Q\) đơn vị năng lượng. Mỗi bãi cỏ được nối với không quá 10 bãi lân cận bằng các đường đi hai chiều, và Bessie tốn \(E\) đơn vị năng lượng để di chuyển giữa hai bãi kề nhau (\(1 \le E \le 1{,}000{,}000\)). Bessie có thể chọn bắt đầu gặm cỏ tại bất kỳ bãi nào và muốn dừng lại khi đã tích lũy được lượng năng lượng lớn nhất.
Không may, Bessie là một cô bò kén chọn: sau khi ăn cỏ có một mức chất lượng nhất định, cô sẽ không bao giờ ăn cỏ có chất lượng bằng hoặc thấp hơn mức đó nữa! Cô vẫn sẵn lòng đi qua các bãi mà không ăn cỏ ở đó; thực tế, cô có thể thấy việc đi qua một bãi cỏ chất lượng cao mà không ăn, rồi quay lại sau để thưởng thức, là có lợi.
Hãy xác định lượng năng lượng lớn nhất Bessie có thể tích lũy.
Dòng đầu tiên chứa \(N\) và \(E\). Mỗi dòng trong \(N\) dòng còn lại mô tả một bãi cỏ. Dòng đó chứa hai số nguyên \(Q\) và \(D\), lần lượt cho biết chất lượng của bãi cỏ (nằm trong khoảng \(1 \ldots 1{,}000{,}000\)) và số bãi lân cận của nó. \(D\) số còn lại trên dòng cho biết các bãi lân cận.
In lượng năng lượng lớn nhất Bessie có thể tích lũy.
Ví dụ 1
5 2
4 1 2
1 3 1 3 4
6 2 2 5
5 2 2 5
2 2 3 47Bessie bắt đầu tại bãi 4 và nhận 5 đơn vị năng lượng từ cỏ ở đó. Sau đó, cô đi theo đường nối đến bãi 5 và mất 2 đơn vị năng lượng khi di chuyển. Cô không ăn cỏ có chất lượng thấp hơn tại bãi 5 rồi đi đến bãi 3, tiếp tục mất 2 đơn vị năng lượng. Cuối cùng, cô ăn cỏ tại bãi 3 và nhận 6 đơn vị năng lượng, đạt tổng cộng 7 đơn vị năng lượng.
Lưu ý rằng trường hợp mẫu trên khác với bộ kiểm thử số 1 khi bạn nộp bài.
USACO 2015 US Open, Silver — Bessie's Birthday Buffet. Tác giả đề: Austin Anderson và Brian Dean, 2015.