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

Lập trình cá nhân tháng 2s 128MB

Đăng nhập

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

$1≤ T ≤10^5$
$2≤N≤3×10^5$
$1≤K≤10^9$
Tổng $N ≤ 3×10^5$

Các phần tử trong $A$ và $B$ :

Là số nguyên
Hai dãy có cùng tập phần tử (có thể khác thứ tự)

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

#	Tài khoản	Kết suất	Lúc nộp
1	Lê Văn Nguyên @35261020087	1 ms 228 KB 2600 Bytes	11/05/2026 17:08
2	GV. Bùi Phú Khuyên @KBP0100298	1 ms 312 KB 2683 Bytes	21/04/2026 22:29
3	GV. Bùi Phú Khuyên @KBP0100298	1 ms 316 KB 2683 Bytes	22/04/2026 00:09
4	Lê Duy Hải @2280600799	1 ms 388 KB 3631 Bytes	23/04/2026 03:09
5	T Phạm Ngọc Trai @2280603326	1 ms 392 KB 5038 Bytes	23/04/2026 09:42
6	Phạm Vũ Minh Đức @2386400012	49 ms 3708 KB 1465 Bytes	22/04/2026 23:10
7	Phạm Trần Minh Hiếu @2280600972	49 ms 3880 KB 2649 Bytes	23/04/2026 10:42
8	Phạm Trần Minh Hiếu @2280600972	50 ms 3872 KB 2873 Bytes	23/04/2026 10:42

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

Đăng nhập

Đang chạy thử nghiệm...

Vui lòng chờ tiến trình hoàn tất

KIỂM THỬ

Không có dữ liệu kiểm thử

Viết code

Không hỗ trợ Mobile