USACO 2024 - Tháng 1 - Hạng Bạc

Nông dân John đang tuyển thêm bò đầu đàn cho đàn bò của mình. Sau khi phỏng vấn, anh ta chấm điểm cho những con bò ứng viên theo thang điểm gọi là "cowmpetency", hay còn gọi là "độ bảnh bò" cho mỗi con bò. Số điểm này dao động từ \(1\) đến \(C\) (\(1 \leq C \leq 10^9\)), với \(C\) là độ bảnh mà John mong muốn con bò đầu đàn của mình có được.

Do đã mệt mỏi sau khi phải phỏng vấn \(N\) con bò được đánh số từ \(1\) đến \(N\) (\(2 \leq N \leq 10^9\)), anh John đã quên mất độ bảnh của những con bò ứng viên. Tuy nhiên, anh vẫn nhớ được \(Q\) (\(1 \leq Q \leq \text{ min(N - 1,100)}\)) cặp số (\(a_1, a_h\)), trong đó bò \(h_1\) là con bò bảnh nhất trong dãy từ bò 1 đến bò \(a_i\) (vậy \(1 \leq a_i < h_i \leq N\)).

Anh John cho bạn biết bảng điểm của những con bò dưới dạng một dãy \(c_1, \ldots, c_N\) (với \(c_i\) = 0 nghĩa là anh John đã quên mất độ bảnh bò của con bò có số thứ tự \(i\)). Nhiệm vụ của bạn là giúp anh John nhớ lại bảng điểm nhỏ nhất theo thứ tự từ điển bằng những thông tin đã có. Biết một dãy điểm sẽ nhỏ hơn một dãy khác nếu tại điểm khác biệt nhỏ nhất có của dãy này nhỏ hơn.

Anh John đã phỏng vấn tất cả \(T\) (\(1 \leq T \leq 20\)) ngày và cần bạn giúp đỡ ngay lạp tức. Dữ liệu đảm bảo tổng số bò của cả \(T\) ngày không quá \(3 \times 10^5\).

Input

• Dòng đầu tiên chứa \(T\) là số câu hỏi anh John đặt ra cho bạn.
• Mỗi câu hỏi bao gồm:
  • Dòng đầu tiên gồm \(N\), \(Q\) và \(C\).
  • Dòng tiếp theo gồm \(c_1, \ldots, c_N\) là bảng điểm của những con bò
  • Cuối cùng là \(Q\) dòng, mỗi dòng chứa một cặp (\(a_j, h_j\)). Dữ liệu đảm bảo mỗi \(a_j\) đều độc lập.

Output

• Gồm \(T\) dòng, mỗi dòng chứa kết quả của một bài toán, hoặc -1 nếu không có kết quả nào phù hợp.

Scoring

• Subtask \(1\): \(N \leq 10\) và \(Q,C \leq 4\)
• Subtask \(2\): \(N \leq 1000\)
• Subtask \(3\): Không có ràng buộc gì thêm.

1
7 3 5
1 0 2 3 0 4 0
1 2
3 4
4 5

1 2 2 3 4 4 1

5
7 6 10
0 0 0 0 0 0 0
1 2
2 3
3 4
4 5
5 6
6 7
8 4 9
0 0 0 0 1 6 0 6
1 3
6 7
4 7
2 3
2 1 1
0 0
1 2
10 4 10
1 2 0 2 1 5 8 6 0 3
4 7
1 2
5 7
3 7
10 2 8
1 0 0 0 0 5 7 0 0 0
4 6
6 9

1 2 3 4 5 6 7
1 1 2 6 1 6 7 6
-1
1 2 5 2 1 5 8 6 1 3
-1

Một tựa game mới ra đang làm bạn say mê. Trong game, bạn phải đi thu thập những bình thuốc tăng sức mạnh để đánh bại con boss ẩn "Bò thần"

Bạn đã sử dụng kĩ năng dò đường siêu hiếm và đã có được bản đồ của game dưới dạng một dãy \(N\) căn phòng (\(2 \leq N \leq 10^5\)) được đánh số từ \(1\) đến \(N\) và được kết nối bởi \(N - 1\) cạnh tạo thành một cây.

