USACO 2024 US Open Contest, Platinum, Activating Robots

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
huyhoang2006
Dạng bài
Điểm: 1000 (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

Bình luận

Không có bình luận nào.