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

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 - Cowdependence 100 (p) 4.0s 512M
2 USACO 2025 - Interstellar Intervals 100 (p) 4.0s 512M
3 USACO 2025 - Job Completion 100 (p) 4.0s 512M

1. USACO 2025 - Cowdependence

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

\(N\) (\(1\leq N\leq 10^5\)) cô bò của Farmer John được xếp thành một hàng. Cô bò thứ \(i\) có nhãn \(a_i\) (\(1\leq a_i\leq N\)). Một nhóm bò có thể tạo thành một nhóm bạn nếu tất cả có cùng nhãn và mỗi cô bò cách mọi cô bò khác trong nhóm không quá \(x\) cô bò, trong đó \(x\) là một số nguyên thuộc \([1,N]\). Mỗi cô bò phải thuộc đúng một nhóm bạn.

Với mỗi \(x\) từ \(1\) đến \(N\), hãy tính số nhóm bạn nhỏ nhất có thể được tạo thành.

Dữ liệu vào

Dòng đầu chứa một số nguyên \(N\).

Dòng tiếp theo chứa \(a_1\dots a_N\), là nhãn của từng cô bò.

Dữ liệu ra

Với mỗi \(x\) từ \(1\) đến \(N\), in trên một dòng mới số nhóm bạn nhỏ nhất ứng với \(x\) đó.

Phân nhóm

  • Các test 2–3: \(N\leq 5000\).
  • Các test 4–7: \(a_i\leq 10\) với mọi \(i\).
  • Các test 8–11: Không nhãn nào xuất hiện quá \(10\) lần.
  • Các test 12–20: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
9
1 1 1 9 2 1 2 1 1
Output 
7
5
4
4
4
4
4
3
3
Giải thích

Dưới đây là các ví dụ về cách phân bò vào các nhóm bạn khi \(x=1\) và \(x=2\) sao cho số nhóm là nhỏ nhất. Mỗi chữ cái tương ứng với một nhóm khác nhau.

       1 1 1 9 2 1 2 1 1
x = 1: A B B C D E F G G (7 nhóm)
x = 1: A A B C D E F G G (7 nhóm, một cách chia khác)
x = 2: A A A B C D C E E (5 nhóm)
x = 2: A A A B C D C D E (5 nhóm, một cách chia khác)

Nguồn

Đề bài gốc: USACO 2024 December Contest, Gold — Cowdependence

Tác giả: Chongtian Ma.

2. USACO 2025 - Interstellar Intervals

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

Năm nay là năm \(3000\), và Bessie đã trở thành cô bò đầu tiên bay vào vũ trụ! Trong hành trình giữa các vì sao, cô tìm thấy một trục số có \(N\) (\(2\leq N\leq 5\cdot 10^5\)) điểm, được đánh số từ \(1\) đến \(N\). Ban đầu mọi điểm đều có màu trắng. Cô có thể thực hiện thao tác sau tùy ý số lần:

  • Chọn một vị trí \(i\) trên trục số và một số nguyên dương \(x\). Sau đó tô đỏ tất cả các điểm trong đoạn \([i,i+x-1]\) và tô xanh dương tất cả các điểm trong đoạn \([i+x,i+2x-1]\). Tất cả các đoạn được chọn phải không giao nhau (nghĩa là không điểm nào trong \([i,i+2x-1]\) đã được tô đỏ hoặc xanh dương). Toàn bộ đoạn cũng phải nằm trên trục số (nghĩa là \(1\leq i\leq i+2x-1\leq N\)).

Farmer John đưa cho Bessie một xâu \(s\) độ dài \(N\) gồm các ký tự \(R\), \(B\) và \(X\). Xâu biểu diễn yêu cầu màu của Farmer John đối với từng điểm: \(s_i=R\) nghĩa là điểm thứ \(i\) phải được tô đỏ, \(s_i=B\) nghĩa là điểm thứ \(i\) phải được tô xanh dương, còn \(s_i=X\) nghĩa là không có ràng buộc về màu của điểm thứ \(i\).