Bạn có thể sử dụng kĩ năng "bước nhảy không gian" để di chuyển giữa các phòng, trong đó mỗi bước nhảy là một lần dịch chuyển từ phòng bất kì đến phòng số 1. Sau khi hoàn thành một lần khám phá bạn sẽ dịch chuyển thẳng về phòng số 1 để tiết kiệm thời gian. Kĩ năng này tuy mạnh nhưng bị giới hạn số lần dùng, nên bạn muốn hoàn thành map và mở khóa cánh cửa đến boss sau khi dịch chuyển ít nhất có thể. Map sẽ được clear nếu bạn đi qua một căn phòng ít nhất một lần.

Cùng với đó, để nhân vật mạnh nhất có thể, bạn cần phải thu thập càng nhiều potion càng tốt. Biết mỗi lần bạn dịch chuyển, map sẽ được làm mới và một lọ potion sẽ xuất hiện ở một căn phòng ngẫu nhiên và bạn chỉ có thể lấy được nó ở lần khám phá tiếp theo, nếu không nó sẽ biến mất.

Bằng cách "ghé thăm" thư mục của game, bạn đã "tình cờ" biết được vị trí mà những potion sẽ xuất hiện trong \(N\) lần dịch chuyển tiếp theo của bạn. Hãy tính toán xem nếu bạn clear map với số lần dịch chuyển ít nhất thì sẽ thu thập được số lượng potion tối đã là bao nhiêu.

Input:

• Dòng đầu tiên chứa một số nguyên \(N\), đại diện cho số phòng có trên bản đồ.
• Dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách \(p_1, p_2, \ldots, p_N\), với \(p_i\) là phòng mà potion sẽ xuất hiện trong lần dịch chuyển thứ \(i\).
• \(N-1\) dòng tiếp theo chứa 2 số nguyên \(a\) và \(b\) (\(1 \leq a,b \leq N\)) mô tả các con đường nối giữa các phòng. Dữ liệu đảm bảo những con đường này luôn tạo thành một cây.

Output:

• Chứa một số nguyên duy nhất là số lượng potion tối đa bạn có thể lấy được sau khi clear map nhanh nhất có thể.

Scoring:

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

5
5 4 3 2 1
1 2
1 3
3 4
3 5

2

Bessie tỉnh dậy trên một hành tinh xa lạ. Trên hành tinh này có \(N\) (\(1\le N\le 10^4\)) tháng, lần lượt có \(a_1,\ldots,a_N\) ngày (\(1\leq a_i\leq 4\cdot 10^9\), mọi \(a_i\) đều là số nguyên). Ngoài ra còn có tuần, mỗi tuần dài \(L\) ngày, trong đó \(L\) là một số nguyên dương. Điều thú vị là Bessie biết rằng:

• Với giá trị \(L\) đúng, mỗi tháng dài ít nhất \(4\) tuần.
• Với giá trị \(L\) đúng, có nhiều nhất \(3\) giá trị phân biệt trong các số \(a_i\bmod L\).

Không may, Bessie đã quên mất \(L\)! Hãy giúp cô bằng cách in tổng của tất cả các giá trị \(L\) có thể.

Lưu ý rằng các số nguyên lớn trong bài có thể đòi hỏi kiểu số nguyên 64 bit (ví dụ long long trong C/C++).

Dữ liệu vào

Dòng đầu chứa một số nguyên \(N\). Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách, \(a_1,\ldots,a_N\).

Dữ liệu ra

In một số nguyên: tổng của tất cả các giá trị \(L\) có thể.

Ví dụ

12
31 28 31 30 31 30 31 31 30 31 30 31

28

4
31 35 28 29

23

Phân nhóm

• Các test 3-4: \(1 \leq a_i \leq 10^6\).
• Các test 5-14: Không có ràng buộc bổ sung.

Nguồn

USACO 2024 January Contest, Silver — Cowlendar: https://usaco.org/index.php?page=viewproblem2&cpid=1376

Tác giả đề: Brandon Wang