#2020 · Tái cấu trúc chuỗi dữ liệu lượng tử

MÔ TẢ BÀI TOÁN

Trong một hệ thống máy tính lượng tử tiên tiến, dữ liệu được lưu trữ dưới dạng một chuỗi các hạt năng lượng. Tuy nhiên, do nhiễu từ môi trường, thứ tự các hạt có thể bị xáo trộn trong quá trình truyền tải.

Bạn có:

  • Một chuỗi ban đầu A
  • Một chuỗi mục tiêu B

Nhiệm vụ của bạn là tái cấu trúc lại A để trở thành B, bằng cách thực hiện các thao tác hoán đổi đặc biệt.

Quy tắc thao tác Bạn được phép thực hiện thao tác sau: Một lần thao tác (cost = 1) cho phép bạn thực hiện chính xác K lần hoán đổi kề nhau Một hoán đổi kề nhau là:

  • Chọn vị trí i $(1 ≤ i < N)$
  • Đổi chỗ hai phần tử liền kề: A_i ↔ A_{i+1}

Nhiệm vụ Với mỗi bộ kiểm thử:

  • Xác định xem có thể biến dãy A → B hay không
  • Nếu có → tìm số lần thao tác nhỏ nhất
  • Nếu không → in -1

Dữ liệu vào

  • Dòng đầu: số nguyên T – số test
  • Với mỗi test:

N K

A_1 A_2 ... A_N

B_1 B_2 ... B_N

Dữ liệu ra

In ra T dòng. Mỗi dòng là:

  • Số thao tác nhỏ nhất nếu làm được
  • Hoặc -1 nếu không thể

Ràng buộc

BẢNG TỔNG QUAN KẾT QUẢ

# Tài khoản Kết suất Lúc nộp
1
GV. Bùi Phú Khuyên @KBP0100298
1 ms 312 KB
2683 Bytes
21/04/2026
22:29
2
GV. Bùi Phú Khuyên @KBP0100298
1 ms 316 KB
2683 Bytes
22/04/2026
00:09

LỊCH SỬ CÁ NHÂN

Vui lòng đăng nhập để xem lịch sử làm bài của bạn.

THẢO LUẬN BÀI TOÁN

Chưa có thảo luận nào cho bài này.

GỢI Ý & HƯỚNG DẪN

Giải thích trong ví dụ 1 với Bộ kiểm thử 1, ta có:

  • Chuỗi ban đầu: A=(3,1,4,1,5)
  • Chuỗi mục tiêu: B=(5,1,3,1,4)
  • Mỗi thao tác cho phép thực hiện 4 lần hoán đổi kề nhau

Thao tác 1 (cost = 1)

  • Bạn thực hiện 4 lần hoán đổi kề nhau, chọn các vị trí: i = 3, 1, 4, 1
  • Thực hiện lần lượt:
    • Swap vị trí 3: (3,1,4,1,5)→(3,1,1,4,5)
    • Swap vị trí 1: →(1,3,1,4,5)
    • Swap vị trí 4: →(1,3,1,5,4)
    • Swap vị trí 1: →(3,1,1,5,4)
  • Sau thao tác 1: A = (3, 1, 1, 5, 4)

Thao tác 2 (cost = 1):

  • Tiếp tục thực hiện 4 lần hoán đổi, chọn: i = 3, 1, 2, 1
  • Thực hiện:
    • Swap vị trí 3: (3,1,1,5,4)→(3,1,5,1,4)
    • Swap vị trí 1: →(1,3,5,1,4)
    • Swap vị trí 2: →(1,5,3,1,4)
    • Swap vị trí 1: →(5,1,3,1,4)
  • Sau thao tác 2: A = (5, 1, 3, 1, 4) = B

Vậy sau 2 thao tác chuỗi đã được tái cấu trúc

Tương tự với bộ kiểm thử 2:

  • Chuỗi ban đầu: A=(1,2)
  • Chuỗi mục tiêu: B=(2,1)
  • K=1000000000

Vấn đề: Để biến A thành B, bạn cần đúng 1 lần hoán đổi. Nhưng mỗi thao tác lại bắt buộc phải thực hiện: 1000000000 lần hoán đổi. Không thể thực hiện được. In ra -1

Viết code