| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2020 - Social Distancing I | 100 (p) | 4.0s | 512M |
| 2 | USACO 2020 - Social Distancing II | 100 (p) | 4.0s | 512M |
| 3 | USACO 2020 - Cowntact Tracing | 100 (p) | 4.0s | 512M |
Một căn bệnh mới khủng khiếp, COWVID-19, đã bắt đầu lây lan giữa các đàn bò trên toàn thế giới. Nông dân John đang cố gắng thực hiện nhiều biện pháp phòng ngừa nhất có thể để bảo vệ đàn bò của mình khỏi bị lây nhiễm.
Chuồng của Nông dân John là một tòa nhà dài và hẹp, gồm \(N\) ô chuồng xếp thành một hàng (\(2 \leq N \leq 10^5\)). Hiện tại, một số ô chuồng có bò ở, còn một số ô đang trống. Sau khi biết được tầm quan trọng của việc "giãn cách xã hội", Nông dân John muốn tối đa hóa \(D\), trong đó \(D\) là khoảng cách giữa hai ô chuồng có bò gần nhau nhất. Ví dụ, nếu ô chuồng 3 và ô chuồng 8 là hai ô có bò gần nhau nhất thì \(D = 5\).
Gần đây, hai con bò mới đã gia nhập đàn bò của Nông dân John, và ông cần quyết định xếp chúng vào những ô chuồng nào vốn đang trống. Hãy xác định cách xếp hai con bò mới sao cho giá trị \(D\) thu được vẫn lớn nhất có thể. Nông dân John không thể di chuyển bất kỳ con bò nào đang có sẵn; ông chỉ muốn xếp ô chuồng cho hai con bò mới.
Tệp socdist1.in:
Dòng đầu tiên chứa \(N\). Dòng tiếp theo chứa một xâu độ dài \(N\) gồm các ký tự 0 và 1, mô tả dãy ô chuồng trong chuồng bò. Ký tự 0 biểu thị ô chuồng trống và ký tự 1 biểu thị ô chuồng có bò. Xâu có ít nhất hai ký tự 0, vì vậy có đủ chỗ cho ít nhất hai con bò mới.
Tệp socdist1.out:
In ra giá trị \(D\) lớn nhất (khoảng cách nhỏ nhất giữa hai ô chuồng có bò) mà Nông dân John có thể đạt được sau khi thêm hai con bò mới theo cách tối ưu.
Ví dụ 1
14
100010010000102Trong ví dụ này, Nông dân John có thể thêm bò để xâu biểu diễn trạng thái các ô chuồng trở thành 10x010010x0010, trong đó các ký tự x biểu thị hai con bò mới. Khi đó \(D = 2\). Không thể thêm hai con bò mới theo cách nào để đạt được giá trị \(D\) lớn hơn.
USACO 2020 US Open Contest, Bronze — Social Distancing I
Tác giả bài: Brian Dean.
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.
Bất chấp nỗ lực hết sức để \(N\) con bò của mình (\(1 \leq N \leq 1000\)) thực hiện "giãn cách xã hội", thật không may là nhiều con vẫn mắc bệnh. Những con bò được đánh số thuận tiện từ \(1 \ldots N\) và mỗi con đứng tại một điểm riêng biệt dọc theo một con đường dài (về cơ bản là một trục số một chiều), trong đó bò \(i\) đứng tại vị trí \(x_i\). Nông dân John biết rằng tồn tại một bán kính \(R\) sao cho bất kỳ con bò nào đứng cách một con bò nhiễm bệnh không quá \(R\) đơn vị cũng sẽ bị lây nhiễm (sau đó lại truyền bệnh cho những con bò khác cách nó không quá \(R\) đơn vị, và cứ tiếp tục như vậy).
Đáng tiếc là Nông dân John không biết chính xác \(R\). Tuy nhiên, ông biết những con bò nào đã bị nhiễm bệnh. Với dữ liệu này, hãy xác định số bò ít nhất có thể đã bị nhiễm bệnh từ ban đầu.
Tệp socdist2.in:
Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một con bò bằng hai số nguyên \(x\) và \(s\), trong đó \(x\) là vị trí của con bò (\(0 \leq x \leq 10^6\)), còn \(s\) bằng 0 nếu bò khỏe mạnh và bằng 1 nếu bò bị bệnh. Có ít nhất một con bò bị bệnh, và tất cả những con bò có khả năng bị lây bệnh do bệnh lan truyền thì giờ đây đều đã bị bệnh.
Tệp socdist2.out:
In ra số bò ít nhất có thể đã bị bệnh từ ban đầu, trước khi bệnh bắt đầu lan truyền.
Tất cả các test tuân theo các ràng buộc đã nêu.
Ví dụ 1
6
7 1
1 1
15 1
3 1
10 0
6 13Trong ví dụ này, ta biết \(R < 3\), vì nếu không thì con bò ở vị trí 7 đã lây bệnh cho con bò ở vị trí 10. Do đó, phải có ít nhất 3 con bò bị nhiễm bệnh từ đầu: một trong hai con bò ở vị trí 1 và 3, một trong hai con bò ở vị trí 6 và 7, và con bò ở vị trí 15.
USACO 2020 US Open Contest, Bronze — Social Distancing II
Tác giả bài: Brian Dean.
Nông dân John lo lắng cho sức khỏe của những con bò (như mọi khi, chúng được đánh số thuận tiện từ \(1 \ldots N\)) sau khi căn bệnh truyền nhiễm rất mạnh ở bò COWVID-19 bùng phát.
Gần đây, Nông dân John xét nghiệm tất cả những con bò và phát hiện một số con dương tính với căn bệnh. Nhờ các đoạn phim ghi lại bên trong chuồng, ông có thể xem lại những lần tương tác gần đây giữa các cặp bò — hóa ra khi chào hỏi nhau, những con bò bắt tay bằng móng, một cử chỉ đáng tiếc là có thể truyền bệnh từ con bò này sang con bò khác. Nông dân John lập một danh sách các cặp bò tương tác có gắn mốc thời gian, với mỗi mục có dạng \((t, x, y)\), nghĩa là tại thời điểm \(t\), bò \(x\) đã bắt tay bằng móng với bò \(y\). Nông dân John còn biết những điều sau:
Chính xác một con bò trong trang trại có thể đã mang bệnh từ ban đầu (ta gọi con bò này là "bệnh nhân số 0").
Sau khi một con bò bị nhiễm bệnh, nó sẽ truyền bệnh qua \(K\) lần bắt tay bằng móng tiếp theo (có thể gồm nhiều lần với cùng một con bò). Sau khi bắt tay bằng móng \(K\) lần, nó không còn truyền bệnh qua những lần bắt tay bằng móng sau đó nữa (vì lúc này nó nhận ra mình đang làm lây bệnh và rửa móng thật kỹ).
Một khi đã bị nhiễm bệnh, con bò sẽ luôn bị nhiễm bệnh.
Đáng tiếc là Nông dân John không biết con nào trong số \(N\) con bò là bệnh nhân số 0, cũng không biết giá trị của \(K\)! Hãy giúp ông thu hẹp các khả năng của những đại lượng chưa biết này dựa trên dữ liệu đã có. Đề bài đảm bảo tồn tại ít nhất một khả năng hợp lệ.
Tệp tracing.in:
Dòng đầu tiên chứa \(N\) (\(2 \leq N \leq 100\)) và \(T\) (\(1 \leq T \leq 250\)). Dòng tiếp theo chứa một xâu độ dài \(N\) gồm các ký tự 0 và 1, mô tả trạng thái hiện tại của \(N\) con bò của Nông dân John — 0 biểu thị một con bò khỏe mạnh và 1 biểu thị một con bò hiện đang mắc bệnh. Mỗi dòng trong \(T\) dòng tiếp theo mô tả một bản ghi trong danh sách tương tác của Nông dân John và gồm ba số nguyên \(t\), \(x\), \(y\), trong đó \(t\) là thời điểm nguyên dương của lần tương tác (\(t \leq 250\)), còn \(x\) và \(y\) là hai số nguyên phân biệt trong phạm vi \(1 \ldots N\), chỉ ra những con bò đã bắt tay tại thời điểm \(t\). Tại mỗi thời điểm có nhiều nhất một lần tương tác.
Tệp tracing.out:
In một dòng gồm ba giá trị \(x\), \(y\) và \(z\), trong đó \(x\) là số con bò có thể là bệnh nhân số 0, \(y\) là giá trị nhỏ nhất có thể của \(K\) phù hợp với dữ liệu, và \(z\) là giá trị lớn nhất có thể của \(K\) phù hợp với dữ liệu (nếu không thể suy ra cận trên của \(K\) từ dữ liệu, in Infinity cho \(z\)). Lưu ý rằng \(K=0\) cũng có thể xảy ra.
Tất cả các test tuân theo các ràng buộc đã nêu.
Ví dụ 1
4 3
1100
7 1 2
5 2 3
6 2 41 1 InfinityỨng viên duy nhất cho bệnh nhân số 0 là bò 1. Với mọi \(K>0\), bò 1 lây bệnh cho bò 2 tại thời điểm 7, trong khi bò 3 và bò 4 vẫn không bị nhiễm bệnh.
USACO 2020 US Open Contest, Bronze — Cowntact Tracing
Tác giả bài: Brian Dean.