USACO 2015 - Tháng 12 - Hạng Vàng

Cô bò Bessie là một người rất hâm mộ các trò chơi bài, điều này khá đáng ngạc nhiên vì cô không có ngón cái đối diện. Đáng tiếc là không có con bò nào khác trong đàn là đối thủ giỏi. Thực tế, chúng chơi tệ đến mức luôn chơi theo một cách hoàn toàn có thể dự đoán! Dù vậy, việc tìm ra cách chiến thắng vẫn có thể là một thử thách đối với Bessie.

Bessie và cô bạn Elsie hiện đang chơi một trò bài đơn giản. Họ lấy một bộ gồm \(2N\) lá bài, được đánh số thuận tiện từ \(1\ldots2N\), rồi chia cho Bessie \(N\) lá và Elsie \(N\) lá. Sau đó, hai cô chơi \(N\) vòng; trong mỗi vòng, Bessie và Elsie đều đánh một lá bài. Trong \(N/2\) vòng đầu, người có lá bài lớn hơn giành được một điểm; trong \(N/2\) vòng cuối, luật chơi đổi lại và người đánh lá bài nhỏ hơn giành được một điểm.

Biết rằng Bessie có thể dự đoán thứ tự Elsie sẽ đánh các lá bài, hãy xác định số điểm tối đa Bessie có thể giành được.

Dữ liệu vào

Dòng đầu tiên chứa giá trị \(N\) (\(2\le N\le50\,000\); \(N\) là số chẵn).

\(N\) dòng tiếp theo chứa các lá bài mà Elsie sẽ đánh trong từng vòng liên tiếp của trò chơi. Lưu ý rằng từ thông tin này có thể dễ dàng xác định các lá bài của Bessie.

Dữ liệu ra

In một dòng chứa số điểm tối đa Bessie có thể ghi được.

Ví dụ

4
1
8
4
3

2

Nguồn

USACO 2015 December Contest, Gold - High Card Low Card (Gold): https://usaco.org/index.php?page=viewproblem2&cpid=573

Tác giả: Brian Dean.

Nuôi heo là một ngành nông nghiệp hết sức quan trọng, nó cung cấp một số lượng rất lớn thịt cho bữa ăn của hàng tỷ người trên Trái Đất và là một loại thực phẩm thiết yếu. Khi nuôi heo, để tối đa lượng thịt, người nông dân thường để heo ít vận động và bón cho heo ăn nhiều để lượng năng lượng dư chuyển hóa thành thịt. Thực phẩm cho heo gồm 2 loại : một loại cung cấp cho heo \(A\) kg thịt và một loại cấp \(B\) kg thịt. Vì thực phẩm được làm trong thế kỉ 25 khi công nghệ đã tiến đến giai đoạn siêu tiên tiến nên khi cho ăn, heo sẽ tăng lên \(x\) kg ngay lập tức với \(x = A\) nếu cho thực phẩm loại \(A\) hoặc \(x = B\) nếu cho thực phẩm loại \(B\). Tuy nhiên, mỗi con heo luôn có một mức độ thịt tối đa nhất định \(W\) (\(W \leq 5 \times 10^6\)). Nếu heo sản xuất nhiều hơn \(W\) kg thịt, chúng sẽ phát nổ vì quá tải. Nhưng việc này cũng đã nằm trong tính toán của người nông dân, họ chỉ cần cho heo ngủ một giấc thì lượng thịt của heo sẽ giảm đi một nửa và người nông dân chỉ có thể cho heo ngủ nhiều nhất \(1\) lần.

Cho \(W\), \(A\) và \(B\) là số liệu của một con heo và thực phẩm của nó. Hãy xác định xem lượng thịt lớn nhất mà heo có thể sản xuất sao cho trong quá trình nuôi, heo không bị phát nổ vì quá tải.

INPUT

• 1 dòng duy nhất gồm 3 số nguyên dương \(T, A\) và \(B\) \((T \leq 5 \times 10^6, 1 \leq A,B \leq T )\).

OUTPUT:

• 1 số nguyên duy nhất là lượng thịt tối đa mà heo có thể sản xuất.

Example

8 5 6

8

Sau khi ăn quá nhiều trái cây trong bếp của Farmer John, cô bò Bessie bắt đầu có những giấc mơ rất kỳ lạ! Trong giấc mơ gần đây nhất, cô bị mắc kẹt trong một mê cung có dạng lưới \(N\times M\) ô (\(1\le N,M\le1\,000\)). Cô bắt đầu ở ô trên cùng bên trái và muốn đến ô dưới cùng bên phải. Khi đứng trên một ô, cô có thể di chuyển sang các ô kề theo bất kỳ hướng nào trong bốn hướng chính.

Nhưng khoan đã! Mỗi ô có một màu, và mỗi màu có một tính chất khác nhau! Bessie chỉ nghĩ đến thôi cũng thấy đau đầu:

• Nếu một ô có màu đỏ, ô đó không thể đi qua.
• Nếu một ô có màu hồng, cô có thể đi trên đó như bình thường.
• Nếu một ô có màu cam, cô có thể đi trên đó như bình thường, nhưng ô này sẽ khiến Bessie mang mùi cam.
• Nếu một ô có màu xanh lam, ô đó có cá piranha và chúng chỉ cho Bessie đi qua nếu cô mang mùi cam.
• Nếu một ô có màu tím, Bessie sẽ trượt sang ô tiếp theo theo hướng đang đi (trừ khi cô không thể đi qua ô đó). Nếu ô tiếp theo cũng có màu tím, Bessie sẽ tiếp tục trượt cho đến khi đáp xuống một ô không màu tím hoặc đụng phải một ô không thể đi qua. Trượt qua một ô được tính là một bước di chuyển. Các ô màu tím cũng sẽ loại bỏ mùi của Bessie.

(Nếu bạn thấy các ô màu tím khó hiểu, ví dụ sẽ minh họa cách chúng hoạt động.)

Hãy giúp Bessie đi từ ô trên cùng bên trái đến ô dưới cùng bên phải với ít bước di chuyển nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), biểu thị số hàng và số cột của mê cung.

\(N\) dòng tiếp theo, mỗi dòng chứa \(M\) số nguyên biểu thị mê cung:

• Số nguyên 0 là một ô màu đỏ.
• Số nguyên 1 là một ô màu hồng.
• Số nguyên 2 là một ô màu cam.
• Số nguyên 3 là một ô màu xanh lam.
• Số nguyên 4 là một ô màu tím.

Các số nguyên ở ô trên cùng bên trái và ô dưới cùng bên phải luôn là 1.

Dữ liệu ra

In một số nguyên duy nhất biểu thị số bước di chuyển ít nhất Bessie cần để vượt qua mê cung, hoặc -1 nếu không thể làm được.

Ví dụ

4 4
1 0 2 1
1 1 4 1
1 0 4 0
1 3 1 1

10

Nguồn

USACO 2015 December Contest, Gold - Bessie's Dream: https://usaco.org/index.php?page=viewproblem2&cpid=575

Tác giả: Nathan Pinsker, inspired by the game "Undertale".