USACO 2025 - Tháng 2 - Hạng Bạch Kim

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 USACO 2025 - Min Max Subarrays 100 (p) 4.0s 512M
2 USACO 2025 - Transforming Pairs 100 (p) 4.0s 512M
3 USACO 2025 - True or False Test 100 (p) 4.0s 512M

1. USACO 2025 - Min Max Subarrays

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Lưu ý: Giới hạn thời gian của bài này là 3 giây, bằng 1,5 lần mặc định.

Bạn được cho một mảng số nguyên độ dài \(N\) là \(a_1,a_2,\dots,a_N\) (\(2\le N\le 10^6\), \(1\le a_i\le N\)). Hãy in ra tổng đáp án của bài toán con dưới đây trên tất cả \(N(N+1)/2\) mảng con liên tiếp của \(a\).

Cho một danh sách số nguyên không rỗng, hãy luân phiên thực hiện các thao tác sau (bắt đầu bằng thao tác thứ nhất) cho đến khi danh sách có đúng một phần tử:

  1. Thay hai số nguyên liên tiếp trong danh sách bằng giá trị nhỏ nhất của chúng.
  2. Thay hai số nguyên liên tiếp trong danh sách bằng giá trị lớn nhất của chúng.

Hãy xác định giá trị lớn nhất có thể của số nguyên cuối cùng còn lại.

Ví dụ:

[4, 10, 3] -> [4, 3] -> [4]
[3, 4, 10] -> [3, 10] -> [10]

Trong mảng đầu tiên, \((10,3)\) được thay bằng \(\min(10,3)=3\) và \((4,3)\) được thay bằng \(\max(4,3)=4\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Dòng thứ hai chứa \(a_1,a_2,\dots,a_N\).

Dữ liệu ra

In ra tổng đáp án của bài toán con trên tất cả các mảng con.

Ví dụ

Ví dụ 1

Input 
2
2 1
Output 
4
Giải thích

Đáp án cho \([2]\) là \(2\), đáp án cho \([1]\) là \(1\), và đáp án cho \([2,1]\) là \(1\).

Vì vậy, kết quả cần in là \(2+1+1=4\).

Ví dụ 2

Input 
3
3 1 3
Output 
12

Ví dụ 3

Input 
4
2 4 1 3
Output 
22
Giải thích

Xét mảng con \([2,4,1,3]\).

  1. Áp dụng thao tác thứ nhất lên \((1,3)\), mảng mới là \([2,4,1]\).
  2. Áp dụng thao tác thứ hai lên \((4,1)\), mảng mới là \([2,4]\).
  3. Áp dụng thao tác thứ ba lên \((2,4)\), số cuối cùng là \(2\).

Có thể chứng minh \(2\) là giá trị lớn nhất có thể của số cuối cùng.

Phân nhóm

  • Dữ liệu 4–5: \(N\le 100\).
  • Dữ liệu 6–7: \(N\le 5000\).
  • Dữ liệu 8–9: \(\max(a)\le 10\).
  • Dữ liệu 10–13: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 February Contest, Platinum — Min Max Subarrays. Tác giả: Benjamin Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1500

2. USACO 2025 - Transforming Pairs

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Hãy trả lời \(Q\) (\(1\le Q\le 10^5\)) truy vấn độc lập, mỗi truy vấn có dạng sau:

Bạn được cho bốn số nguyên \(a,b,c,d\) (\(-10^{18}\le a,b,c,d\le 10^{18}\)). Trong một thao tác, bạn có thể thực hiện \(a\mathrel{+}=b\) hoặc \(b\mathrel{+}=a\). Hãy xác định số thao tác tối thiểu để biến đổi \((a,b)\) thành \((c,d)\); nếu không thể, in ra \(-1\).

Dữ liệu vào

Dòng đầu tiên chứa \(Q\).

\(Q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(a,b,c,d\).

Dữ liệu ra

In đáp án cho mỗi truy vấn trên một dòng riêng.

Ví dụ

Ví dụ 1

Input 
4
5 -3 -1 -3
5 3 5 2
5 3 8 19
5 3 5 3
Output 
2
-1
3
0
Giải thích

Truy vấn thứ nhất: \((5,-3)\to(2,-3)\to(-1,-3)\).

Truy vấn thứ hai: Không thể thực hiện.

Truy vấn thứ ba: \((5,3)\to(8,3)\to(8,11)\to(8,19)\).

Truy vấn thứ tư: Không cần thao tác nào.

Phân nhóm

  • Dữ liệu 2: \(|a|,|b|,|c|,|d|\le 10\).
  • Dữ liệu 3: \(a,b\ge 0\).
  • Dữ liệu 4: \(a\geq 0\geq b\).
  • Dữ liệu 5: \(a\leq 0\leq b\).
  • Dữ liệu 6: \(a,b\le 0\).
  • Dữ liệu 7: \(c,d\ge 0\).
  • Dữ liệu 8: \(c\geq 0\geq d\).
  • Dữ liệu 9: \(c\leq 0\leq d\).
  • Dữ liệu 10: \(c,d\le 0\).
  • Dữ liệu 11–14: \(Q\leq 10^3\).
  • Dữ liệu 15–19: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 February Contest, Platinum — Transforming Pairs. Tác giả: Benjamin Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1501

3. USACO 2025 - True or False Test

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Lưu ý: Giới hạn thời gian của bài này là 3 giây, bằng 1,5 lần mặc định. Giới hạn bộ nhớ của bài này là 512 MB, gấp đôi mặc định.

Bessie đang làm một bài kiểm tra đúng/sai gồm \(N\) câu (\(1\le N\le 2\cdot 10^5\)). Với câu hỏi thứ \(i\), cô nhận được \(a_i\) điểm nếu trả lời đúng, mất \(b_i\) điểm nếu trả lời sai, hoặc không được cũng không mất điểm nếu không trả lời (\(0<a_i,b_i\le 10^9\)).

Bessie biết tất cả đáp án vì cô là một cô bò thông minh, nhưng lo rằng Elsie (người coi thi) sẽ thay đổi hồi tố không quá \(k\) câu hỏi sau bài kiểm tra sao cho Bessie không trả lời đúng những câu đó.

Cho \(Q\) (\(1\le Q\le N+1\)) giá trị ứng viên của \(k\) (\(0\le k\le N\)), hãy xác định số điểm Bessie có thể đảm bảo với mỗi \(k\), biết rằng cô phải trả lời ít nhất \(k\) câu hỏi.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(Q\).

\(N\) dòng tiếp theo, mỗi dòng chứa \(a_i\) và \(b_i\).

\(Q\) dòng tiếp theo, mỗi dòng chứa một giá trị \(k\). Không giá trị \(k\) nào xuất hiện quá một lần.

Dữ liệu ra

In đáp án cho mỗi \(k\) trên một dòng riêng.

Ví dụ

Ví dụ 1

Input 
2 3
3 1
4 2
2
1
0
Output 
-3
1
7
Giải thích

Với mỗi giá trị \(k\), phương án tối ưu của Bessie là trả lời tất cả các câu hỏi.

Phân nhóm

  • Dữ liệu 2–4: \(N\le 100\).
  • Dữ liệu 5–7: \(Q\le 10\), \(N\le 2\cdot 10^5\).
  • Dữ liệu 7–20: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 February Contest, Platinum — True or False Test. Tác giả: Benjamin Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1502