| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2017 - Balanced Photo | 100 (p) | 4.0s | 512M |
| 2 | USACO 2017 - Hoof, Paper, Scissors | 100 (p) | 4.0s | 512M |
| 3 | USACO 2017 - Cow Navigation | 100 (p) | 4.0s | 512M |
Farmer John đang xếp \(N\) con bò thành một hàng để chụp ảnh (\(1 \leq N \leq 100\,000\)). Chiều cao của con bò thứ \(i\) trong hàng là \(h_i\), và chiều cao của tất cả các con bò đều khác nhau.
Như với mọi bức ảnh chụp đàn bò, Farmer John muốn bức ảnh này trông đẹp nhất có thể. Ông cho rằng bò \(i\) trông "mất cân đối" nếu \(L_i\) và \(R_i\) chênh lệch nhau quá hệ số \(2\), trong đó \(L_i\) và \(R_i\) lần lượt là số bò cao hơn bò \(i\) nằm bên trái và bên phải nó. Nói cách khác, bò \(i\) mất cân đối nếu số lớn hơn trong hai số \(L_i\) và \(R_i\) lớn hơn nghiêm ngặt hai lần số nhỏ hơn. Farmer John hy vọng rằng không có quá nhiều bò bị mất cân đối.
Hãy giúp Farmer John tính tổng số bò bị mất cân đối.
Dòng đầu tiên chứa \(N\). \(N\) dòng tiếp theo chứa \(h_1 \ldots h_N\), mỗi giá trị là một số nguyên không âm không quá \(1\,000\,000\,000\).
In số lượng bò bị mất cân đối.
Ví dụ 1
7
34
6
23
0
5
99
23Trong ví dụ này, các con bò có chiều cao \(34\), \(5\) và \(2\) bị mất cân đối.
USACO 2017 January Contest, Gold — Balanced Photo. Tác giả đề: 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 \(K\) lần (\(0 \leq K \leq 20\)). Chẳng hạn, nếu \(K=2\), cô có thể ra "móng guốc" trong vài ván đầu tiên, rồi đổi sang "giấy" trong một khoảng thời gian, sau đó kết thúc các ván còn lại bằng "móng guốc".
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\) và \(K\).
\(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 \(K\) lần.
Ví dụ 1
5 1
P
P
H
P
S4USACO 2017 January Contest, Gold — Hoof, Paper, Scissors. Tác giả đề: Mark Chen và Brian Dean.
Bessie lại bị mắc kẹt ở phía bên kia chuồng của Farmer John, và vì thị lực quá kém, cô cần bạn giúp tìm đường đi qua chuồng.
Chuồng được mô tả bằng một lưới gồm \(N \times N\) ô vuông (\(2 \leq N \leq 20\)); một số ô trống, còn một số ô chứa các kiện cỏ khô không thể đi qua. Bessie bắt đầu ở góc dưới bên trái (ô \((1,1)\)) và muốn đi đến góc trên bên phải (ô \((N,N)\)). Bạn có thể dẫn đường cho cô bằng một dãy chỉ dẫn, mỗi chỉ dẫn là "tiến lên", "quay trái \(90\) độ" hoặc "quay phải \(90\) độ". Bạn muốn đưa ra dãy chỉ dẫn ngắn nhất có thể dẫn cô đến đích. Nếu bạn bảo Bessie đi ra ngoài lưới (tức là đâm vào tường chuồng) hoặc đi vào một kiện cỏ khô, cô sẽ không di chuyển và sẽ chuyển sang thực hiện lệnh tiếp theo trong dãy.
Đáng tiếc, Bessie không biết ban đầu mình đang quay mặt lên trên (hướng về ô \((1,2)\)) hay sang phải (hướng về ô \((2,1)\)). Bạn cần đưa ra dãy chỉ dẫn ngắn nhất có thể dẫn cô đến đích trong cả hai trường hợp. Sau khi đến đích, cô sẽ bỏ qua mọi lệnh còn lại.
Dòng đầu tiên chứa \(N\).
Mỗi dòng trong \(N\) dòng tiếp theo chứa một xâu có đúng \(N\) ký tự, biểu diễn chuồng. Ký tự đầu tiên của dòng cuối cùng là ô \((1,1)\). Ký tự cuối cùng của dòng đầu tiên là ô \((N,N)\).
Mỗi ký tự là H để biểu thị một kiện cỏ khô hoặc E để biểu thị một ô trống.
Đảm bảo rằng các ô \((1,1)\) và \((N,N)\) đều trống, đồng thời tồn tại một đường đi qua các ô trống từ ô \((1,1)\) đến ô \((N,N)\).
In trên một dòng độ dài của dãy chỉ dẫn ngắn nhất có thể dẫn Bessie đến đích, bất kể ban đầu cô quay mặt lên trên hay sang phải.
Ví dụ 1
3
EHE
EEE
EEE9Trong ví dụ này, dãy chỉ dẫn "Tiến lên, Phải, Tiến lên, Tiến lên, Trái, Tiến lên, Trái, Tiến lên, Tiến lên" sẽ dẫn Bessie đến đích bất kể hướng ban đầu của cô.
USACO 2017 January Contest, Gold — Cow Navigation. Tác giả đề: Brian Dean.