| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2016 - Angry Cows | 100 (p) | 4.0s | 512M |
| 2 | USACO 2016 - Subsequences Summing to Sevens | 100 (p) | 4.0s | 512M |
| 3 | USACO 2016 - Build Gates | 100 (p) | 4.0s | 512M |
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 những 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ố. Mỗi con bò đáp xuống với lực đủ mạnh để làm nổ các kiện cỏ ở gần điểm tiếp đất. Mục tiêu là dùng một nhóm bò để làm nổ tất cả các kiện cỏ.
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ới sức mạnh \(R\) và đáp xuống vị trí \(x\), nó sẽ tạo ra một vụ nổ có "bán kính \(R\)", phá hủy mọi kiện cỏ trong đoạn \(x-R\ldots x+R\).
Có tổng cộng \(K\) con bò để phóng, mỗi con đều có cùng sức mạnh \(R\). Hãy xác định giá trị nguyên nhỏ nhất của \(R\) sao cho có thể dùng \(K\) con bò để làm nổ mọi kiện cỏ trong khung cảnh.
Dòng đầu tiên chứa \(N\) (\(1\le N\le50\,000\)) và \(K\) (\(1\le K\le10\)). 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ức mạnh nhỏ nhất \(R\) cần dùng để phóng mỗi con bò nhằm làm nổ tất cả các kiện cỏ.
Ví dụ 1
7 2
20
25
18
8
10
3
15USACO 2016 January Contest, Silver - Angry Cows: https://usaco.org/index.php?page=viewproblem2&cpid=594
Tác giả: Brian Dean.
\(N\) con bò của Farmer John đang đứng thành một hàng, như thỉnh thoảng chúng vẫn hay làm. Mỗi con bò được gắn một mã số nguyên phân biệt để FJ có thể nhận ra chúng. FJ muốn chụp ảnh một nhóm bò liên tiếp, nhưng do một sự cố đau buồn thời thơ ấu liên quan đến các số \(1\ldots6\), ông chỉ muốn chụp một nhóm bò nếu tổng các mã số của chúng là bội của 7.
Hãy giúp FJ xác định số lượng bò trong nhóm lớn nhất mà ông có thể chụp.
Dòng đầu tiên chứa \(N\) (\(1\le N\le50\,000\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa mã số nguyên của một con bò trong số \(N\) con (tất cả đều nằm trong khoảng \(0\ldots1\,000\,000\)).
In số lượng bò trong nhóm liên tiếp lớn nhất có tổng mã số là bội của 7. Nếu không tồn tại nhóm như vậy, in 0.
Lưu ý rằng tổng mã số của một nhóm bò lớn có thể quá lớn để lưu trong kiểu số nguyên 32 bit tiêu chuẩn. Vì vậy, nếu tính tổng mã số của những nhóm lớn, bạn có thể cần dùng kiểu số nguyên lớn hơn, chẳng hạn long long 64 bit trong C/C++.
Ví dụ 1
7
3
5
1
6
2
14
105Trong ví dụ này, \(5+1+6+2+14=28\).
USACO 2016 January Contest, Silver - Subsequences Summing to Sevens: https://usaco.org/index.php?page=viewproblem2&cpid=595
Tác giả: Brian Dean.
Farmer John quyết định xây một hàng rào mới quanh một số phần của trang trại, nhưng ông liên tục bị xao nhãng và cuối cùng xây hàng rào thành một hình dạng kỳ lạ hơn nhiều so với dự định!
Cụ thể, FJ bắt đầu tại vị trí \((0,0)\) và đi \(N\) bước, mỗi bước di chuyển một đơn vị về phía bắc, nam, đông hoặc tây. Với mỗi bước đi, ông để lại phía sau một đoạn hàng rào dài một đơn vị. Chẳng hạn, nếu bước đầu tiên đi về phía bắc, ông thêm một đoạn hàng rào từ \((0,0)\) đến \((0,1)\). FJ có thể ghé lại một điểm nhiều lần và thậm chí có thể dựng cùng một đoạn hàng rào nhiều lần. Hàng rào còn có thể tự cắt nếu đường đi của ông băng qua một dải hàng rào đã dựng trước đó.
Không cần phải nói, FJ khá thất vọng với kết quả sau khi hoàn tất hàng rào. Đặc biệt, ông nhận thấy mình có thể đã ngăn cách một số khu vực của trang trại với những khu vực khác, khiến người ta không còn có thể đi từ khu vực này sang khu vực kia mà không băng qua hàng rào. FJ muốn thêm các cổng vào hàng rào để khắc phục vấn đề. Một cổng có thể được thêm vào bất kỳ đoạn hàng rào dài một đơn vị nào ông đã dựng, cho phép đi qua giữa hai phía của đoạn đó.
Hãy xác định số cổng ít nhất FJ cần xây để mọi khu vực của trang trại lại có thể đi đến nhau.
Dòng đầu tiên chứa \(N\) (\(1\le N\le1000\)). Dòng tiếp theo chứa một xâu độ dài \(N\) mô tả đường đi của FJ. Mỗi ký tự là N (bắc), E (đông), S (nam) hoặc W (tây).
In một số nguyên cho biết số cổng ít nhất FJ cần xây để khôi phục khả năng kết nối hoàn toàn giữa mọi khu vực trong trang trại. Lưu ý rằng đáp án có thể bằng 0 nếu ngay từ đầu mọi khu vực của trang trại đã liên thông.
Ví dụ 1
14
NNNESWWWSSEEEE2USACO 2016 January Contest, Silver - Build Gates: https://usaco.org/index.php?page=viewproblem2&cpid=596
Tác giả: Brian Dean.