USACO 2024 - Tháng 1 - Hạng Đồng

Nông dân John đang muốn mua cỏ cho đàn bò của anh ây, tuy nhiên, do không muốn tìm mua khắp nơi, anh muốn tất cả đàn bò của mình thích chung một loại cỏ thông qua cách thao túng tâm lý chúng.

Anh nông dân có \(N\) con bò (\(2 \leq N \leq 10^5\)) được đánh số từ \(1\) đến \(N\). Do những con bò có có bệnh ba phải, khi trong một nhóm bò có hơn một nửa cùng thích một loại cỏ. Lợi dụng điều này, anh John cố ý tổ chúc những cuộc họp gồm những con bò có thứ tự từ \(i\) đến \(j\) để khiến cho toàn bộ đàn bò thích cùng loại cỏ.

Nhiệm vụ của bạn là giúp John phân tích xem loại cỏ nào có thể trở thành loại cỏ duy nhất mà cả đàn bò đều thích, biết rằng anh chỉ có thể mở một cuộc họp mỗi lần, nhưng có thể mở vô tận số cuộc họp để đạt được mục đích.

Input

• Dòng đầu tiên sẽ bao gồm một số nguyên T đại diện cho số lượng test case. (\(1 \leq T \leq 10\)).
• Dòng đầu tiên của mỗi test case bao gồm số nguyên \(N\).
• Dòng thứ hai của mỗi test case bao gồm \(N\) số nguyên, đại diện cho loại cỏ ưa thích \(h_{i}\) của những con bò thứ \(i\).
• Dữ liệu đảm bảo tổng của \(N\) của tất cả các test case không quá \(2 \times 10^{5}\).

Output

• Gồm \(T\) dòng là câu trả lời cho \(T\) test case, trong đó mỗi dòng gồm tất cả loại cỏ có thể trở thành loại cỏ yêu thích của đàn bò theo thứ tự tăng dần, hoặc -1 nếu không có loại cỏ nào phù hợp

Scoring

• Subtask \(1\): \(N = 2\).
• Subtask \(2\): \(N \leq 50\).
• Subtask \(3\): \(h_{i} \leq h_{i+1}\) với mọi \(1 \leq i \leq N - 1\).
• Subtask \(4\): Không có ràng buộc gì thêm.

5
5
1 2 2 2 3
6
1 2 3 1 2 3
6
1 1 1 2 2 2
3
3 2 3
2
2 1

2
-1
1 2
3
-1

Sau một khóa học tài năng, Bessie đã lĩnh hội được cách để biến bản thân thành một quả bóng và nảy đi. Cô thường biểu diễn cho những con bò khác trong nông trại xem trò bật nảy vào những mục tiêu trên một con đường dài được mô tả bởi trục số từ \(1\) đến \(N\). Bessie bắt đầu ở vị trí \(S\) (\(1 \leq S \leq N\)), sau đó bắt đầu bật nảy sang phía bên phải trục số với lực nhảy là \(1\). Nếu lúc đó Bessie đang có sức bật là \(k\), cú nhảy tiếp theo sẽ nhảy \(k\) đơn vị từ vị trí của cô.

Mọi vị trí nguyên từ \(1\) đến \(N\) đều là một mục tiêu hoặc một pad nhảy, và mỗi vị trí đều có giá trị phân biệt trong khoảng từ \(0\) đến \(N\). Mỗi khi Bessie nảy vào một pad nhảy, cô sẽ được tăng lực nhảy bằng với giá trị của nó và thay đổi chiều nảy, và nếu cô nảy vào một mục tiêu có giá trị \(v\) với ít nhất \(v\) lực nảy, cô sẽ phá hủy được nó. Sau khi mục tiêu bị phá hủy, nó sẽ trở thành một vị trí trống và không có hiệu ứng nếu Bessie nảy vào nó lần nữa.

Biết nếu Bessie bắt đầu ở một vị trí mục tiêu mà cô có thể phá hủy, nó sẽ bị phá hủy ngay và tương tự với pad nhảy. Nhiệm vụ của bạn là dự đoán xem Bessie có thể phá hủy bao nhiêu mục tiêu nếu cô ấy có thể nảy bao nhiêu lần tùy thích.

Input

• Dòng đầu tiên chứa \(N\) và \(S\) lần lượt đại diện cho độ dài của đoạn thẳng và vị trí bắt đầu của Bessie.
• N dòng tiếp theo mô tả các vị trí, trong đó dòng thứ \(i\) chứa các số nguyên \(q_{i}\) và \(v_{i}\) , trong đó \(q_{i}=0\) nếu vị trí \(i\) là một pad nhảy và \(q_{i}=1\) nếu vị trí \(i\) là một mục tiêu, và \(v_{i}\) là giá trị của vị trí \(i\) .

Output

• In ra một số nguyên đại diện cho số lượng mục tiêu sẽ bị phá vỡ.

Scoring

• Subtask 1: \(N \leq 100\).
• Subtask 2: \(N \leq 1000\).
• Subtask 3: Không có ràng buộc gì thêm.

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

3

Nông dân John đang thử nghiệm một cách mới để tăng năng suất trồng cỏ của mình, đó là tận dụng vi khuẩn có lợi. Tuy nhiên cái gì quá nhiều hay quá ít thì cũng không tốt nên anh đã đặt ra "mức vi khuẩn" để dễ dàng kiểm soát sự tăng trưởng của hàng cỏ của mình.

Anh John trồng hàng cỏ gồm \(N\) (\(1 \leq N \leq 2 \times 10^5\)) cụm cỏ dọc theo trục số, trong đó cụm cỏ thứ \(i\) có mức vi khuẩn chênh lệch với mức tiêu chuẩn \(a_i\). Ví dụ nếu \(a_i = -1\) thì cụm cỏ \(i\) có ít hơn mức tiêu chuẩn 1 đơn vị.

Nhiệm vụ của bạn là giúp anh John phun thuốc lên hàng cỏ, sao cho mọi cụm cỏ đều có mức vi khuẩn tiêu chuẩn bằng loại máy phun đặc biệt có thể đổi giữa tăng giảm mức vi khuẩn và mức năng lượng. Mỗi lần phun, bạn sẽ phun từ đầu bên phải của hàng cỏ đến hàng cỏ cách đó \(L\) đơn vị, thêm vào đó, cứ cụm cỏ cách bạn \(i\) thì sẽ nhận ít hơn \(N-i\) hiệu ứng tăng giảm, nghĩa là cụm cỏ ở vị trí \(N-1\) sẽ tăng 2 mức vi khuẩn nếu máy phun đang ở mức năng lượng 3.

Hãy hoàn thành công việc anh John giao cho bạn với số lần phun ít nhất có thể.

Input

• Dòng đầu tiên chứa \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_{1}...a{n}\) là mức vi khuẩn ban đầu của hàng cỏ

Output

• Gồm một số nguyên duy nhất là số lần phun ít nhất có thể để hoàn thành công việc.

Scoring

• Subtask \(1\): \(N \leq 10^{3}\), kết quả lớn nhất không quá 10^{3}.
• Subtask \(2\): \(N \leq 10^{3}\)
• Subtask \(3\): Không có ràng buộc gì thêm.

2
-1 3

6

5
1 3 -2 -7 5

26