Thoát khỏi tháp ngục
Đề bài
Mô tả
Sau một trận chiến dài, Ác mộng cuối cùng của tòa tháp ngục thần thánh đã bị hạ gục, và con đường để các Huyết Thiếu nữ (Blood Maidens) cùng bạn bè thoát khỏi nhà ngục dưới lòng đất đã mở ra.
Khi mọi người đã thu xếp xong hành lý, đã đến lúc lên đường. Được biết đến là người nhanh nhẹn nhất, Cinderella được giao nhiệm vụ dẫn đầu cuộc rời khỏi tòa tháp mà cô và bạn bè vừa chinh phục.
Tòa tháp ngục giờ đã biến dạng, gồm hành lang nối với nhau thành một chuỗi: với , hành lang thứ chỉ tiếp giáp hành lang thứ và hành lang thứ . Hành lang thứ dài đơn vị, và hai hành lang kề nhau luôn vuông góc với nhau. Ở cuối hành lang cuối cùng có một lối ra.
Để di chuyển nhanh nhất có thể (không chỉ cho cô mà cho cả mọi người), Cinderella có khả năng chạy nước rút từng được gọi là "Twelve Dash". Qua nhiều năm luyện tập, giờ đây nó đã trở thành khả năng tùy chỉnh mang tên "-dash", đặc trưng bởi một số nguyên dương . Khả năng này hoạt động như sau:
- Mỗi giây, Cinderella và bạn bè chạy được đơn vị độ dài.
- Nếu trong một giây nào đó, Cinderella chạm tới cuối một hành lang mà chưa chạy được đúng đơn vị độ dài, cô dừng lại ở cuối hành lang và bị trễ thêm một giây, vì cú va vào tường hoặc vào lối ra làm cả nhóm hơi rối loạn và họ cần giây đó để chỉnh đốn lại đội hình.
- Mỗi khi tới cuối một hành lang và không bị choáng (hoặc đã hồi phục hoàn toàn sau khi bị choáng), Cinderella và bạn bè quay sang hướng của hành lang tiếp theo và chuẩn bị chạy tiếp, hoặc thoát ra ngoài nếu đã tới lối ra. Hành động này mất giây.
Giá trị không thể thay đổi khi cô đã bắt đầu chạy, nhưng cô có thể chọn tùy ý trước đó. Cinderella muốn biết mình có thể thoát khỏi mê cung nhanh nhất là bao lâu, nhưng tâm trí cô đang mải mê với chiếc mặt dây chuyền thủy tinh nên không thể tính toán phức tạp lúc này. Bạn hãy giúp cô nhé!
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (): số bộ test. Mỗi bộ test gồm:
- Dòng đầu tiên chứa số nguyên (): số hành lang của mê cung.
- Dòng thứ hai chứa số nguyên (): độ dài các hành lang.
Tổng trên tất cả các bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, in ra một số nguyên: thời gian nhỏ nhất (tính bằng giây) để Cinderella và bạn bè thoát khỏi mê cung, khi cô được chọn giá trị bất kỳ trước khi xuất phát.
Ràng buộc
- , tổng không vượt quá
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 6 12 24 9 12 6 12 4 27 12 38 36 |
9 7 |
Bộ test thứ nhất: chọn . Các hành lang dài được chạy hết bằng lần chạy đủ đơn vị; mỗi hành lang dài và cần một lần chạy và bị trễ một giây. Tổng cộng lần chạy và giây trễ, tức giây. |
| 2 3 4 8 8 5 10 2 4 6 8 |
4 9 |
Bộ test thứ nhất: chọn ; hành lang dài tốn giây, mỗi hành lang dài tốn giây. Bộ test thứ hai: chọn ; hành lang dài tốn giây, mỗi hành lang còn lại tốn giây. |
Bình luận