USACO 2013 - Tháng 2 - Hạng Đồng

\(N\) con bò của Farmer John (\(1 \le N \le 1000\)) được đánh số thuận tiện từ \(1\) đến \(N\). Bằng một cơ chế liên lạc kiểu cũ dựa trên những chiếc lon thiếc và dây nối, những con bò đã tìm ra cách giao tiếp với nhau mà Farmer John không nhận ra.

Mỗi con bò có thể chuyển tiếp tin nhắn cho nhiều nhất một con bò khác: với bò thứ \(i\), giá trị \(F(i)\) cho biết chỉ số của con bò mà bò thứ \(i\) sẽ chuyển tiếp mọi tin nhắn nó nhận được đến (số này luôn khác \(i\)). Nếu \(F(i)\) bằng \(0\), bò thứ \(i\) không chuyển tiếp tin nhắn.

Thật không may, những con bò nhận ra rằng tin nhắn bắt nguồn từ một số con bò nhất định cuối cùng có thể bị mắc kẹt trong các vòng lặp, được chuyển tiếp mãi mãi theo một chu trình. Một con bò được gọi là "lặp" nếu tin nhắn được gửi từ con bò đó cuối cùng sẽ mắc kẹt trong một vòng lặp. Đàn bò muốn tránh gửi tin nhắn từ những con bò lặp. Hãy giúp chúng đếm tổng số bò của FJ không phải là bò lặp.

Dữ liệu vào

• Dòng đầu tiên chứa số lượng bò \(N\).
• \(N\) dòng tiếp theo: dòng thứ \(i\) chứa giá trị \(F(i)\).

Dữ liệu ra

In ra tổng số bò không phải là bò lặp.

Ví dụ

5
0
4
1
5
4

2

Nguồn

USACO 2013 February Contest, Bronze — Problem 1: Message Relay

Tác giả đề: Brian Dean, 2013.

Mỗi ngày, \(N\) con bò của Farmer John (\(1 \le N \le 100\,000\)) băng qua một con đường ở giữa trang trại. Xét bản đồ trang trại của FJ trên mặt phẳng hai chiều, con đường chạy theo phương ngang, với một bên đường được mô tả bởi đường thẳng \(y=0\) và bên còn lại bởi đường thẳng \(y=1\). Bò thứ \(i\) băng qua đường theo một đoạn thẳng từ vị trí \((a_i,0)\) ở một bên đến vị trí \((b_i,1)\) ở bên kia. Tất cả các giá trị \(a_i\) đôi một khác nhau, tất cả các giá trị \(b_i\) cũng đôi một khác nhau, và mọi giá trị này đều là số nguyên trong khoảng từ \(-1\,000\,000\) đến \(1\,000\,000\).

Mặc dù những con bò khá nhanh nhẹn, FJ vẫn thường lo rằng các cặp bò có đường đi giao nhau có thể làm nhau bị thương nếu chúng va chạm khi băng qua đường. FJ coi một con bò là "an toàn" nếu không có đường đi của con bò nào khác giao với đường đi của nó. Hãy giúp FJ tính số lượng bò an toàn.

Dữ liệu vào

• Dòng đầu tiên chứa số lượng bò \(N\).
• \(N\) dòng tiếp theo: dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\), mô tả đường đi của bò thứ \(i\).

Dữ liệu ra

In ra số lượng bò an toàn.

Ví dụ

4
-3 4
7 8
10 16
3 9

2

Nguồn

USACO 2013 February Contest, Bronze — Problem 2: Cow Crossings

Tác giả đề: Brian Dean, 2013.

Farmer John đã xếp \(N\) kiện cỏ khô (\(1 \le N \le 50\,000\)) ở giữa một cánh đồng. Nếu coi cánh đồng là một lưới \(1\,000\,000 \times 1\,000\,000\) gồm các ô vuông \(1 \times 1\), thì mỗi kiện cỏ khô chiếm đúng một ô (dĩ nhiên, không có hai kiện cỏ khô nào chiếm cùng một ô).

FJ nhận thấy tất cả các kiện cỏ khô tạo thành một vùng liên thông lớn, nghĩa là từ bất kỳ kiện cỏ nào, ta có thể đến bất kỳ kiện cỏ nào khác bằng một chuỗi bước đi về phía bắc, nam, đông hoặc tây sang các kiện cỏ kề cạnh trực tiếp. Tuy nhiên, vùng liên thông gồm các kiện cỏ có thể chứa những "lỗ hổng" — các vùng trống bị kiện cỏ bao quanh hoàn toàn.

Hãy giúp FJ xác định chu vi của vùng được tạo bởi các kiện cỏ khô. Lưu ý rằng các lỗ hổng không đóng góp vào chu vi.

Dữ liệu vào

• Dòng đầu tiên chứa số lượng kiện cỏ khô \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa vị trí \((x,y)\) của một kiện cỏ khô, trong đó \(x\) và \(y\) đều là số nguyên trong khoảng từ \(1\) đến \(1\,000\,000\). Vị trí \((1,1)\) là ô dưới cùng bên trái trong cánh đồng của FJ, còn vị trí \((1000000,1000000)\) là ô trên cùng bên phải.

Dữ liệu ra

In ra chu vi của vùng liên thông gồm các kiện cỏ khô.

Ví dụ

8
10005 200003
10005 200004
10008 200004
10005 200005
10006 200003
10007 200003
10007 200004
10006 200005

14

XX 
X XX
XXX

Nguồn

USACO 2013 February Contest, Silver — Problem 1: Perimeter

Tác giả đề: Brian Dean, 2013.