| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2017 - Cow Dance Show | 100 (p) | 4.0s | 512M |
| 2 | USACO 2017 - Hoof, Paper, Scissors | 100 (p) | 4.0s | 512M |
| 3 | USACO 2017 - Secret Cow Code | 100 (p) | 4.0s | 512M |
Sau nhiều tháng luyện tập, đàn bò gần như đã sẵn sàng trình diễn tiết mục khiêu vũ thường niên; năm nay chúng biểu diễn vở ba lê bò nổi tiếng "Cowpelia".
Điều duy nhất còn phải quyết định là kích thước sân khấu. Sân khấu có kích thước \(K\) có thể chứa \(K\) con bò nhảy cùng lúc. \(N\) con bò trong đàn (\(1 \leq N \leq 10\,000\)) được đánh số thuận tiện từ \(1 \ldots N\) theo thứ tự chúng phải xuất hiện trong tiết mục. Mỗi con bò \(i\) dự định nhảy trong một khoảng thời gian cụ thể \(d(i)\). Ban đầu, các con bò \(1 \ldots K\) lên sân khấu và bắt đầu nhảy. Khi con đầu tiên trong số này hoàn thành phần diễn, nó rời sân khấu và bò \(K+1\) lập tức bắt đầu nhảy, rồi quá trình cứ tiếp diễn như vậy để luôn có \(K\) con bò đang nhảy (cho đến cuối chương trình, khi không còn đủ bò chưa biểu diễn). Chương trình kết thúc khi con bò cuối cùng hoàn thành phần diễn của mình, tại thời điểm \(T\).
Rõ ràng, \(K\) càng lớn thì \(T\) càng nhỏ. Vì chương trình không thể kéo dài quá lâu, dữ liệu vào cho một cận trên \(T_{max}\), chỉ giá trị lớn nhất được phép của \(T\). Với ràng buộc này, hãy xác định giá trị \(K\) nhỏ nhất có thể.
Dòng đầu tiên chứa \(N\) và \(T_{max}\), trong đó \(T_{max}\) là một số nguyên không quá \(1\,000\,000\).
\(N\) dòng tiếp theo cho biết thời lượng \(d(1) \ldots d(N)\) của phần biểu diễn của các con bò \(1 \ldots N\). Mỗi giá trị \(d(i)\) là một số nguyên trong khoảng \(1 \ldots 100\,000\).
Đảm bảo rằng nếu \(K=N\), chương trình sẽ kết thúc đúng thời hạn.
In giá trị \(K\) nhỏ nhất sao cho tiết mục khiêu vũ kéo dài không quá \(T_{max}\) đơn vị thời gian.
Ví dụ 1
5 8
4
7
8
6
44USACO 2017 January Contest, Silver — Cow Dance Show. Tác giả đề: Delphine và Brian Dean.
Hẳn bạn đã từng nghe nói đến trò chơi "Oẳn tù tì" (Rock, Paper, Scissors). Đàn bò thích chơi một trò tương tự mà chúng gọi là "Móng guốc, Giấy, Kéo" (Hoof, Paper, Scissors).
Luật chơi "Móng guốc, Giấy, Kéo" rất đơn giản. Hai con bò đấu với nhau. Cả hai cùng đếm đến ba, rồi đồng thời ra một cử chỉ tượng trưng cho móng guốc, một tờ giấy hoặc một chiếc kéo. Móng guốc thắng kéo (vì móng guốc có thể đập nát kéo), kéo thắng giấy (vì kéo có thể cắt giấy), còn giấy thắng móng guốc (vì móng guốc có thể bị giấy cứa). Chẳng hạn, nếu con bò thứ nhất ra cử chỉ "móng guốc" và con thứ hai ra "giấy", con bò thứ hai sẽ thắng. Tất nhiên, hai bên cũng có thể hòa nếu cùng ra một cử chỉ.
Farmer John muốn đấu với cô bò quý Bessie của mình trong \(N\) ván "Móng guốc, Giấy, Kéo" (\(1 \leq N \leq 100\,000\)). Là một chuyên gia của trò chơi, Bessie có thể đoán trước từng cử chỉ của Farmer John. Đáng tiếc, do là một con bò, Bessie cũng rất lười. Vì vậy, cô thường ra cùng một cử chỉ nhiều lần liên tiếp. Trên thực tế, trong toàn bộ các ván đấu, cô chỉ sẵn lòng đổi cử chỉ nhiều nhất một lần. Chẳng hạn, cô có thể ra "móng guốc" trong \(x\) ván đầu tiên, rồi đổi sang "giấy" trong \(N-x\) ván còn lại.
Dựa trên dãy cử chỉ Farmer John sẽ ra, hãy xác định số ván lớn nhất Bessie có thể thắng.
Dòng đầu tiên chứa \(N\).
\(N\) dòng còn lại chứa các cử chỉ của Farmer John, mỗi cử chỉ là H, P hoặc S.
In số ván lớn nhất Bessie có thể thắng khi cô chỉ được đổi cử chỉ nhiều nhất một lần.
Ví dụ 1
5
P
P
H
P
S4USACO 2017 January Contest, Silver — Hoof, Paper, Scissors. Tác giả đề: Mark Chen và Brian Dean.
Đàn bò đang thử nghiệm các mật mã bí mật và đã nghĩ ra một phương pháp tạo một xâu dài vô hạn để dùng làm một phần trong mật mã của chúng.
Với một xâu \(s\), gọi \(F(s)\) là xâu \(s\) nối với xâu \(s\) được "xoay" sang phải một ký tự (khi xoay phải, ký tự cuối của \(s\) vòng lại và trở thành ký tự đầu tiên mới). Từ xâu ban đầu \(s\), đàn bò xây dựng xâu mật mã dài vô hạn bằng cách áp dụng \(F\) lặp đi lặp lại; vì vậy, sau mỗi bước, độ dài của xâu hiện tại tăng gấp đôi.
Cho xâu ban đầu và một chỉ số \(N\), hãy giúp đàn bò tính ký tự ở vị trí thứ \(N\) trong xâu mật mã vô hạn.
Dữ liệu vào gồm một dòng duy nhất chứa một xâu, theo sau là \(N\). Xâu gồm không quá \(30\) chữ cái in hoa và \(N \leq 10^{18}\).
Lưu ý rằng \(N\) có thể quá lớn để lưu trong một số nguyên \(32\) bit tiêu chuẩn, vì vậy bạn có thể cần dùng kiểu số nguyên \(64\) bit (chẳng hạn long long trong C/C++).
In ký tự thứ \(N\) của xâu mật mã vô hạn được xây dựng từ xâu ban đầu. Ký tự đầu tiên ứng với \(N=1\).
Ví dụ 1
COW 8CTrong ví dụ này, xâu ban đầu COW được mở rộng như sau:
COW -> COWWCO -> COWWCOOCOWWC
12345678
USACO 2017 January Contest, Silver — Secret Cow Code. Tác giả đề: Brian Dean.