Chuyến đi vượt thời gian: Chapter II (Temporal Gate To 1962)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Youtuber_TWK, doangiaphuc13
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1300 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Sau khi giải được bài toán ở Chapter I, Youtuber_TWK và doangiaphuc13 cuối cùng cũng lấy đủ năng lượng để khởi động chiếc máy thời gian được tìm thấy trong kho đồ cũ của Liên Xô.

Chiếc máy thời gian chỉ có kích thước khoảng bằng một cái đầu người, được đặt cố định trên bảng điều khiển trong toa chỉ huy.

Bên ngoài, đoàn tàu vẫn đang lao qua màn đêm.

Ánh sáng xanh bắt đầu lan ra từ chiếc máy, rồi dần bao phủ cả toa tàu.

Youtuber_TWK vui mừng:

"Được rồi! Lần này chắc chắn chúng ta về được rồi!"

Nhưng ngay khi anh vừa nói xong...

"ẦM!"

Cả đoàn tàu rung chuyển.

Một tiếng động cơ phản lực khổng lồ vang lên từ phía trên.

doangiaphuc13 chạy tới cửa sổ.

Trên bầu trời đêm, một chiếc MiG-25 đang bay với tốc độ cực lớn, song song với đoàn tàu.

"MiG-25..."

"Hình như nó đang theo dõi chúng ta."

Đúng lúc đó, chiếc máy thời gian phát ra một tiếng bíp.

Màn hình lập tức chuyển sang màu đỏ.

TEMPORAL GATE ERROR

Youtuber_TWK hoảng hốt:

"Lại chuyện gì nữa đây?!"

doangiaphuc13 nhanh chóng kiểm tra chiếc máy thời gian.

Thiết bị chỉ lớn bằng một cái đầu người nhưng bên trong chứa một hệ thống năng lượng cực kỳ phức tạp.

Sau vài phút kiểm tra, cậu phát hiện ra nguyên nhân.

Chiếc máy thời gian có hai lõi năng lượng.

Hai lõi này không thể hoạt động nếu năng lượng được phân phối quá lệch nhau.

Nói cách khác, năng lượng lấy được từ hai phía phải gần bằng nhau.

doangiaphuc13 mở những tài liệu cũ tìm thấy trong toa chỉ huy.

Trong tài liệu có một sơ đồ về hệ thống năng lượng của đoàn tàu.

Có tất cả \(n\) toa, được đánh số từ \(1\) đến \(n\).

Toa thứ \(i\) chứa \(a_i\) đơn vị năng lượng.

Nếu họ chọn các toa

\[ i_1<i_2<...<i_k \]

thì tổng năng lượng lấy được là

\[ a_{i_1}+a_{i_2}+...+a_{i_k}. \]

Họ phải chọn ít nhất hai toa.

Chi phí giữa các toa

Để lấy năng lượng từ những toa được chọn, họ phải trả thêm chi phí cho những toa bị bỏ qua giữa hai toa được chọn.

Nếu hai toa được chọn liên tiếp là \(i_j\) và \(i_{j+1}\) thì có

\[ i_{j+1}-i_j-1 \]

toa nằm giữa chúng.

Do đó, chi phí bỏ qua giữa hai toa này là

\[ i_{j+1}-i_j-1. \]

Nếu không sử dụng chế độ khẩn cấp, tổng chi phí sẽ là

\[ A+B+\sum_{j=1}^{k-1}(i_{j+1}-i_j-1)+|A-B|. \]

Chia thành hai nhóm

Các toa được chọn phải được chia thành hai nhóm liên tiếp trong thứ tự các toa được chọn.

Nếu

\[ i_1<i_2<...<i_k \]

thì phải chọn một vị trí \(p\), với

\[ 1\le p<k, \]

để

  • Nhóm thứ nhất gồm \(i_1,i_2,...,i_p\).
  • Nhóm thứ hai gồm \(i_{p+1},i_{p+2},...,i_k\).

Gọi năng lượng của hai nhóm lần lượt là

\[ A=a_{i_1}+a_{i_2}+...+a_{i_p} \]

và

\[ B=a_{i_{p+1}}+a_{i_{p+2}}+...+a_{i_k}. \]

Chiếc máy thời gian chỉ có thể hoạt động nếu

\[ |A-B|\le x. \]

Nếu hai nhóm càng lệch nhau, việc đồng bộ càng tốn nhiều chi phí.

