| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2018 - Blocked Billboard II | 100 (p) | 4.0s | 512M |
| 2 | USACO 2018 - Lifeguards | 100 (p) | 4.0s | 512M |
| 3 | USACO 2018 - Out of Place | 100 (p) | 4.0s | 512M |
Bessie từng có một khung cảnh thật đẹp nhìn từ chuồng bò của mình, qua con đường về phía hai tấm biển quảng cáo thức ăn cho bò trông rất ngon. Không may, một trong hai tấm biển gần đây đã được thay nội dung thành quảng cáo cho “Máy cắt cỏ của bác nông dân Larry”. Bessie không thích máy cắt cỏ, bởi theo những gì cô biết, mục đích duy nhất của chúng là cắt ngắn đám cỏ thơm ngon trong cánh đồng của cô (nếu bạn chưa nhận ra, phần lớn suy nghĩ của Bessie đều xoay quanh thức ăn).
May mắn thay, tấm biển quảng cáo thức ăn cho bò còn lại nằm phía trước tấm biển quảng cáo máy cắt cỏ và có thể che khuất nó.
Quyết tâm loại bỏ hoàn toàn tấm biển quảng cáo máy cắt cỏ đáng ghét khỏi tầm mắt, Bessie nghĩ ra một kế hoạch mạo hiểm. Cô định lấy trộm một tấm bạt hình chữ nhật lớn trong chuồng bò rồi lẻn ra ngoài vào đêm khuya để che phần còn lại của tấm biển quảng cáo máy cắt cỏ, sao cho cô không còn nhìn thấy bất kỳ phần nào của nó.
Cho vị trí của hai tấm biển quảng cáo, hãy giúp Bessie tính diện tích nhỏ nhất của tấm bạt mà cô cần. Vì trong chuồng chỉ có các tấm bạt hình chữ nhật, Bessie nhận thấy cô có thể cần một tấm bạt có diện tích lớn hơn một chút so với phần lộ ra của tấm biển quảng cáo máy cắt cỏ, như trong ví dụ bên dưới. Chỉ được đặt tấm bạt sao cho các cạnh của nó song song với các cạnh của hai tấm biển (nghĩa là không được đặt “nghiêng”).
Dòng đầu tiên chứa bốn số nguyên cách nhau bởi dấu cách: \(x_1\) \(y_1\) \(x_2\) \(y_2\), trong đó \((x_1, y_1)\) và \((x_2, y_2)\) lần lượt là tọa độ góc dưới bên trái và góc trên bên phải của tấm biển quảng cáo máy cắt cỏ trong trường nhìn hai chiều của Bessie. Dòng tiếp theo chứa thêm bốn số nguyên, tương tự mô tả góc dưới bên trái và góc trên bên phải của tấm biển quảng cáo thức ăn cho bò. Tấm biển quảng cáo thức ăn cho bò có thể che toàn bộ, một phần hoặc không che phần nào của tấm biển quảng cáo máy cắt cỏ. Mọi tọa độ đều nằm trong khoảng từ \(-1000\) đến \(+1000\).
In ra diện tích nhỏ nhất của tấm bạt Bessie cần dùng để che một phần tấm biển quảng cáo máy cắt cỏ sao cho nó bị che khuất hoàn toàn.
Ví dụ 1
2 1 7 4
5 -1 10 315Tấm biển quảng cáo thức ăn cho bò che góc dưới bên phải của tấm biển quảng cáo máy cắt cỏ, nhưng điều này thực ra không giúp ích gì, vì Bessie vẫn cần dùng một tấm bạt có diện tích lớn bằng diện tích toàn bộ tấm biển quảng cáo máy cắt cỏ.
USACO 2018 January Contest, Bronze — Blocked Billboard II
Tác giả bài toán: Brian Dean.
Bác nông dân John đã mở một hồ bơi cho đàn bò vì cho rằng nơi này sẽ giúp chúng thư giãn và sản xuất nhiều sữa hơn.
Để đảm bảo an toàn, ông thuê \(N\) cô bò làm nhân viên cứu hộ, mỗi cô có một ca trực bao phủ một khoảng thời gian liên tục trong ngày. Để đơn giản, mỗi ngày hồ bơi mở cửa từ thời điểm \(t=0\) đến thời điểm \(t=1000\), nên mỗi ca trực có thể được mô tả bằng hai số nguyên cho biết thời điểm một cô bò bắt đầu và kết thúc ca trực. Ví dụ, một nhân viên cứu hộ bắt đầu lúc \(t=4\) và kết thúc lúc \(t=7\) sẽ trực trong ba đơn vị thời gian (lưu ý rằng hai đầu mút là các “điểm” thời gian).
Không may, bác nông dân John đã thuê nhiều hơn khả năng chi trả đúng một nhân viên cứu hộ. Biết rằng ông phải sa thải đúng một nhân viên cứu hộ, thời lượng lớn nhất vẫn có thể được bao phủ bởi các ca trực của những nhân viên còn lại là bao nhiêu? Một khoảng thời gian được coi là có người trực nếu có ít nhất một nhân viên cứu hộ hiện diện.
Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 100\)). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một nhân viên cứu hộ bằng hai số nguyên trong khoảng \(0 \ldots 1000\), cho biết thời điểm bắt đầu và kết thúc ca trực của cô. Tất cả các đầu mút này đôi một khác nhau. Ca trực của những nhân viên cứu hộ khác nhau có thể chồng lấn.
In ra một số duy nhất là thời lượng lớn nhất vẫn có thể được bao phủ nếu bác nông dân John sa thải một nhân viên cứu hộ.
Ví dụ 1
3
5 9
1 4
3 77USACO 2018 January Contest, Bronze — Lifeguards
Tác giả bài toán: Brian Dean.
Với đầy tham vọng, bác nông dân John dự định thử làm một việc dường như chẳng bao giờ diễn ra suôn sẻ: ông muốn chụp ảnh toàn bộ đàn bò của mình.
Để bức ảnh trông đẹp mắt, ông muốn các cô bò xếp thành một hàng từ thấp nhất đến cao nhất. Không may, ngay sau khi ông xếp đàn bò theo thứ tự này, cô bò Bessie vốn luôn gây rắc rối lại bước ra khỏi hàng rồi chen vào một vị trí khác trong hàng!
Bác nông dân John muốn hoán đổi từng cặp bò để cả đàn một lần nữa được xếp đúng thứ tự. Hãy giúp ông xác định số lần hoán đổi ít nhất giữa các cặp bò để đạt được mục tiêu này.
Dòng đầu tiên chứa \(N\) (\(2 \leq N \leq 100\)). Mỗi dòng trong \(N\) dòng tiếp theo mô tả chiều cao của một cô bò theo thứ tự trong hàng sau khi Bessie di chuyển. Chiều cao của mỗi cô bò là một số nguyên trong khoảng \(1 \ldots 1{,}000{,}000\). Nhiều cô bò có thể có cùng chiều cao.
In ra số lần ít nhất bác nông dân John cần hoán đổi các cặp bò để đưa đàn bò về đúng thứ tự. Các lần hoán đổi không nhất thiết phải thực hiện giữa hai cô bò đứng kề nhau trong hàng.
Ví dụ 1
6
2
4
7
7
9
33Trong ví dụ này, Bessie rõ ràng là cô bò có chiều cao \(3\). Bác nông dân John đưa đàn bò trở lại thứ tự đã sắp xếp bằng ba lần hoán đổi như sau:
2 4 7 7 9 3 - Hàng ban đầu
2 4 7 7 3 9 - Hoán đổi hai cô bò cuối cùng
2 4 3 7 7 9 - Hoán đổi cô bò 7 đầu tiên với cô bò 3
2 3 4 7 7 9 - Hoán đổi cô bò 4 với cô bò 3
USACO 2018 January Contest, Bronze — Out of Place
Tác giả bài toán: Brian Dean.