| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2016 - Promotion Counting | 100 (p) | 4.0s | 512M |
| 2 | USACO 2016 - Angry Cows | 100 (p) | 4.0s | 512M |
| 3 | USACO 2016 - Mowing the Field | 100 (p) | 4.0s | 512M |
Cô bò Bessie đang giúp Farmer John tổ chức Kỳ thi Olympic Bò Hoa Kỳ (USACO), một cuộc thi trực tuyến nơi người tham gia trả lời những câu hỏi đầy thử thách để thể hiện vốn hiểu biết sâu rộng về các kiến thức liên quan đến bò.
Để phù hợp với nền tảng đa dạng hơn của người tham gia, Farmer John gần đây đã mở rộng cuộc thi thành bốn bảng có độ khó khác nhau: Đồng, Bạc, Vàng và Bạch Kim. Mọi người mới tham gia đều bắt đầu ở bảng Đồng, và mỗi khi đạt điểm tuyệt đối trong một kỳ thi, họ được thăng lên bảng cao hơn kế tiếp. Một người thậm chí có thể được thăng hạng nhiều lần trong cùng một kỳ thi. Farmer John lưu giữ danh sách tất cả người tham gia cùng bảng hiện tại của họ để có thể xếp mỗi người vào đúng trình độ mỗi khi tổ chức thi.
Khi công bố kết quả kỳ thi gần nhất, Farmer John muốn đưa vào số người đã được thăng từ Đồng lên Bạc, từ Bạc lên Vàng và từ Vàng lên Bạch Kim. Tuy nhiên, ông đã quên đếm các lượt thăng hạng khi chúng diễn ra trong kỳ thi. Là một cô bò thông minh, Bessie nhận ra rằng Farmer John vẫn có thể suy ra số lượt thăng hạng chỉ từ số người ở mỗi bảng trước và sau kỳ thi. Hãy giúp cô thực hiện phép tính này!
Dữ liệu vào gồm bốn dòng, mỗi dòng chứa hai số nguyên trong khoảng \(0\ldots1\,000\,000\). Dòng đầu tiên cho biết số người đăng ký ở bảng Đồng trước và sau kỳ thi. Dòng thứ hai cho biết số người ở bảng Bạc trước và sau kỳ thi. Dòng thứ ba cho biết số người ở bảng Vàng trước và sau kỳ thi. Dòng cuối cùng cho biết số người ở bảng Bạch Kim trước và sau kỳ thi.
In ra ba dòng, mỗi dòng chứa một số nguyên. Dòng đầu tiên chứa số người được thăng từ Đồng lên Bạc. Dòng thứ hai chứa số người được thăng từ Bạc lên Vàng. Dòng cuối cùng chứa số người được thăng từ Vàng lên Bạch Kim.
Ví dụ 1
1 2
1 1
1 1
1 21
1
1Trong ví dụ này, trước kỳ thi có 1 người đăng ký ở mỗi bảng. Khi kỳ thi kết thúc, có 2 người đăng ký ở bảng Đồng và 2 người ở bảng Bạch Kim. Một khả năng dẫn đến kết quả này là có 2 người mới tham gia trong kỳ thi; một người được thăng hạng liên tiếp đến tận bảng Bạch Kim, còn người kia vẫn ở bảng Đồng.
USACO 2016 January Contest, Bronze - Promotion Counting: https://usaco.org/index.php?page=viewproblem2&cpid=591
Tác giả: Brian Dean.
Cô bò Bessie đã thiết kế một trò chơi điện tử mà cô nghĩ sẽ trở thành trò chơi ăn khách tiếp theo: "Angry Cows". Ý tưởng mà cô tin là hoàn toàn nguyên bản như sau: người chơi dùng súng cao su bắn một con bò vào một khung cảnh một chiều gồm các kiện cỏ khô nằm tại nhiều điểm trên một trục số; con bò đáp xuống một kiện cỏ với lực đủ mạnh để làm nó phát nổ, từ đó có thể tạo ra phản ứng dây chuyền khiến các kiện cỏ gần đó tiếp tục phát nổ. Mục tiêu là dùng một con bò duy nhất để khởi phát phản ứng dây chuyền làm nổ càng nhiều kiện cỏ càng tốt.
Có \(N\) kiện cỏ nằm tại các vị trí nguyên phân biệt \(x_1, x_2, \ldots, x_N\) trên trục số. Nếu một con bò được phóng vào kiện cỏ tại vị trí \(x\), kiện cỏ này phát nổ với "bán kính nổ" bằng 1, nghĩa là mọi kiện cỏ khác cách nó không quá 1 đơn vị cũng bị bao trùm bởi vụ nổ. Các kiện cỏ lân cận này sau đó đồng loạt phát nổ, mỗi kiện có bán kính nổ bằng 2, nên những vụ nổ ấy có thể bao trùm thêm các kiện cỏ chưa nổ ở cách xa không quá 2 đơn vị. Ở bước thời gian tiếp theo, các kiện này cũng đồng loạt phát nổ với bán kính nổ bằng 3. Nói chung, tại thời điểm \(t\), một tập hợp các kiện cỏ sẽ phát nổ, mỗi kiện có bán kính nổ \(t\). Những kiện cỏ bị các vụ nổ này bao trùm sẽ phát nổ tại thời điểm \(t+1\) với bán kính nổ \(t+1\), và quá trình cứ tiếp diễn như vậy.
Hãy xác định số kiện cỏ lớn nhất có thể phát nổ nếu một con bò duy nhất được phóng vào kiện cỏ tốt nhất để khởi phát phản ứng dây chuyền.
Dòng đầu tiên chứa \(N\) (\(1\le N\le100\)). Mỗi dòng trong \(N\) dòng còn lại chứa một trong các số nguyên \(x_1,\ldots,x_N\) (mỗi số nằm trong khoảng \(0\ldots1\,000\,000\,000\)).
In số kiện cỏ lớn nhất mà một con bò duy nhất có thể làm phát nổ.
Ví dụ 1
6
8
5
6
13
3
45Trong ví dụ này, phóng một con bò vào kiện cỏ ở vị trí 5 sẽ khiến các kiện tại vị trí 4 và 6 phát nổ, mỗi kiện có bán kính nổ bằng 2. Những vụ nổ này tiếp tục làm các kiện tại vị trí 3 và 8 phát nổ, mỗi kiện có bán kính nổ bằng 3. Tuy nhiên, các vụ nổ cuối cùng này không đủ mạnh để chạm tới kiện cỏ tại vị trí 13.
USACO 2016 January Contest, Bronze - Angry Cows: https://usaco.org/index.php?page=viewproblem2&cpid=592
Tác giả: Brian Dean.
Farmer John khá đáng tin cậy trong mọi khía cạnh quản lý trang trại, ngoại trừ một điều: ông cực kỳ tệ trong việc cắt cỏ đúng lúc hoặc theo một trình tự hợp lý.
Trang trại là một lưới hai chiều lớn gồm các ô vuông đơn vị. FJ bắt đầu tại một trong các ô này vào thời điểm \(t=0\) và cắt cỏ trong ô đó, vì vậy ban đầu đây là ô duy nhất có cỏ đã được cắt. Lộ trình cắt cỏ còn lại của FJ được mô tả bằng một dãy \(N\) chỉ dẫn. Chẳng hạn, nếu chỉ dẫn đầu tiên là W 10, thì từ thời điểm \(t=1\) đến \(t=10\) (tức 10 đơn vị thời gian tiếp theo), ở mỗi thời điểm FJ bước sang ô liền kề phía tây và cắt cỏ trên đường đi. Sau khi hoàn thành dãy bước này, vào thời điểm \(t=10\), ông sẽ ở cách vị trí ban đầu 10 ô về phía tây và đã cắt cỏ trong mọi ô trên đường đi.
FJ tiến triển chậm đến mức một phần cỏ ông đã cắt có thể mọc lại trước khi ông hoàn tất toàn bộ công việc. Bất kỳ phần cỏ nào được cắt tại thời điểm \(t\) sẽ mọc lại vào thời điểm \(t+x\).
Lộ trình cắt cỏ có thể khiến FJ ghé lại cùng một ô nhiều lần, nhưng ông nhận xét rằng mình không bao giờ gặp một ô mà cỏ vẫn chưa mọc lại sau lần cắt trước. Nói cách khác, mỗi khi ông ghé một ô, lần gần nhất ông từng ghé chính ô đó phải cách ít nhất \(x\) đơn vị thời gian để cỏ kịp mọc lại.
Hãy xác định giá trị lớn nhất có thể của \(x\) sao cho nhận xét của FJ vẫn đúng.
Dòng đầu tiên chứa \(N\) (\(1\le N\le100\)). Mỗi dòng trong \(N\) dòng còn lại chứa một chỉ dẫn có dạng D S, trong đó D là một ký tự mô tả hướng (N = bắc, E = đông, S = nam, W = tây) và S là số bước đi theo hướng đó (\(1\le S\le10\)).
In giá trị lớn nhất của \(x\) sao cho FJ không bao giờ bước vào một ô có cỏ vẫn chưa mọc lại sau lần cắt trước. Nếu FJ không bao giờ ghé bất kỳ ô nào quá một lần, hãy in -1.
Ví dụ 1
6
N 10
E 2
S 3
W 4
S 5
E 810Trong ví dụ này, tại thời điểm 17, FJ bước vào một ô mà ông từng bước vào ở thời điểm 7; do đó, \(x\) không được vượt quá 10, nếu không cỏ sau lần ghé đầu tiên vẫn chưa mọc lại. Ông cũng bước vào một ô ở thời điểm 26 mà mình từng ghé ở thời điểm 2; vì vậy \(x\) cũng không được vượt quá 24. Vì ràng buộc đầu tiên chặt hơn, ta thấy \(x\) lớn nhất có thể là 10.
USACO 2016 January Contest, Bronze - Mowing the Field: https://usaco.org/index.php?page=viewproblem2&cpid=593
Tác giả: Brian Dean.