Vì vậy, ngoài các chi phí do những toa bị bỏ qua, họ phải trả thêm

\[ |A-B|. \]

Điều kiện radar

doangiaphuc13 vừa đọc xong tài liệu thì nhìn ra ngoài cửa sổ.

Chiếc MiG-25 đã bắt đầu hạ độ cao.

"Không ổn."

"Radar đang theo dõi khoảng cách giữa các toa chúng ta chọn."

Cậu tìm thấy một thông số được ghi trong tài liệu \(d\).

Radar chỉ có thể duy trì liên lạc nếu hai toa được chọn liên tiếp có hiệu số chỉ số không vượt quá \(d\).

Do đó, với mọi cặp toa được chọn liên tiếp

\[ i_{j+1}-i_j\le d. \]

Lưu ý rằng

  • \(i_{j+1}-i_j\) là khoảng cách giữa chỉ số của hai toa.
  • Số toa thực sự bị bỏ qua giữa chúng là \(i_{j+1}-i_j-1\).

Nếu khoảng cách chỉ số lớn hơn \(d\), phương án đó không thể sử dụng.

Chế độ khẩn cấp

Youtuber_TWK vẫn chưa chịu bỏ cuộc.

Đúng lúc đó, anh phát hiện một cần gạt cũ nằm dưới bảng điều khiển.

Trên đó có một dòng chữ tiếng Nga đã bị mờ:

EMERGENCY

doangiaphuc13 lau lớp bụi.

Bên dưới dòng chữ là một ghi chú ngắn.

Trong tình huống khẩn cấp, họ có thể sử dụng chế độ khẩn cấp nhiều nhất một lần trong toàn bộ phương án.

Nếu hai toa \(i<j\) được chọn liên tiếp, bình thường phải trả

\[ j-i-1 \]

đơn vị chi phí cho các toa nằm giữa.

Nếu sử dụng chế độ khẩn cấp cho chính cặp toa này, khoản chi phí đó trở thành \(0\).

Tuy nhiên, chế độ khẩn cấp sẽ phát sinh thêm \(c\) đơn vị chi phí.

Như vậy, nếu sử dụng chế độ khẩn cấp cho cặp toa này, tổng chi phí sẽ giảm đi

\[ j-i-1 \]

nhưng tăng thêm

\[ c. \]

Điều kiện radar vẫn không thay đổi, nên cặp toa này vẫn phải thỏa mãn

\[ j-i\le d. \]

Chế độ khẩn cấp có thể

  • Không sử dụng; hoặc
  • Sử dụng đúng một lần cho một trong các cặp toa được chọn liên tiếp.

Không được sử dụng chế độ khẩn cấp nhiều hơn một lần.

MiG-25 ngày càng tiến gần.

Youtuber_TWK nhìn vào toàn bộ dãy toa.

Họ cần chọn ít nhất hai toa.

Các toa được chọn phải đủ gần để không bị radar phát hiện.

Tổng năng lượng của hai nhóm phải đủ cân bằng.

Tổng chi phí phải nằm trong giới hạn \(m\).

Nếu cần thiết, họ có thể sử dụng chế độ khẩn cấp nhiều nhất một lần.

Trong số tất cả những cách chọn hợp lệ, họ muốn lấy được càng nhiều năng lượng càng tốt.

Mô tả chính xác

Giả sử chọn

\[ i_1<i_2<...<i_k, \]

với \(k\ge2\), và chia tại vị trí \(p\), với

\[ 1\le p<k. \]

Khi đó

\[ A=a_{i_1}+...+a_{i_p} \]

và

\[ B=a_{i_{p+1}}+...+a_{i_k}. \]

Phương án chỉ hợp lệ nếu

\[ |A-B|\le x \]

và

\[ i_{j+1}-i_j\le d \]

với mọi \(1\le j<k\).

Đặt

\[ S=A+B \]

và

\[ G=\sum_{j=1}^{k-1}(i_{j+1}-i_j-1). \]

Không sử dụng chế độ khẩn cấp

Tổng chi phí là

\[ S+G+|A-B|. \]

Phương án hợp lệ nếu

\[ S+G+|A-B|\le m. \]

Sử dụng chế độ khẩn cấp

Nếu sử dụng chế độ khẩn cấp cho một cặp \(i_j,i_{j+1}\), phần chi phí

\[ i_{j+1}-i_j-1 \]

