| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2017 - Moocast | 100 (p) | 4.0s | 512M |
| 2 | USACO 2017 - Cow Checklist | 100 (p) | 4.0s | 512M |
| 3 | USACO 2017 - Lasers and Mirrors | 100 (p) | 4.0s | 512M |
\(N\) con bò của Farmer John (\(1 \leq N \leq 1000\)) muốn tổ chức một hệ thống "moo-cast" khẩn cấp để truyền những thông điệp quan trọng cho nhau.
Thay vì rống gọi nhau từ xa, đàn bò quyết định tự trang bị bộ đàm, mỗi con một chiếc. Mỗi bộ đàm có bán kính truyền hữu hạn, nhưng đàn bò có thể chuyển tiếp thông điệp cho nhau theo một đường đi gồm nhiều chặng, nên không nhất thiết mọi con bò đều phải truyền trực tiếp được tới mọi con bò khác.
Đàn bò cần quyết định sẽ chi bao nhiêu tiền cho các bộ đàm. Nếu chúng chi \(X\) đô la, mỗi con sẽ nhận được một bộ đàm có khả năng truyền xa tới khoảng cách \(\sqrt{X}\). Nói cách khác, bình phương khoảng cách giữa hai con bò phải không vượt quá \(X\) để chúng có thể liên lạc.
Hãy giúp đàn bò xác định giá trị nguyên nhỏ nhất của \(X\) sao cho một thông điệp phát từ bất kỳ con bò nào cuối cùng cũng có thể tiếp cận mọi con bò khác.
Dòng đầu tiên chứa \(N\).
\(N\) dòng tiếp theo, mỗi dòng chứa tọa độ \(x\) và \(y\) của một con bò. Cả hai tọa độ đều là số nguyên trong khoảng \(0 \ldots 25\,000\).
In một dòng chứa số nguyên \(X\), là số tiền tối thiểu đàn bò phải chi cho các bộ đàm.
Ví dụ 1
4
1 3
5 4
7 2
6 117USACO 2016 December Contest, Gold — Moocast. Tác giả đề: Richard Peng.
Mỗi ngày, Farmer John đi qua đồng cỏ để kiểm tra tình trạng của từng con bò. Trang trại của ông có hai giống bò là Holstein và Guernsey. \(H\) con bò Holstein được đánh số thuận tiện từ \(1 \ldots H\), còn \(G\) con bò Guernsey được đánh số thuận tiện từ \(1 \ldots G\) (\(1 \leq H \leq 1000\), \(1 \leq G \leq 1000\)). Mỗi con bò nằm tại một điểm trên mặt phẳng hai chiều (các điểm không nhất thiết phân biệt).
Farmer John bắt đầu chuyến đi tại bò Holstein \(1\) và kết thúc tại bò Holstein \(H\). Trên đường đi, ông muốn thăm từng con bò; để thuận tiện cho việc cập nhật danh sách những con bò đã thăm, ông muốn thăm các bò Holstein và Guernsey theo thứ tự đánh số. Trong dãy gồm tất cả \(H+G\) con bò mà ông thăm, các bò Holstein được đánh số \(1 \ldots H\) phải xuất hiện như một dãy con (không nhất thiết liên tiếp), và các bò Guernsey cũng vậy. Nói cách khác, dãy gồm tất cả \(H+G\) con bò phải được tạo thành bằng cách xen kẽ danh sách bò Holstein đánh số \(1 \ldots H\) với danh sách bò Guernsey đánh số \(1 \ldots G\).
Khi Farmer John di chuyển từ một con bò sang một con bò khác qua khoảng cách \(D\), ông tiêu tốn \(D^2\) năng lượng. Hãy giúp ông xác định lượng năng lượng nhỏ nhất cần để thăm tất cả đàn bò theo một chuyến đi như mô tả ở trên.
Dòng đầu tiên chứa \(H\) và \(G\), cách nhau bởi một dấu cách.
\(H\) dòng tiếp theo chứa tọa độ \(x\), \(y\) của \(H\) con bò Holstein; \(G\) dòng sau đó chứa tọa độ của các bò Guernsey. Mỗi tọa độ là một số nguyên trong khoảng \(0 \ldots 1000\).
In một dòng chứa lượng năng lượng nhỏ nhất cần cho chuyến đi thăm tất cả đàn bò của Farmer John.
Ví dụ 1
3 2
0 0
1 0
2 0
0 3
1 320USACO 2016 December Contest, Gold — Cow Checklist. Tác giả đề: Brian Dean.
Vì một lý do nào đó, đàn bò của Farmer John dường như lúc nào cũng tổ chức các màn trình diễn ánh sáng laser.
Cho màn trình diễn mới nhất, đàn bò đã kiếm được một máy laser lớn và mạnh đến mức chúng không thể dễ dàng di chuyển nó khỏi nơi được giao tới. Chúng muốn bằng cách nào đó đưa ánh sáng từ máy laser đến chuồng bò ở phía bên kia khu đất của Farmer John. Cả máy laser lẫn chuồng bò đều có thể được coi là nằm tại các điểm trên mặt phẳng hai chiều trong bản đồ trang trại. Đàn bò dự định hướng máy laser để nó phát ra một tia sáng theo phương ngang hoặc phương dọc (tức là thẳng hàng với trục \(x\) hoặc trục \(y\)). Sau đó, chúng sẽ cho tia sáng phản xạ qua một số gương để dẫn nó tới chuồng bò.
Trong trang trại có \(N\) cọc hàng rào (\(1 \leq N \leq 100\,000\)) nằm tại các điểm phân biệt trên mặt phẳng hai chiều (và cũng khác vị trí máy laser cùng chuồng bò), là những nơi đàn bò có thể lắp gương. Đàn bò có thể chọn không lắp gương trên một cọc hàng rào; khi đó, tia laser đơn giản sẽ đi thẳng qua phía trên cọc mà không đổi hướng. Nếu lắp gương trên một cọc hàng rào, chúng đặt gương theo đường chéo dạng / hoặc \ để chuyển hướng một tia sáng nằm ngang thành thẳng đứng hoặc ngược lại.
Hãy tính số gương ít nhất mà đàn bò cần dùng để chuyển hướng tia laser tới chuồng bò.
Dòng đầu tiên chứa năm số nguyên cách nhau bởi dấu cách: \(N\), \(x_L\), \(y_L\), \(x_B\), \(y_B\), trong đó \((x_L,y_L)\) là vị trí máy laser và \((x_B,y_B)\) là vị trí chuồng bò. Tất cả các tọa độ đều nằm trong khoảng từ \(0\) đến \(1\,000\,000\,000\).
\(N\) dòng tiếp theo, mỗi dòng chứa tọa độ \(x\), \(y\) của một cọc hàng rào; cả hai đều là số nguyên trong khoảng \(0 \ldots 1\,000\,000\,000\).
In số gương ít nhất cần dùng để dẫn tia laser tới chuồng bò, hoặc in \(-1\) nếu không thể thực hiện được.
Ví dụ 1
4 0 0 7 2
3 2
0 2
1 6
3 01USACO 2016 December Contest, Gold — Lasers and Mirrors. Tác giả đề: Brian Dean.