USACO 2020 - Tháng 12 - Hạng Bạc

Farmer John và các nông dân khác đã làm việc không ngừng để kiểm soát sự lây lan của căn bệnh COWVID-19 nguy hiểm trên các trang trại.

Họ cùng quản lý \(N\) trang trại (\(1\le N\le 10^5\)), được đánh số \(1\ldots N\). Các trang trại được nối bởi \(N-1\) con đường sao cho có thể đi từ trang trại \(1\) đến bất kỳ trang trại nào qua một dãy đường.

Không may, một con bò ở trang trại \(1\) vừa có kết quả dương tính với COWVID-19. Chưa có con bò nào khác tại trang trại đó hoặc các trang trại khác mắc bệnh. Tuy nhiên, vì biết bệnh dễ lây, Farmer John dự đoán đúng một trong hai sự kiện sau sẽ xảy ra trong mỗi ngày kế tiếp:

1. Tại một trang trại duy nhất, một sự kiện "siêu lây nhiễm" làm số bò mắc COWVID-19 ở trang trại đó tăng gấp đôi.
2. Một con bò mắc COWVID-19 đi theo một con đường từ trang trại hiện tại sang một trang trại kề.

Farmer John lo lắng về tốc độ lây lan của dịch bệnh. Hãy xác định số ngày ít nhất có thể để mỗi trang trại đều có ít nhất một con bò mắc bệnh.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\). Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\), cách nhau bởi dấu cách, mô tả một con đường giữa hai trang trại \(a\) và \(b\). Cả \(a\) và \(b\) đều thuộc đoạn \(1\ldots N\).

Dữ liệu ra

In số ngày ít nhất để dịch bệnh có thể lan tới mọi trang trại.

Phân nhóm

• Trong các test 1-4, mọi trang trại, ngoại trừ chính trang trại \(1\), đều nối trực tiếp với trang trại \(1\).
• Trong các test 5-7, mỗi trang trại \(2\ldots N\) kề với nhiều nhất hai con đường.
• Trong các test 8-15, không có ràng buộc bổ sung.

Ví dụ

4
1 2
1 3
1 4

5

Nguồn

USACO 2020 December Contest, Silver - Cowntagion: https://usaco.org/index.php?page=viewproblem2&cpid=1062

Tác giả: Dhruv Rohatgi.

Cho một chuồng rộng vô hạn được biểu diễn dưới dạng lưới 2D. Có một tập hợp lớn gồm \(N\) con bò, con bò thứ \(i\) đứng ở hàng \(x_i\) cột \(y_i\) (ký hiệu là ô \((x_i, y_i)\)).

Một cách đặt hàng rào sẽ bao đóng trọn vẹn một vùng chữ nhật các ô, với các cạnh phải song song với trục \(x\) và \(y\), vùng có thể nhỏ tới mức chỉ bao gồm một ô.

Với một cách đặt hàng rào, có thể dựng nên một tập hợp con các con bò nằm trong hàng rào.

Đếm số tập con khác nhau của tập hợp lớn có thể xây dựng bằng cách đặt hàng rào như trên.

Dữ liệu đầu vào

• Dòng đầu tiên chứa số \(N\) \((1 \leq N \leq 2500)\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số \(x_i, y_i\) \((0 \leq x_i, y_i \leq 10^9)\)

Định dạng đầu ra

• In ra số tập con khác nhau có thể dựng được

Điểm số

• Test 1 là test ví dụ
• Test 2-3 thỏa mãn \(N \leq 20\)
• Test 4-6 thỏa mãn \(N \leq 100\)
• Test 7-12 thỏa mãn \(N \leq 500\)
• Test 13-20 không có điều kiện nào khác.

Ví dụ

4
0 2
1 0
2 3
3 5

13

Farmer John vừa mở rộng trang trại, nên từ góc nhìn của đàn bò, trang trại giờ gần như vô hạn! Những chú bò xem khu vực chăn thả là một lưới ô vuông hai chiều vô hạn, mỗi ô đầy cỏ ngon. Mỗi con trong số \(N\) con bò của Farmer John (\(1\le N\le 1000\)) bắt đầu ở một ô khác nhau; một số con quay mặt về phía bắc, số còn lại quay mặt về phía đông.

Mỗi giờ, mỗi con bò thực hiện một trong hai việc sau:

• Dừng lại, và từ đó về sau vẫn đứng yên, nếu cỏ trong ô hiện tại đã bị một con bò khác ăn.
• Nếu không, ăn hết cỏ trong ô hiện tại rồi đi thẳng một ô theo hướng đang quay mặt.

Theo thời gian, mỗi con bò để lại phía sau một "vệt" gồm các ô trống không còn cỏ. Nếu hai con bò đi vào cùng một ô còn cỏ trong cùng một lượt, chúng cùng ở trong ô đó và tiếp tục đi theo hướng tương ứng vào giờ tiếp theo.

Farmer John không vui khi thấy bò ngừng gặm cỏ và muốn biết phải trách ai. Nếu bò \(b\) dừng trong một ô mà bò \(a\) đã ăn cỏ trước đó, ta nói bò \(a\) đã chặn bò \(b\). Hơn nữa, nếu bò \(a\) chặn bò \(b\) và bò \(b\) chặn bò \(c\), ta cũng nói bò \(a\) đã chặn bò \(c\); quan hệ "chặn" có tính bắc cầu. Mức trách nhiệm của mỗi con bò bằng số bò mà nó đã chặn. Hãy tính mức trách nhiệm của từng con bò.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo mô tả vị trí ban đầu của một con bò bằng một ký tự N (quay mặt về phía bắc) hoặc E (quay mặt về phía đông), cùng hai số nguyên không âm \(x\) và \(y\) (\(0\le x\le 10^9\), \(0\le y\le 10^9\)) là tọa độ của ô. Mọi tọa độ \(x\) đôi một khác nhau; tương tự, mọi tọa độ \(y\) cũng đôi một khác nhau.

Để làm rõ hướng và tọa độ: nếu một con bò ở ô \((x,y)\) và đi về phía bắc, nó đến ô \((x,y+1)\). Nếu đi về phía đông, nó đến ô \((x+1,y)\).

Dữ liệu ra

In \(N\) dòng. Dòng thứ \(i\) là mức trách nhiệm của con bò thứ \(i\) trong dữ liệu vào.

Phân nhóm

• Trong các test 2-5, mọi tọa độ không vượt quá \(2000\).
• Trong các test 6-10, không có ràng buộc bổ sung.

Ví dụ

6
E 3 5
N 5 3
E 4 6
E 10 4
N 11 1
E 9 2

0
0
1
2
1
0

Nguồn

USACO 2020 December Contest, Silver - Stuck in a Rut: https://usaco.org/index.php?page=viewproblem2&cpid=1064

Tác giả: Brian Dean.