được thay bằng \(0\), đồng thời tổng chi phí tăng thêm \(c\).

Khi đó tổng chi phí là

\[ S+G-(i_{j+1}-i_j-1)+c+|A-B|. \]

Phương án hợp lệ nếu tổng chi phí không vượt quá \(m\).

Trong cả hai trường hợp, điều kiện

\[ i_{j+1}-i_j\le d \]

vẫn phải được thỏa mãn.

Yêu cầu

Hãy tìm giá trị lớn nhất của

\[ A+B \]

trong tất cả các phương án hợp lệ.

Nếu không tồn tại cách chọn ít nhất hai toa thỏa mãn tất cả các điều kiện, in ra \(0\).

Điều quan trọng là hai nhóm phải là hai đoạn liên tiếp trong dãy các toa được chọn.

Ví dụ, nếu chọn

\[ i_1<i_2<i_3<i_4<i_5 \]

thì có thể chia thành

\[ i_1\ |\ i_2,i_3,i_4,i_5 \]

hoặc

\[ i_1,i_2\ |\ i_3,i_4,i_5 \]

hoặc

\[ i_1,i_2,i_3\ |\ i_4,i_5 \]

hoặc

\[ i_1,i_2,i_3,i_4\ |\ i_5. \]

Không thể chia thành

\[ i_1,i_3\ |\ i_2,i_4,i_5. \]

Input

  • Dòng đầu tiên chứa năm số nguyên \(n,m,d,c,x\).
  • \(n\) — số lượng toa tàu.
  • \(m\) — giới hạn tổng chi phí.
  • \(d\) — khoảng cách chỉ số tối đa giữa hai toa được chọn liên tiếp.
  • \(c\) — chi phí bổ sung khi sử dụng chế độ khẩn cấp.
  • \(x\) — độ lệch năng lượng tối đa cho phép giữa hai nhóm.
  • Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n\), trong đó \(a_i\) là lượng năng lượng chứa trong toa thứ \(i\).

Output

  • In ra một số nguyên duy nhất — tổng năng lượng lớn nhất có thể lấy được.
  • Nếu không tồn tại phương án chọn ít nhất hai toa hợp lệ, in ra 0.

Example

Test 1

Input 
7 30 3 4 8
4 6 5 7 3 8 4
Output 
27
Note

Ở test này, phương án tối ưu là chọn 5 toa liên tiếp [3, 4, 5, 6, 7].

  • Năng lượng các toa tương ứng là 5, 7, 3, 8, 4.
  • Tổng năng lượng thu được là \(27\).
  • Chia thành hai nhóm:
  • \(A=5+7=12\).
  • \(B=3+8+4=15\).
  • Độ chênh lệch:
\[ |A-B|=|12-15|=3\le8. \]
  • Do các toa được chọn nằm liền kề nhau nên:
\[ G=0. \]
  • Tổng chi phí:
\[ 27+0+3=30\le m. \]
  • Khoảng cách giữa các toa liên tiếp đều bằng \(1\le d\).

Vậy phương án hợp lệ và cho ra đáp án \(27\).

Test 2

Input 
8 35 3 4 10
3 8 4 6 7 5 9 2
Output 
33
Note

Cách tối ưu là chọn các toa [3, 4, 5, 6, 7, 8].

  • Tổng năng lượng:
\[ 4+6+7+5+9+2=33. \]
  • Chia thành hai nhóm:
\[ A=4+6+7=17, \]
\[ B=5+9+2=16. \]
  • Độ chênh lệch:
\[ |A-B|=1\le10. \]
  • Các toa được chọn liền kề nhau nên \(G=0\).
  • Tổng chi phí:
\[ 33+0+1=34\le35. \]

Phương án không cần sử dụng chế độ khẩn cấp và lấy được \(33\) đơn vị năng lượng.

Ràng buộc

  • \(2\le n\le15\)
  • \(1\le m\le500\)
  • \(1\le d\le n\)
  • \(0\le c\le70\)
  • \(0\le x\le80\)
  • \(1\le a_i\le60\)
  • Đảm bảo đáp án không vượt quá \(10^{18}\).

Scoring

  • Subtask 1 (\(10\%\) điểm): \(n\le5\).
  • Subtask 2 (\(15\%\) điểm): \(n\le8,\ m\le100\).
  • Subtask 3 (\(20\%\) điểm): \(n\le10,\ d\le10\).
  • Subtask 4 (\(20\%\) điểm): \(n\le12,\ m\le300\).
  • Subtask 5 (\(35\%\) điểm): Không có giới hạn bổ sung.

