USACO 2024 - US Open - 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 2024 US Open Contest, Platinum, Identity Theft 100 (p) 3.0s 512M
2 USACO 2024 US Open Contest, Platinum, Splitting Haybales 100 (p) 2.0s 0B
3 USACO 2024 US Open Contest, Platinum, Activating Robots 100 (p) 2.0s 256M

1. USACO 2024 US Open Contest, Platinum, Identity Theft

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

Anh nông dân John có \(N\) con bò, mỗi con bò có một mã định danh khác nhau được viết dưới dạng chuỗi bit (chuỗi được tạo thành từ 2 loại kí tự '0' và '1'). Bessie là cô bò lớn tuổi nhất, cô nhớ mã định danh của tất cả con bò khác và thích đi lại trong trang trại để hỏi về mã định danh của chúng.

Khi một con bò được hỏi về mã định danh, nó sẽ bắt đầu trả lời chuỗi bit định danh của mình, tuy nhiên nó có thể quên phần sau của chuỗi và dừng lại trước khi trả lời đủ mã định danh của mình. Mỗi khi Bessie nghe được một chuỗi bit, nếu đó không phải là mã định danh của bất kỳ con bò nào trên trang trại, thì cô ấy sẽ nhún vai và đi khỏi. Tuy nhiên, nếu đó vô tình là mã định danh của một con bò khác mà không phải con bò cô ấy đang hỏi, thì cô ấy sẽ cho rằng đã xảy ra hành vi đánh cắp danh tính và đưa trang trại vào tình trạng phong tỏa. Lưu ý rằng điều này có thể xảy ra ngay cả khi con bò nói đầy đủ mã định danh của nó.

John cảm thấy mệt mỏi vì tình trạng này nên muốn ngăn chặn nó xảy ra. Anh sẵn sàng thay đổi mã định danh của các con bò bằng cách thêm một số bit vào đó. Trong một giây, anh có thể thêm một bit vào cuối mã định danh của bất kỳ con bò nào. Hãy tính toán thời gian ít nhất để anh ngăn chặn được việc phong tỏa trang trại.

Input

  • Dòng đầu tiên chứa \(N\), là số lượng con bò trên trang trại của nông dân John.
  • \(N\) dòng tiếp theo, dòng thứ \(k\) chứa một chuỗi bit là mã định danh của con bò thứ \(k\).
  • Dữ liệu đảm bảo không có mã định danh nào là chuỗi rỗng và tổng dộ dài của tất cả mã định danh không quá \(10^6\).

Output

  • Gồm một số tự nhiên duy nhất là số giây tối thiểu mà John cần dành ra để đảm bảo rằng việc phong tỏa sẽ không bao giờ xảy ra.

Scoring

  • Subtask \(1\): Tất cả các mã định danh có độ dài chính xác là \(1\).
  • Subtask \(2\): \(N \leq 10^2\) và tổng độ dài của các mã định danh không vượt quá \(10^3\).
  • Subtask \(3\): Không có ràng buộc gì thêm.

Example

Test 1

