trang chủ / đề bài / icpc24_reg_k

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 n hành lang nối với nhau thành một chuỗi: với 1<i<n, hành lang thứ i chỉ tiếp giáp hành lang thứ i−1 và hành lang thứ i+1. Hành lang thứ i dài ai đơ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 "m-dash", đặc trưng bởi một số nguyên dương m. Khả năng này hoạt động như sau:

  • Mỗi giây, Cinderella và bạn bè chạy được m đơ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 m đơ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 0 giây.

Giá trị m không thể thay đổi khi cô đã bắt đầu chạy, nhưng cô có thể chọn m 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 t (1≤t≤104): số bộ test. Mỗi bộ test gồm:

  • Dòng đầu tiên chứa số nguyên n (1≤n≤106): số hành lang của mê cung.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (1≤ai≤109): độ dài các hành lang.

Tổng n trên tất cả các bộ test không vượt quá 106.

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ị m bất kỳ trước khi xuất phát.

Ràng buộc

  • 1≤t≤104
  • 1≤n≤106, tổng n không vượt quá 106
  • 1≤ai≤109

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 m=12. Các hành lang dài 12,24,12,12 được chạy hết bằng 1,2,1,1 lần chạy đủ m đơn vị; mỗi hành lang dài 9 và 6 cần một lần chạy và bị trễ một giây. Tổng cộng 7 lần chạy và 2 giây trễ, tức 9 giây.
2
3
4 8 8
5
10 2 4 6 8
4
9
Bộ test thứ nhất: chọn m=8; hành lang dài 4 tốn 2 giây, mỗi hành lang dài 8 tốn 1 giây. Bộ test thứ hai: chọn m=10; hành lang dài 10 tốn 1 giây, mỗi hành lang còn lại tốn 2 giây.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0