trang chủ / đề bài / icpc26_mb_c

Bộ chuyển đổi năng lượng

Đề bài

Mô tả

Hệ thống đẩy của tàu vũ trụ gồm N ô năng lượng, mỗi ô được biểu diễn bằng một số nguyên không âm. Để kích hoạt động cơ siêu tốc, mọi ô phải được cân bằng về cùng một giá trị, với tổng số thao tác ít nhất.

Bạn có thể chọn một ô bất kỳ có giá trị x và áp dụng một trong hai thao tác:

  1. Nạp quá mức: thay x bằng 2×x+1.
  2. Xả: thay x bằng ⌊x/2⌋ (chia nguyên).

Hãy xác định tổng số thao tác ít nhất (tính trên tất cả các ô) để mọi giá trị trong mảng trở nên bằng nhau.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên N (2≤N≤50000).
  • Dòng thứ hai chứa N số nguyên không âm (mỗi số ≤2×105).

Dữ liệu ra

In ra một số nguyên duy nhất: tổng số thao tác ít nhất cần thực hiện.

Ràng buộc

  • 2≤N≤50000.
  • Mỗi giá trị là số nguyên thỏa 0≤ai≤2×105.

Ví dụ

Input Output Giải thích
4
6 7 12 15
6 Đưa mọi ô về 7: 6→3→7 (2 thao tác), 7 giữ nguyên, 12→6→3→7 (3 thao tác), 15→7 (1 thao tác); tổng 6.
5
0 3 7 7 14
5 Ví dụ bổ sung (không có trong đề gốc). Đưa mọi ô về 7: 0→1→3→7 (3), 3→7 (1), hai ô 7 giữ nguyên, 14→7 (1); tổng 5. Đưa về 3 tốn 2+0+1+1+2=6.

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