Input 
3
1
1
1
Output 
5
Note

  • Chúng ta có thể ngăn chặn khóa trang trại trong \(5\) giây bằng cách thêm \('0'\) vào mã định danh đầu tiên, \('10'\) vào mã định danh thứ hai và \('11'\) vào mã định danh thứ ba, tạo thành các mã định danh \('10'\), \("110'\) và \('111'\).

  • Điều này không thể được thực hiện trong \(4\) giây hoặc ít hơn. Ví dụ, nếu bạn để nguyên các mã định danh, thì cả ba con bò đều có cùng mã định danh \('1'\), vì vậy khi Bessie nghe thấy, nó sẽ luôn là mã định danh của một con bò khác.

  • Một ví dụ khác, nếu bạn chỉ mất \(2\) giây để thêm \('0'\) vào mã định danh thứ hai và \('1'\) vào mã định danh thứ ba, thì các mã định danh là \('1'\), \('10'\) và \('11'\), với con bò thứ hai và thứ ba, khi nói mã định danh của chúng, có thể dừng ở giữa và chỉ nói \('1'\), đó sẽ là mã định danh của con bò đầu tiên.

Test 2

Input 
3
1
11
111
Output 
2
Note
  • Chúng ta có thể ngăn chặn khóa trang trại trong \(2\) giây bằng cách thêm \('0'\) vào hai mã định danh đầu tiên, tạo thành các mã định danh \('10'\), \('110'\) và \('111'\).

Test 3

Input 
3
1
1
11
Output 
4
Note
  • Chúng ta có thể ngăn chặn khóa trang trại trong \(4\) giây bằng cách thêm \('00'\) vào mã định danh đầu tiên và \('01'\) vào mã định danh thứ hai. Điều này không thể được thực hiện trong \(3\) giây hoặc ít hơn.

Test 4

Input 
5
0
01
0011
010
01
Output 
6

Test 5

Input 
14
0
1
1
0
1
0
1
1
1
1
1
0
0
1
Output 
41
Note
  • Ví dụ này thỏa mãn ràng buộc của subtask đầu tiên.

2. USACO 2024 US Open Contest, Platinum, Splitting Haybales

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

Nông dân John muốn chia đều cỏ giữa hai con bò yêu thích của mình là Bessie và Elsie. Anh có \(N\) (\(1 \leq N \leq 2 \times 10^5\)) bó cỏ được sắp xếp theo thứ tự không tăng dần, trong đó bó cỏ thứ \(i\) có \(a_i\) cọng cỏ (\(2 \times 10^5 \geq a_1 \geq a_2 \geq ... \geq a_N \geq1\)).

Nông dân John đang nghĩ đến chuyện chia những bó cỏ một cách lần lượt cho hai con bò, cụ thể như sau:

  • Nông dân John chia các bó cỏ theo đúng thứ tự từ \(l\) đến \(r\) trong kho cỏ cho trước.
  • Với bó cỏ thứ \(i\), anh John sẽ đưa cho con bò có ít cỏ hơn. Nếu 2 con bò cố lượng cỏ bằng nhau, anh John sẽ đưa cho Bessie.

Bạn được cho Q truy vấn (\(1 \leq Q \leq 2 \times 10^5\)), mỗi truy vấn gồm 3 số nguyên \(l, r, x\) (\(1 \leq l \leq r \leq N, |x| \leq 10^9\)). Với mỗi truy vấn, bạn cần tìm xem Bessie sẽ có nhiều hơn Elsie bao nhiêu cọng cỏ, biết Bessie ban đầu có nhiều hơn Elsie \(x\) cọng cỏ. Lưu ý rằng giá trị này âm nếu Elsie có nhiều cỏ hơn Bessie.

Input

  • Dòng đầu tiên chứa \(N\).
  • Dòng thứ hai chứa \(a_1…a_N\).
  • Dòng thứ ba chứa \(Q\).
  • \(Q\) dòng tiếp theo chứa \(l, r, x\).

Output

  • Gồm \(Q\) dòng, mỗi dòng chứa câu trả lời cho mỗi truy vấn.

Scoring

  • Subtask \(1\): \(Q \leq 100\)
  • Subtask \(2\): Tối đa \(100\) giá trị \(a_i\) khác nhau
  • Subtask \(3\): Không có ràng buộc gì thêm.

Example

Test 1

Input 
2
3 1
15
1 1 -2
1 1 -1
1 1 0
1 1 1
1 1 2
1 2 -2
1 2 -1
1 2 0
1 2 1
1 2 2
2 2 -2
2 2 -1
2 2 0
2 2 1
2 2 2
Output 
1
2
3
-2
-1
0
1
2
-1
0
-1
0
1
0
1
Note
  • Đối với truy vấn đầu tiên, Elsie ban đầu có nhiều hơn Bessie \(2\) cọng cỏ. Sau đó, sau khi xử lý bó cỏ thứ \(1\), Bessie sẽ nhận được \(3\) cọng cỏ, và Bessie sẽ có nhiều hơn Elsie \(1\) cọng cỏ.
  • Đối với truy vấn thứ \(3\), Elsie và Bessie ban đầu có cùng số lượng cỏ. Sau khi xử lý bó cỏ thứ \(1\), Bessie sẽ nhận được \(3\) cọng cỏ, và Bessie sẽ có nhiều hơn Elsie \(3\) cọng cỏ.
  • Đối với truy vấn thứ \(9\), Bessie ban đầu có nhiều hơn Elise \(1\) cọng cỏ. Sau khi xử lý bó cỏ thứ \(1\), Bessie có ít hơn Elsie \(2\) cọng cỏ, và sau khi xử lý bó cỏ thứ \(2\), Bessie có ít hơn Elsie \(1\) cọng cỏ.

Test 2

Input 
5
4 4 3 1 1
7
1 1 20
1 2 20
1 5 20
1 1 0
1 5 0
1 4 0
3 5 2
Output 
16
12
7
4
1
2
1
Note
  • Trong truy vấn thứ \(5\), có \(5\) bó cỏ. Bessie nhận được \(4\) cọng cỏ, sau đó Elsie nhận được \(4\) cọng cỏ, sau đó Bessie nhận được \(3\) cọng cỏ, sau đó Elsie nhận được \(1\) cọng cỏ, sau đó Elsie nhận được \(1\) cọng cỏ.

3. USACO 2024 US Open Contest, Platinum, Activating Robots

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

Bạn và một robot ban đầu đứng tại điểm \(0\) trên một vòng tròn có chu vi \(L\) (\(1 \leq L \leq 10^9\)). Bạn có thể di chuyển liên tục theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ trên vòng tròn với tốc độ \(1\) đơn vị trên giây. Tất cả các chuyển động trong bài toán này là liên tục.

Mục tiêu của bạn là đặt thêm \(R-1\) robot sao cho đến cuối cùng, mọi cặp robot liền kề cách nhau \(L/R\) đơn vị (\(2 \leq R \leq 20\), \(R\) chia hết cho \(L\)). Có \(N\) (\(1 \leq N \leq 10^5\)) điểm kích hoạt, điểm thứ \(i\) cách điểm \(0\) một khoảng \(a_i\) theo chiều ngược kim đồng hồ (\(0 < a_i < L\)). Nếu bạn đang ở tại một điểm kích hoạt, bạn có thể đặt một robot tại đó. Tất cả các robot (kể cả robot ban đầu) di chuyển ngược chiều kim đồng hồ liên tục với tốc độ \(1\) đơn vị trên \(K\) giây (\(1 \leq K \leq 10^9\)).

Hãy tính toán thời gian tối thiểu cần thiết để đạt được mục tiêu.

Input

  • Dòng đầu tiên chứa \(L\), \(R\), \(N\), và \(K\).
  • Dòng tiếp theo chứa \(N\) số nguyên \(a_1, a_2, ..., a_N\) cách nhau bởi dấu cách.

Output

  • Gồm một số duy nhất là thời gian ngắn nhất để đạt được mục tiêu đặt ra.

Scoring

  • Subtask \(1\): Tất cả các mã định danh có độ dài chính xác là \(1\).
  • Subtask \(2\): \(N \leq 10^2\) và tổng độ dài của các mã định danh không vượt quá \(10^3\).
  • Subtask \(3\): Không có ràng buộc gì thêm.

Example

Test 1

Input 
10 2 1 2
6
Output 
22
Note

  • Chúng ta có thể đến điểm kích hoạt tại \(6\) trong \(4\) giây bằng cách đi theo chiều kim đồng hồ. Lúc này, robot ban đầu sẽ ở vị trí \(2\). Chờ thêm \(18\) giây nữa cho đến khi robot ban đầu ở vị trí \(1\). Bây giờ chúng ta có thể đặt một robot để ngay lập tức hoàn thành mục tiêu.

  • Điều này không thể được thực hiện trong \(4\) giây hoặc ít hơn. Ví dụ, nếu bạn để nguyên các mã định danh, thì cả ba con bò đều có cùng mã định danh \('1'\), vì vậy khi Bessie nghe thấy, nó sẽ luôn là mã định danh của một con bò khác.

  • Một ví dụ khác, nếu bạn chỉ mất \(2\) giây để thêm \('0'\) vào mã định danh thứ hai và \('1'\) vào mã định danh thứ ba, thì các mã định danh là \('1'\), \('10'\) và \('11'\), với con bò thứ hai và thứ ba, khi nói mã định danh của chúng, có thể dừng ở giữa và chỉ nói \('1'\), đó sẽ là mã định danh của con bò đầu tiên.

Test 2

Input 
10 2 1 2
7
Output 
4
Note
  • Chúng ta có thể ngăn chặn khóa trang trại trong \(2\) giây bằng cách thêm \('0'\) vào hai mã định danh đầu tiên, tạo thành các mã định danh \('10'\), \('110'\) và \('111'\).

Test 3

Input 
32 4 5 2
0 23 12 5 11
Output 
48

Test 4

Input 
24 3 1 2
16
Output 
48