| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2016 - Fence Painting | 100 (p) | 4.0s | 512M |
| 2 | USACO 2016 - Speeding Ticket | 100 (p) | 4.0s | 512M |
| 3 | USACO 2016 - Contaminated Milk | 100 (p) | 4.0s | 512M |
Nhiều mùa hè nóng nực và mùa đông lạnh giá đã khiến hàng rào của Farmer John xuống cấp, nên ông quyết định đã đến lúc sơn lại nó với sự giúp đỡ của cô bò yêu thích Bessie. Đáng tiếc là tuy Bessie thực sự sơn rất thành thạo, cô lại không giỏi hiểu những chỉ dẫn của Farmer John.
Nếu coi hàng rào là một trục số một chiều, Farmer John sơn đoạn từ \(x=a\) đến \(x=b\). Ví dụ, nếu \(a=3\) và \(b=5\) thì Farmer John sơn một đoạn dài 2. Do hiểu nhầm chỉ dẫn của Farmer John, Bessie sơn đoạn từ \(x=c\) đến \(x=d\); đoạn này có thể chồng lên một phần hoặc toàn bộ đoạn của Farmer John. Hãy xác định tổng chiều dài hàng rào hiện đã được phủ sơn.
Dòng đầu tiên chứa hai số nguyên \(a\) và \(b\), cách nhau bởi dấu cách (\(a<b\)).
Dòng thứ hai chứa hai số nguyên \(c\) và \(d\), cách nhau bởi dấu cách (\(c<d\)).
Các giá trị \(a\), \(b\), \(c\) và \(d\) đều nằm trong đoạn \(0\ldots100\).
In một dòng chứa tổng chiều dài hàng rào được phủ sơn.
Ví dụ 1
7 10
4 86Tổng cộng 6 đơn vị hàng rào được phủ sơn, từ \(x=4\) đến hết \(x=10\).
USACO 2015 December Contest, Bronze - Fence Painting: https://usaco.org/index.php?page=viewproblem2&cpid=567
Tác giả: Brian Dean.
Bessie, cô bò lúc nào cũng gây rắc rối, đã lấy trộm máy kéo của Farmer John rồi phóng đi trên đường!
Con đường dài đúng 100 dặm và Bessie lái hết chiều dài con đường trước khi cuối cùng bị một cảnh sát yêu cầu dừng xe. Viên cảnh sát phạt Bessie vì chạy quá tốc độ, sử dụng giấy phép đã hết hạn và điều khiển một phương tiện cơ giới trong khi là bò. Bessie thừa nhận rằng hai lỗi sau có lẽ là đúng, nhưng cô nghi ngờ liệu viên cảnh sát có đúng khi phạt lỗi chạy quá tốc độ hay không. Cô muốn tự mình xác định xem trong một phần hành trình, mình có thực sự lái nhanh hơn giới hạn tốc độ hay không.
Con đường được chia thành \(N\) đoạn. Mỗi đoạn được mô tả bởi một số nguyên dương là chiều dài tính bằng dặm và một số nguyên là giới hạn tốc độ trong đoạn \(1\ldots100\) dặm một giờ. Vì con đường dài 100 dặm nên tổng chiều dài của tất cả \(N\) đoạn bằng 100. Ví dụ, con đường có thể bắt đầu bằng một đoạn dài 45 dặm với giới hạn tốc độ 70, rồi kết thúc bằng một đoạn dài 55 dặm với giới hạn tốc độ 60.
Hành trình của Bessie cũng có thể được mô tả bằng \(M\) đoạn. Trong mỗi đoạn, cô đi một số nguyên dương dặm nhất định với một tốc độ nguyên nhất định. Ví dụ, cô có thể bắt đầu bằng việc đi 50 dặm với tốc độ 65, sau đó đi thêm 50 dặm với tốc độ 55. Tổng chiều dài của tất cả \(M\) đoạn bằng 100 dặm. Máy kéo của Farmer John có thể chạy nhanh nhất 100 dặm một giờ.
Với các thông tin trên, hãy xác định mức vượt quá giới hạn tốc độ lớn nhất của Bessie tại bất kỳ phần nào trong hành trình.
Dòng đầu tiên chứa \(N\) và \(M\), cách nhau bởi dấu cách.
\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả một đoạn đường: chiều dài và giới hạn tốc độ của đoạn đó.
\(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả một đoạn trong hành trình của Bessie: chiều dài đoạn và tốc độ mà Bessie đã lái.
In một dòng chứa mức vượt quá giới hạn tốc độ lớn nhất của Bessie tại bất kỳ phần nào trong hành trình. Nếu cô không bao giờ vượt quá giới hạn tốc độ, hãy in 0.
Ví dụ 1
3 3
40 75
50 35
10 45
40 76
20 30
40 405Trong ví dụ này, con đường gồm ba đoạn (40 dặm với giới hạn 75 dặm một giờ, tiếp theo là 50 dặm với giới hạn 35 dặm một giờ, rồi 10 dặm với giới hạn 45 dặm một giờ). Bessie lái xe theo ba đoạn (40 dặm với tốc độ 76 dặm một giờ, 20 dặm với tốc độ 30 dặm một giờ và 40 dặm với tốc độ 40 dặm một giờ). Trong đoạn đầu tiên, cô vượt giới hạn tốc độ một chút, nhưng đoạn cuối là lần vi phạm nghiêm trọng nhất: trong một phần của đoạn này, cô vượt giới hạn tốc độ 5 dặm một giờ. Vì vậy, đáp án đúng là 5.
USACO 2015 December Contest, Bronze - Speeding Ticket: https://usaco.org/index.php?page=viewproblem2&cpid=568
Tác giả: Austin Bannister và Brian Dean.
Farmer John, vốn nổi tiếng gần xa vì chất lượng sữa được sản xuất tại trang trại của mình, đang tổ chức một buổi thử sữa cho \(N\) người bạn thân nhất (\(1\le N\le50\)). Đáng tiếc là trong số \(M\) loại sữa có tại buổi tiệc (\(1\le M\le50\)), đúng một loại đã bị hỏng, nhưng Farmer John không biết đó là loại nào! Bất kỳ ai uống phải sữa hỏng sau đó sẽ bị ốm, có thể trong thời gian còn lại của buổi tiệc hoặc sau khi buổi tiệc kết thúc.
Bạn được cung cấp bản ghi của buổi tiệc — ai uống gì vào lúc nào, cũng như ai bị ốm vào lúc nào. Dựa vào thông tin này, bạn có thể suy ra những loại sữa nào có khả năng là loại bị hỏng. Dùng kết quả đó, hãy giúp Farmer John xác định số liều thuốc tối thiểu ông cần chuẩn bị để đảm bảo có thể chữa cho tất cả những người bị ốm, dù họ bị ốm trong hay sau buổi tiệc.
Dòng đầu tiên chứa các số nguyên \(N\), \(M\), \(D\) và \(S\).
\(D\) dòng tiếp theo (\(1\le D\le1000\)), mỗi dòng chứa ba số nguyên \(p,m,t\), cho biết người \(p\) đã uống loại sữa \(m\) tại thời điểm \(t\). Giá trị \(p\) nằm trong đoạn \(1\ldots N\), \(m\) nằm trong đoạn \(1\ldots M\) và \(t\) nằm trong đoạn \(1\ldots100\). Một người có thể uống cùng một loại sữa nhiều lần và cũng có thể uống nhiều loại sữa tại cùng một thời điểm.
\(S\) dòng tiếp theo (\(1\le S\le N\)), mỗi dòng chứa hai số nguyên \(p,t\), cho biết người \(p\) bị ốm tại thời điểm \(t\). Giá trị \(p\) nằm trong đoạn \(1\ldots N\) và \(t\) nằm trong đoạn \(1\ldots100\). Mỗi người bị ốm nhiều nhất một lần, và họ chỉ bị ốm vì đã uống sữa hỏng tại một thời điểm sớm hơn một cách nghiêm ngặt.
In một số nguyên duy nhất là số liều thuốc tối thiểu Farmer John cần chuẩn bị để đảm bảo có đủ liều chữa cho tất cả những người bị ốm, cả trong và sau buổi tiệc.
Ví dụ 1
3 4 7 2
1 1 1
1 4 1
1 3 4
1 2 2
3 1 3
2 1 5
2 2 7
1 3
2 83Có 3 người và 4 loại sữa. Người 1 bị ốm tại thời điểm 3 và người 2 bị ốm tại thời điểm 8. Người 3 không bị ốm tại buổi tiệc, mặc dù ta vẫn cần xét khả năng người này có thể bị ốm sau đó, khi buổi tiệc đã kết thúc. Hãy lần lượt xét từng loại sữa để xem loại nào có thể bị nhiễm bẩn; ta biết một loại sữa có khả năng bị hỏng nếu tất cả những người đã bị ốm đều uống loại sữa đó trước khi bị ốm.
Sữa 1: Cả hai người bị ốm (1 và 2) đều uống loại sữa này trước khi bị ốm, nên đây có thể là sữa hỏng. Nếu đúng như vậy, người 3 cũng đã uống nó, nên tổng cộng 3 người sẽ bị ốm (người 3 sẽ bị ốm sau buổi tiệc).
Sữa 2: Cả hai người bị ốm đều uống loại sữa này trước khi bị ốm, nên đây cũng có thể là sữa hỏng. Không ai khác uống loại sữa này, vì vậy trong trường hợp xấu nhất sẽ có tổng cộng 2 người bị ốm nếu đây là sữa hỏng.
Sữa 3: Đây không thể là sữa hỏng vì người 1 không uống nó trước khi bị ốm — người 1 uống nó tại thời điểm 4 nhưng bị ốm tại thời điểm 3. Để sữa 3 có thể là nguyên nhân khiến người 1 bị ốm, người 1 phải uống loại sữa này muộn nhất tại thời điểm 2.
Sữa 4: Đây không thể là sữa hỏng vì người 2 không uống nó nhưng vẫn bị ốm.
Vì vậy, đáp án là Farmer John phải chuẩn bị 3 liều thuốc, bởi nếu sữa 1 bị hỏng thì tổng cộng 3 người sẽ cần được chữa trị.
USACO 2015 December Contest, Bronze - Contaminated Milk: https://usaco.org/index.php?page=viewproblem2&cpid=569
Tác giả: Austin Anderson và Brian Dean.