trang chủ / đề bài / icpcwf22_q

Xáo trộn container

Đề bài

Mô tả

Những con tàu chở hàng khổng lồ, mỗi chiếc chở hàng nghìn container, ngày ngày đi khắp các vùng biển trên thế giới. Chúng giúp thương mại hiện đại trở nên khả thi vì hiệu quả đến mức vận chuyển hàng hoá qua nửa vòng trái đất chỉ tốn vài xu.

Khi tàu đến nơi, các container kích thước tiêu chuẩn được dỡ từ tàu xuống các chồng trên đất liền, rồi từ đó được chuyển lên tàu hoả hoặc xe tải để chở đến nơi nhận. Việc di chuyển container rất tốn kém, nên các nhà khai thác cảng cố gắng giảm tối thiểu số lần di chuyển cần thiết để giao hàng.

Trong bài này, ta xét một tình huống dỡ container như vậy. Cần dỡ n container, chúng được đặt vào hai chồng, mỗi chồng xếp từ dưới lên trên. Vị trí của mỗi container là ngẫu nhiên: với xác suất bằng nhau nó được đặt lên chồng thứ nhất hoặc chồng thứ hai (độc lập với các container khác). Sau khi dỡ hết container, chúng sẽ được các xe tải lấy đi theo một thứ tự cho trước. Khi một xe tải muốn lấy một container cụ thể, có hai trường hợp. Nếu container đó đang ở trên cùng chồng của nó, nó được chuyển lên xe tải mà không cần di chuyển container nào khác. Ngược lại, phải chuyển các container từ chồng này sang chồng kia cho đến khi container cần lấy nằm trên cùng chồng của nó. Lúc đó container được chuyển lên xe tải.

Ví dụ, xét trường hợp có ba container được dỡ theo thứ tự 1,2,3. Giả sử container 1 và 3 nằm ở chồng thứ nhất, container 2 nằm ở chồng thứ hai. Nếu các container được chuyển lên xe tải theo thứ tự 1,2,3 thì cần tất cả năm lần di chuyển container:

Chồng 1 Chồng 2 Diễn giải
1 3 2 Trạng thái ban đầu (các chồng liệt kê từ dưới lên trên)
1 2 3 Chuyển container 3 từ chồng 1 sang chồng 2
2 3 Chuyển container 1 lên xe tải
3 2 Chuyển container 3 từ chồng 2 sang chồng 1
3 Chuyển container 2 lên xe tải
Chuyển container 3 lên xe tải

Ta muốn biết cần bao nhiêu lần di chuyển để giao hết container cho khách hàng. Giả sử vị trí đặt các container là ngẫu nhiên như trên, hãy tính kỳ vọng số lần di chuyển cần thiết với một thứ tự lấy hàng của xe tải cho trước.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên n (1≤n≤106), số container. Các container được đánh số 1,2,…,n và được dỡ khỏi tàu theo đúng thứ tự này.

Dòng thứ hai chứa n số nguyên a1,…,an. Các số này là một hoán vị của {1,2,…,n}, cho biết thứ tự các container được chuyển lên xe tải.

Dữ liệu ra

In ra kỳ vọng số lần di chuyển cần thiết để chuyển các container lên xe tải. Số này không tính chi phí dỡ container khỏi tàu, nhưng tính cả các lần chuyển giữa hai chồng và các lần chuyển từ chồng lên xe tải. Đáp án được chấp nhận nếu sai số tuyệt đối không quá 10−3.

Ràng buộc

  • 1≤n≤106.
  • a1,…,an là một hoán vị của {1,2,…,n}.

Ví dụ

Input Output Giải thích
5
4 2 5 3 1
7.000 Lấy trung bình số lần di chuyển trên cả 25=32 cách đặt container (mỗi cách có xác suất như nhau) được 7.
6
1 2 3 4 5 6
13.500 Mỗi container phải được chuyển lên xe tải một lần (6 lần); trung bình có thêm 7,5 lần chuyển giữa hai chồng.

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