| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2018 - Lifeguards | 100 (p) | 4.0s | 512M |
| 2 | USACO 2018 - Cow at Large | 100 (p) | 4.0s | 512M |
| 3 | USACO 2018 - Sprinklers | 100 (p) | 4.0s | 512M |
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 \(0\) đến thời điểm \(10^9\), 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 \(K\) nhân viên cứu hộ. Biết rằng ông phải sa thải đúng \(K\) 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\) và \(K\) (\(K \leq N \leq 100{,}000\), \(1 \leq K \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 10^9\), 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 đúng \(K\) nhân viên cứu hộ.
Ví dụ 1
3 2
1 8
7 15
2 1412Trong ví dụ này, bác nông dân John nên sa thải các nhân viên cứu hộ trực trong những khoảng \(1 \ldots 8\) và \(7 \ldots 15\).
USACO 2018 January Contest, Platinum — Lifeguards
Tác giả bài toán: Brian Dean.
Cuối cùng cũng bị dồn vào đường cùng, Bessie đã lẩn trốn trong một trang trại hẻo lánh. Trang trại gồm \(N\) chuồng bò (\(2 \leq N \leq 7 \cdot 10^4\)) và \(N-1\) đường hầm hai chiều nối các chuồng, sao cho giữa mọi cặp chuồng đều có một đường đi duy nhất. Mỗi chuồng có đúng một đường hầm nối với nó đều là một lối thoát. Khi trời sáng, Bessie sẽ xuất hiện tại một chuồng nào đó và cố gắng đi đến một lối thoát.
Nhưng ngay khi Bessie xuất hiện tại một chuồng nào đó, lực lượng hành pháp sẽ có thể xác định chính xác vị trí của cô. Khi đó, một số nông dân sẽ bắt đầu từ các chuồng là lối thoát và cố gắng bắt Bessie. Những người nông dân di chuyển với cùng tốc độ như Bessie (vì vậy trong mỗi bước thời gian, mỗi nông dân có thể đi từ một chuồng sang một chuồng kề nó). Những người nông dân luôn biết Bessie ở đâu, và Bessie cũng luôn biết họ ở đâu. Những người nông dân bắt được Bessie nếu tại bất kỳ thời điểm nào có một nông dân ở cùng chuồng với Bessie hoặc đang đi qua cùng một đường hầm với Bessie. Ngược lại, Bessie trốn thoát nếu thời điểm cô đến được một chuồng là lối thoát sớm hơn nghiêm ngặt so với thời điểm bất kỳ nông dân nào bắt được cô.
Bessie không chắc mình nên xuất hiện tại chuồng nào. Với mỗi chuồng trong số \(N\) chuồng, hãy giúp cô xác định số nông dân ít nhất cần có để bắt được cô nếu cô xuất hiện tại đó, giả sử những người nông dân phân bố tối ưu giữa các chuồng là lối thoát.
Lưu ý rằng giới hạn thời gian của bài này lớn hơn mặc định một chút: \(4\) giây đối với C/C++/Pascal và \(8\) giây đối với Java/Python.
Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên, mỗi số thuộc khoảng \(1 \ldots N\), mô tả một đường hầm nối hai chuồng.
In ra \(N\) dòng, trong đó dòng thứ \(i\) cho biết số nông dân ít nhất cần có để bắt Bessie nếu cô xuất hiện tại chuồng thứ \(i\).
Ví dụ 1
7
1 2
1 3
3 4
3 5
4 6
5 73
1
3
3
3
1
1USACO 2018 January Contest, Platinum — Cow at Large
Tác giả bài toán: Dhruv Rohatgi.
Bác nông dân John có một cánh đồng lớn và đang cân nhắc trồng ngô ngọt trên một phần cánh đồng. Sau khi khảo sát, ông nhận thấy cánh đồng là một hình vuông kích thước \((N-1) \times (N-1)\). Góc tây nam có tọa độ \((0,0)\) và góc đông bắc có tọa độ \((N-1,N-1)\).
Tại một số tọa độ nguyên có các vòi phun hai đầu, mỗi vòi phun cả nước lẫn phân bón. Một vòi phun hai đầu tại tọa độ \((i,j)\) phun nước lên phần cánh đồng ở phía bắc và phía đông của nó, đồng thời phun phân bón lên phần cánh đồng ở phía nam và phía tây của nó. Cụ thể, nó tưới nước cho mọi tọa độ thực \((x,y)\) thỏa mãn \(N \geq x \geq i\) và \(N \geq y \geq j\), đồng thời bón phân cho mọi tọa độ thực \((x,y)\) thỏa mãn \(0 \leq x \leq i\) và \(0 \leq y \leq j\).
Bác nông dân John muốn trồng ngô ngọt trong một hình chữ nhật nào đó trên cánh đồng, có các cạnh song song với các trục tọa độ và tọa độ các đỉnh đều là số nguyên. Tuy nhiên, để ngô ngọt phát triển, mọi điểm trong hình chữ nhật đều phải vừa được tưới nước vừa được bón phân bởi các vòi phun hai đầu. Và tất nhiên, hình chữ nhật phải có diện tích dương, nếu không bác nông dân John sẽ không thể trồng được cây ngô nào trong đó!
Hãy giúp bác nông dân John xác định số hình chữ nhật có diện tích dương mà ông có thể trồng ngô ngọt. Vì số này có thể rất lớn, hãy in ra phần dư của nó theo \(10^9+7\).
Dòng đầu tiên chứa một số nguyên \(N\), kích thước của cánh đồng (\(1 \leq N \leq 10^5\)).
Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên cách nhau bởi dấu cách. Nếu hai số đó là \(i\) và \(j\), với \(0 \leq i,j \leq N-1\), chúng biểu thị một vòi phun đặt tại \((i,j)\).
Dữ liệu đảm bảo có đúng một vòi phun trong mỗi cột và đúng một vòi phun trong mỗi hàng. Nói cách khác, không có hai vòi phun nào có cùng tọa độ \(x\), và không có hai vòi phun nào có cùng tọa độ \(y\).
In ra một số nguyên duy nhất: số hình chữ nhật có diện tích dương được tưới nước và bón phân hoàn toàn, lấy phần dư theo \(10^9+7\).
Ví dụ 1
5
0 4
1 1
2 2
3 0
4 321USACO 2018 January Contest, Platinum — Sprinklers
Tác giả bài toán: Dhruv Rohatgi.