Chiếc MiG-25 đã tiến sát đoàn tàu.

doangiaphuc13 nhìn đồng hồ.

"Chúng ta chỉ còn vài giây!"

Youtuber_TWK nhìn dãy số trên màn hình của chiếc máy thời gian.

Lúc này không hiểu sao nỗi buồn nặng nề trong lòng anh lại xuất hiện, kéo theo sự cô đơn và lạnh lẽo.

Những giọt nước mắt long lanh từ từ tuôn ra từ khóe mắt anh.

Nhưng để có thể trở về hiện tại và xóa đi nỗi buồn phiền ấy, anh chỉ còn cách cố gắng tìm được cách chia những toa tàu thành hai phía sao cho vừa đủ cân bằng, vừa lấy được nhiều năng lượng nhất để có thể trở về ngày ấy.

Một tiếng còi vang lên.

"BÍP!"

Radar của MiG-25 đã khóa mục tiêu.

5...

4...

Khi Youtuber_TWK vẫn còn đang lưỡng lự vì nỗi buồn thất tình chưa thể phai nhòa trong tim anh, doangiaphuc13 đã nhanh chóng kéo cần khẩn cấp.

3...

Youtuber_TWK lau nước mắt rồi nhập đáp án vào hệ thống điều khiển chính.

2...

Động cơ của chiếc MiG-25 gầm lên.

1...

"ẦM!!!"

Chiếc máy thời gian phát sáng rực rỡ.

Ánh sáng từ thiết bị nhỏ bằng một cái đầu người nhanh chóng lan ra khắp toa chỉ huy.

Rồi xuyên qua toàn bộ đoàn tàu.

Cả đoàn tàu rung chuyển dữ dội.

Một luồng sáng trắng bao phủ toàn bộ đoàn tàu.

Mọi thứ xung quanh dần trở nên mờ đi.

Tiếng động cơ của chiếc MiG-25 biến mất.

Tiếng rung chuyển của đoàn tàu cũng dần chìm vào im lặng.

Chỉ còn tiếng máy thời gian vang lên trong toa chỉ huy.

TEMPORAL JUMP INITIATED

CALCULATING DESTINATION...

Những con số trên màn hình liên tục thay đổi.

YEAR: 1962

LOCATION: CUBA

DATE: OCTOBER 1962

doangiaphuc13 nhìn màn hình nhưng chưa kịp nói gì.

"BÍP!"

TEMPORAL COORDINATES: LOCKED

TEMPORAL JUMP: COMPLETE

Một luồng sáng mạnh lóe lên.

Cả đoàn tàu rung lên lần cuối.

Rồi

Mọi thứ trở nên yên tĩnh.

Ánh sáng trắng từ từ tan đi.

Chiếc máy thời gian vẫn phát sáng trên bảng điều khiển.

TEMPORAL JUMP: SUCCESS

LOCATION: CUBA

DATE: OCTOBER 1962

Youtuber_TWK từ từ mở mắt.

Anh nhìn quanh.

Nhưng lần này, trước mắt anh không còn là toa chỉ huy.

Cả hai đang ở trong một căn nhà cũ.

Những bức tường đã phủ đầy bụi.

Một chiếc bàn gỗ cũ nằm giữa căn phòng.

Cảnh vật bên ngoài cửa sổ đã hoàn toàn thay đổi.

doangiaphuc13 nhìn ra ngoài cửa sổ.

Cậu im lặng vài giây.

Youtuber_TWK cũng nhìn theo.

Chiếc máy thời gian vẫn phát sáng trên chiếc bàn gỗ.

Màn hình hiện rõ:

TEMPORAL DESTINATION: CUBA — 1962

Youtuber_TWK nhìn dòng chữ trên màn hình.

Anh khẽ nói:

"Vậy là chúng ta thật sự đã quay về năm 1962."

Cả hai tiếp tục nhìn quanh căn phòng xa lạ.

Họ đã đến một nơi hoàn toàn khác.

Cuba — tháng 10 năm 1962.

Câu chuyện vẫn chưa kết thúc!!!!

Chuyến đi vượt thời gian: Chapter III — Tempest Over Cuba 1962

Bình luận (13)

Mới nhất
Tải bình luận...