| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2020 - Social Distancing | 100 (p) | 4.0s | 512M |
| 2 | USACO 2020 - Cereal | 100 (p) | 4.0s | 512M |
| 3 | USACO 2020 - The Moo Particle | 100 (p) | 4.0s | 512M |
Nông dân John lo lắng cho sức khỏe của những con bò sau khi căn bệnh truyền nhiễm rất mạnh ở bò COWVID-19 bùng phát.
Để hạn chế sự lây truyền của căn bệnh, \(N\) con bò của Nông dân John (\(2 \leq N \leq 10^5\)) đã quyết định thực hiện "giãn cách xã hội" và phân tán khắp trang trại. Trang trại có dạng một trục số một chiều, với \(M\) đoạn đôi một rời nhau (\(1 \leq M \leq 10^5\)) mà trên đó có cỏ để gặm. Những con bò muốn đứng tại các điểm nguyên phân biệt có cỏ, sao cho tối đa hóa giá trị \(D\), trong đó \(D\) là khoảng cách giữa cặp bò gần nhau nhất. Hãy giúp những con bò xác định giá trị \(D\) lớn nhất có thể.
Tệp socdist.in:
Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(M\) dòng tiếp theo mô tả một đoạn bằng hai số nguyên \(a\) và \(b\), trong đó \(0 \leq a \leq b \leq 10^{18}\). Không có hai đoạn nào giao nhau hoặc tiếp xúc nhau tại đầu mút. Một con bò đứng tại đầu mút của một đoạn vẫn được tính là đứng trên cỏ.
Tệp socdist.out:
In ra giá trị \(D\) lớn nhất có thể sao cho mọi cặp bò đều cách nhau ít nhất \(D\) đơn vị. Đề bài đảm bảo tồn tại một cách xếp với \(D>0\).
Ví dụ 1
5 3
0 2
4 7
9 92Một cách để đạt được \(D=2\) là đặt các con bò tại các vị trí \(0\), \(2\), \(4\), \(6\) và \(9\).
USACO 2020 US Open Contest, Silver — Social Distancing
Tác giả bài: Brian Dean.
Không gì khiến những con bò của Nông dân John thích thú hơn ngũ cốc ăn sáng! Thật vậy, chúng háu ăn đến mức mỗi con sẽ ăn hết cả một hộp ngũ cốc trong một bữa.
Gần đây, trang trại nhận được một lô hàng gồm \(M\) loại ngũ cốc khác nhau (\(1 \leq M \leq 10^5\)). Thật không may, mỗi loại ngũ cốc chỉ có đúng một hộp! Mỗi con trong số \(N\) con bò (\(1 \leq N \leq 10^5\)) có một loại ngũ cốc yêu thích nhất và một loại yêu thích thứ hai. Khi được lựa chọn trong số các loại ngũ cốc, một con bò thực hiện quy trình sau:
Những con bò đã xếp hàng để nhận ngũ cốc. Với mỗi \(0 \leq i \leq N-1\), hãy xác định có bao nhiêu con bò sẽ lấy được một hộp ngũ cốc nếu Nông dân John loại \(i\) con bò đầu tiên khỏi hàng.
Tệp cereal.in:
Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) cách nhau bởi dấu cách.
Với mỗi \(1 \leq i \leq N\), dòng thứ \(i\) tiếp theo chứa hai số nguyên \(f_i\) và \(s_i\) cách nhau bởi dấu cách (\(1 \leq f_i,s_i \leq M\) và \(f_i \neq s_i\)), lần lượt biểu thị loại ngũ cốc yêu thích nhất và yêu thích thứ hai của con bò thứ \(i\) trong hàng.
Tệp cereal.out:
Với mỗi \(0 \leq i \leq N-1\), in một dòng chứa đáp án cho \(i\).
Ví dụ 1
4 2
1 2
1 2
1 2
1 22
2
2
1Nếu còn lại ít nhất hai con bò thì có đúng hai con lấy được một hộp ngũ cốc.
USACO 2020 US Open Contest, Silver — Cereal
Tác giả bài: Dhruv Rohatgi.
Trong thời gian được cách ly để bảo vệ khỏi đợt bùng phát COWVID-19, những con bò của Nông dân John đã nghĩ ra một cách mới để bớt buồn chán: nghiên cứu vật lý nâng cao! Thật vậy, chúng thậm chí còn khám phá được một hạt hạ nguyên tử mới và đặt tên cho nó là "hạt moo".
Hiện tại, những con bò đang tiến hành một thí nghiệm với \(N\) hạt moo (\(1 \leq N \leq 10^5\)). Hạt \(i\) có một "spin" được mô tả bởi hai số nguyên \(x_i\) và \(y_i\) trong phạm vi \(-10^9 \ldots 10^9\), kể cả hai đầu mút. Đôi khi hai hạt moo tương tác với nhau. Điều này chỉ có thể xảy ra với hai hạt có spin \((x_i, y_i)\) và \((x_j, y_j)\) nếu \(x_i \leq x_j\) và \(y_i \leq y_j\). Trong những điều kiện này, có khả năng đúng một trong hai hạt biến mất (và hạt còn lại không bị ảnh hưởng). Tại mỗi thời điểm, nhiều nhất một tương tác sẽ xảy ra.
Những con bò muốn biết số hạt moo nhỏ nhất có thể còn lại sau một chuỗi tương tác tùy ý.
Tệp moop.in:
Dòng đầu tiên chứa một số nguyên \(N\), là số hạt moo ban đầu. 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, biểu thị spin của một hạt. Mỗi hạt có một spin riêng biệt.
Tệp moop.out:
In một số nguyên duy nhất, là số hạt moo nhỏ nhất có thể còn lại sau một chuỗi tương tác tùy ý.
Ví dụ 1
4
1 0
0 1
-1 0
0 -11Một chuỗi tương tác có thể xảy ra là:
Chỉ còn lại hạt 2.
Ví dụ 2
3
0 0
1 1
-1 32Hạt 3 không thể tương tác với một trong hai hạt còn lại, nên nó bắt buộc phải còn lại. Ít nhất một trong hai hạt 1 và 2 cũng phải còn lại.
USACO 2020 US Open Contest, Silver — The Moo Particle
Tác giả bài: Dhruv Rohatgi.