Hãy giúp Bessie đếm số cách tô màu khác nhau cho trục số mà thỏa mãn các yêu cầu của Farmer John. Hai cách tô màu khác nhau nếu có ít nhất một điểm tương ứng mang màu khác nhau. Vì đáp án có thể rất lớn, hãy in nó theo modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu chứa một số nguyên \(N\).

Dòng tiếp theo chứa xâu \(s\).

Dữ liệu ra

In số cách tô màu khác nhau cho trục số thỏa mãn các yêu cầu của Farmer John, theo modulo \(10^9+7\).

Phân nhóm

  • Test 4: \(N\leq 500\).
  • Các test 5–6: \(N\leq 10^4\).
  • Các test 7–13: Ngoại trừ nhiều nhất \(100\) ký tự, mọi ký tự trong \(s\) đều là \(X\).
  • Các test 14–23: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
6
RXXXXB
Output 
5
Giải thích

Bessie có thể chọn \(i=1,x=1\) (tức tô điểm \(1\) màu đỏ và điểm \(2\) màu xanh dương) và \(i=3,x=2\) (tức tô các điểm \(3,4\) màu đỏ và các điểm \(5,6\) màu xanh dương) để tạo ra cách tô màu \(RBRRBB\).

Các cách tô màu còn lại là \(RRBBRB\), \(RBWWRB\), \(RRRBBB\) và \(RBRBRB\).

Ví dụ 2

Input 
6
XXRBXX
Output 
6
Giải thích

Sáu cách tô màu là \(WWRBWW\), \(WWRBRB\), \(WRRBBW\), \(RBRBWW\), \(RBRBRB\) và \(RRRBBB\).

Ví dụ 3

Input 
12
XBXXXXRXRBXX
Output 
18

Nguồn

Đề bài gốc: USACO 2024 December Contest, Gold — Interstellar Intervals

Tác giả: Chongtian Ma, Alex Liang.

3. USACO 2025 - Job Completion

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

Bessie có \(N\) công việc (\(1\leq N\leq 2\cdot 10^5\)) mà bạn có thể lựa chọn hoàn thành. Nếu chọn hoàn thành công việc thứ \(i\), bạn phải bắt đầu nó vào hoặc trước thời điểm \(s_i\) và cần \(t_i\) đơn vị thời gian để hoàn thành (\(0\leq s_i\leq 10^{18}\), \(1\leq t_i\leq 10^{18}\)).

Số công việc tối đa bạn có thể hoàn thành là bao nhiêu? Thời gian bắt đầu từ \(0\). Sau khi bắt đầu một công việc, bạn phải làm liên tục đến khi hoàn thành và không được bắt đầu công việc nào khác trong lúc đó.

Dữ liệu vào

Dòng đầu chứa \(T\), số bộ test độc lập (\(1\leq T\leq 10\)). Mỗi bộ test có định dạng như sau.

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

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(s_i\) và \(t_i\). Dòng thứ \(i+1\) chứa thông tin của công việc thứ \(i\).

Đảm bảo tổng \(N\) trên tất cả các bộ test không vượt quá \(3\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ test, in trên một dòng mới số công việc tối đa bạn có thể hoàn thành.

Phân nhóm

  • Test 2: Trong cùng một bộ test, tất cả \(t_i\) bằng nhau.
  • Các test 3–4: \(N\leq 2000\), \(s_i,t_i\leq 2000\).
  • Các test 5–8: \(N\leq 2000\).
  • Các test 9–16: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

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

Với bộ test đầu tiên, bạn chỉ có thể hoàn thành một công việc. Sau khi hoàn thành một công việc, thời gian đã là \(2\) hoặc muộn hơn, nên đã quá trễ để bắt đầu công việc còn lại, vốn phải được bắt đầu vào thời điểm \(1\) hoặc sớm hơn.

Với bộ test thứ hai, bạn có thể bắt đầu công việc thứ hai tại thời điểm \(0\) và hoàn thành tại thời điểm \(2\), sau đó bắt đầu công việc thứ nhất tại thời điểm \(2\) và hoàn thành tại thời điểm \(5\).

Nguồn

Đề bài gốc: USACO 2024 December Contest, Gold — Job Completion

Tác giả: Benjamin Qi.