| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2016Jan Gold - Angry Cows | 100 (p) | 1.0s | 256M |
| 2 | USACO 2016 - Radio Contact | 100 (p) | 4.0s | 512M |
| 3 | USACO 2016 - Lights Out | 100 (p) | 4.0s | 512M |
(lược dịch)
Cô bò Bessie đã thiết kế một thứ mà cô ấy nghĩ sẽ là trò chơi điện tử lớn tiếp theo: "Angry Cows". Ý tưởng trò chơi (mà cô tin tưởng là hoàn-toàn-nguyên-bản) là người chơi sẽ bắn một chú bò bằng một chiếc ná lên một màn chơi một-chiều gồm các đống rơm đặt tại các vị trí khác nhau trên một trục số; chú bò sẽ đáp xuống với lực đủ mạnh để phá hủy các đống rơm gần vị trí đáp đấy, khiến cho một phản ứng dây chuyền được kích hoạt làm các đống rơm khác cũng bị kích nổ theo. Mục tiêu của trò chơi là chỉ sử dụng một chú bò để bắt đầu phản ứng dây chuyền để phá hủy toàn bộ đống rơm.
Có \(N\) đống rơm được đặt tại các vị trí nguyên dương khác nhau \(x_1, x_2, \dots, x_n\) trên trục số. Nếu một chú bò được phóng với cường độ lực \(R\) đáp xuống điểm \(x\), nó sẽ tạo ra một vụ nổ có "bán kính R", hủy diệt toàn bộ đống rơm nằm trong đoạn \([x-R; x+R]\). Những đống rơm này sau đó sẽ đồng loạt phát nổ với bán kính nổ \(R-1\). Nhứng đống rơm chưa-bị-kích-nổ bị kích nổ tiếp theo từ những đống rơm trước sẽ phát nổ với bán kinh \(R-2\), và cứ tiếp tục như thế.
Hãy xác định cường độ \(R\) đối thiểu để phóng chú bò sao cho nếu nó đáp xuống một vị trí thích hợp, thì nó sẽ tạo nên phản ứng nổ dây chuyền lên tất cả đống rơm trong màn chơi.
Ví dụ 1
5
8
10
3
11
13.0Chú bò được phóng ra với lực \(3\) đáp xuống vị trí \(5\) sẽ phá hủy ngay lập tức đống rơm ở vị trí \(3\) và \(8\). Hai đống rơm này sẽ đồng thời phát nổ với bán kính \(2\), hủy diệt đống rơm ở vị trí \(1\) và \(10\). Hai đống rơm tiếp theo này lại phát nổ với bán kính \(1\), hủy diệt đống rơm ở vị trí \(11\), mà sau đó sẽ phát nổ với bán kính \(0\).
Farmer John đã làm mất chiếc chuông bò yêu thích, và cô bò Bessie đồng ý giúp ông tìm nó! Cả hai tỏa ra tìm kiếm trên trang trại theo những đường đi khác nhau, nhưng vẫn liên lạc bằng bộ đàm để giữ liên lạc với nhau. Đáng tiếc, pin bộ đàm của họ sắp cạn, nên họ muốn lên kế hoạch di chuyển để tiết kiệm năng lượng bằng cách cố gắng luôn giữ khoảng cách giữa hai người ở mức nhỏ.
Farmer John bắt đầu tại vị trí \((f_x,f_y)\) và dự định đi theo một đường gồm \(N\) bước, mỗi bước là N (bắc), E (đông), S (nam) hoặc W (tây). Bessie bắt đầu tại vị trí \((b_x,b_y)\) và đi theo một đường tương tự gồm \(M\) bước. Hai đường đi có thể có những điểm chung. Tại mỗi bước thời gian, Farmer John có thể đứng yên ở vị trí hiện tại hoặc tiến một bước theo đường đi của mình, theo hướng kế tiếp trên đường đó (giả sử ông chưa đến vị trí cuối cùng). Bessie cũng có thể lựa chọn tương tự. Tại mỗi bước thời gian (không tính bước đầu tiên khi họ ở các vị trí ban đầu), bộ đàm tiêu thụ một lượng năng lượng bằng bình phương khoảng cách giữa họ.
Hãy giúp FJ và Bessie lập một chiến lược di chuyển chung sao cho tổng năng lượng tiêu thụ đến và tính cả bước cuối cùng, tức thời điểm đầu tiên mà cả hai đều đã đến vị trí cuối trên đường đi tương ứng, là nhỏ nhất.
Dòng đầu tiên chứa \(N\) và \(M\) (\(1\le N,M\le1000\)). Dòng thứ hai chứa hai số nguyên \(f_x\) và \(f_y\), còn dòng thứ ba chứa \(b_x\) và \(b_y\) (\(0\le f_x,f_y,b_x,b_y\le1000\)). Dòng tiếp theo chứa một xâu độ dài \(N\) mô tả đường đi của FJ, và dòng cuối cùng chứa một xâu độ dài \(M\) mô tả đường đi của Bessie.
Đảm bảo rằng trong suốt hành trình, tọa độ của Farmer John và Bessie luôn nằm trong khoảng \(0\le x,y\le1000\). Lưu ý rằng hướng đông là chiều dương của trục \(x\), còn hướng bắc là chiều dương của trục \(y\).
In một số nguyên cho biết lượng năng lượng nhỏ nhất mà FJ và Bessie có thể sử dụng trong hành trình.
Ví dụ 1
2 7
3 0
5 0
NN
NWWWWWN28USACO 2016 January Contest, Gold - Radio Contact: https://usaco.org/index.php?page=viewproblem2&cpid=598
Tác giả: Brian Dean.
Farmer John đã lắp một chiếc máy vắt sữa hiện đại mới trong chuồng, nhưng nó tiêu thụ nhiều điện đến mức thỉnh thoảng làm mất điện! Việc này xảy ra thường xuyên đến nỗi Bessie đã ghi nhớ bản đồ chuồng, giúp cô dễ tìm lối ra hơn trong bóng tối. Tuy nhiên, cô tò mò về ảnh hưởng của việc mất điện đến khả năng nhanh chóng thoát khỏi chuồng. Chẳng hạn, cô muốn biết mình có thể phải đi xa hơn bao nhiêu để tìm được lối ra trong bóng tối.
Chuồng được mô tả bởi một đa giác đơn (không tự cắt) có các đỉnh nguyên \((x_1,y_1)\ldots(x_n,y_n)\) được liệt kê theo chiều kim đồng hồ. Các cạnh luân phiên nằm ngang (song song với trục \(x\)) và thẳng đứng (song song với trục \(y\)); cạnh đầu tiên có thể thuộc một trong hai loại. Lối ra nằm tại \((x_1,y_1)\). Bessie bắt đầu ở bên trong chuồng tại một đỉnh nào đó \((x_i,y_i)\) với \(i>1\). Cô chỉ có thể đi quanh chu vi chuồng theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ. Mục tiêu của cô là đi quãng đường ngắn nhất để đến lối ra. Khi đèn sáng, điều này tất nhiên khá dễ: từ vị trí hiện tại, cô sẽ đi đến lối ra theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ, tùy hướng nào ngắn hơn.
Một ngày nọ, đèn tắt khiến Bessie hoảng sợ và quên mất mình đang đứng ở đỉnh nào. May thay, cô vẫn nhớ chính xác bản đồ chuồng, nên có thể xác định vị trí bằng cách đi quanh chuồng và dùng xúc giác. Mỗi khi đứng tại một đỉnh (kể cả đỉnh ban đầu), cô có thể cảm nhận chính xác góc trong tại đỉnh đó và biết được đỉnh ấy có phải lối ra hay không. Khi đi dọc một cạnh của chuồng, sau khi đi hết cạnh đó cô có thể xác định chính xác độ dài của nó. Bessie quyết định dùng chiến lược sau: cô sẽ di chuyển theo chiều kim đồng hồ quanh chu vi chuồng cho đến khi cảm nhận đủ góc và cạnh để suy ra mình hiện đang ở đỉnh nào. Khi đó, cô có thể dễ dàng tìm đường đến lối ra với quãng đường còn lại nhỏ nhất, bằng cách tiếp tục đi theo chiều kim đồng hồ hoặc đổi hướng và đi ngược chiều kim đồng hồ.
Hãy giúp Bessie xác định mức tăng lớn nhất của quãng đường cô phải đi trong trường hợp xấu nhất (xét mọi đỉnh xuất phát có thể) khi đi trong bóng tối so với khi chuồng được chiếu sáng.
Dòng đầu tiên chứa \(N\) (\(4\le N\le200\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên mô tả các điểm \((x_i,y_i)\) theo thứ tự chiều kim đồng hồ quanh chuồng. Các số nguyên này nằm trong khoảng \(-100\,000\ldots100\,000\).
In mức tăng lớn nhất của quãng đường Bessie phải đi tại vị trí xuất phát xấu nhất khi dùng chiến lược được mô tả trong đề bài.
Ví dụ 1
4
0 0
0 10
1 10
1 02Trong ví dụ này, Bessie có thể cảm nhận rằng ban đầu cô đang đứng tại một góc 90 độ, nhưng không thể biết mình đang ở đỉnh 2, 3 hay 4. Sau khi đi dọc một cạnh theo chiều kim đồng hồ, Bessie hoặc đến lối ra, hoặc có thể xác định duy nhất vị trí của mình dựa trên độ dài cạnh này. Các quãng đường cô đi được là:
Do đó, chênh lệch trong trường hợp xấu nhất trên mọi điểm xuất phát là \(12-10=2\). Nghĩa là với chiến lược của mình, Bessie có thể đảm bảo rằng bất kể xuất phát ở đâu, trong bóng tối cô sẽ đi xa hơn nhiều nhất 2 đơn vị so với khi có ánh sáng.
USACO 2016 January Contest, Gold - Lights Out: https://usaco.org/index.php?page=viewproblem2&cpid=599
Tác giả: Brian Dean.