Trộn xen kẽ hai dãy

Nguồn: CLUE OJ Độ khó: Dễ Mảng 1 chiều Chỉ số mảng

Đề bài

Cho số nguyên dương $N$ và hai dãy số nguyên $A = (A_1, A_2, \ldots, A_N)$, $B = (B_1, B_2, \ldots, B_N)$. Dãy $C$ gồm $2N$ phần tử được tạo ra bằng cách lấy xen kẽ từng phần tử của $A$ và $B$:

$C = (A_1, B_1, A_2, B_2, \ldots, A_N, B_N)$

tức là $C_{2k-1} = A_k$ và $C_{2k} = B_k$ với $k = 1, 2, \ldots, N$. Hãy tạo và in ra dãy $C$.

Dữ liệu vào:

• Dòng đầu là số nguyên dương $N$.
• Dòng thứ hai là $N$ số nguyên của dãy $A$.
• Dòng thứ ba là $N$ số nguyên của dãy $B$.

Kết quả:

In ra $2N$ số của dãy $C$, các số cách nhau bởi dấu cách.

Giới hạn:

• $1 \le N < 1000$
• $|A_i|, |B_i| < 10^{18}$

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

3
1 2 3
4 5 6

Ví dụ 1 – output

1 4 2 5 3 6

$C_1 = A_1 = 1$, $C_2 = B_1 = 4$, $C_3 = A_2 = 2$, $C_4 = B_2 = 5$, $C_5 = A_3 = 3$, $C_6 = B_3 = 6$.

Nguồn: phỏng theo bài "MẢNG 5.13" – vinhdinhcoder.net (chủ đề Mảng 1 chiều).

Lời mở đầu

Ghép hai dãy thành một bằng cách lấy lần lượt một số của $A$, một số của $B$. Mấu chốt là tính đúng chỉ số: phần tử thứ $k$ của $A$ đi về ô $2k - 1$, phần tử thứ $k$ của $B$ đi về ô $2k$. Ghi chú: đề gốc viết công thức "$C_i = A_i$ với $i = 2k - 1$, $C_i = B_i$ với $i = 2k$", nếu hiểu đúng từng chữ thì $C$ chỉ có $N$ phần tử ($A_1, B_2, A_3, \ldots$), mâu thuẫn với ví dụ "1 4 2 5 3 6". Mình làm theo ví dụ: $C_{2k-1} = A_k$, $C_{2k} = B_k$, dãy $C$ có $2N$ phần tử.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngC[2k-1] = A[k], C[2k] = B[k]Lời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau.

Test	Nội dung kiểm tra
1	Ví dụ của đề
2–3, 20	$N = 1$, $N = 2$
4–5, 9–10	Số âm, số 0, phần tử lặp lại, hai dãy ngược chiều
6–7, 11, 13–14, 16–17, 19	Giá trị cỡ $10^{18}$, quanh $2^{31}$ – dùng int bị tràn
11–19	Các dãy dài tới 999 phần tử

Ý tưởngĐặt từng cặp (A[k], B[k]) vào hai ô liền nhau

Với mỗi $k$ từ 1 tới $N$: C[2k - 1] = A[k] và C[2k] = B[k]. Sau vòng lặp, $C$ có đủ $2N$ phần tử, in ra theo thứ tự.

Kiểm tra bằng tay với k = 1, 2

$k = 1$: ô 1 và ô 2 nhận $A_1, B_1$. $k = 2$: ô 3 và ô 4 nhận $A_2, B_2$. Hai ô của các $k$ liên tiếp nối tiếp nhau, không chồng lên nhau và không bỏ sót ô nào.

Thật ra không cần mảng $C$: in luôn A[k] rồi B[k] trong vòng lặp cũng được. Nhưng tạo mảng $C$ đúng như đề yêu cầu giúp em luyện cách tính chỉ số.

Em nhập hai dãy cùng độ dài rồi bấm Tiếp:

Dãy A = Dãy B =

Ví dụ nhanh:

Lời giảiMột vòng lặp, hai phép gán

Mảng $C$ phải khai báo đủ $2N$ ô (tới 1998 ô), kiểu long long.

C++▶ Chạy tay từng dòng codeĐặt A[k] vào C[2k-1], B[k] vào C[2k].

Dữ liệu vào (stdin) – sửa thoải mái3 1 2 3 4 5 6

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Vòng in chạy tới 2 * n, không phải n.
2. Trong Python, chỉ số bắt đầu từ 0 nên công thức thành c[2*k] = a[k], c[2*k + 1] = b[k] với k từ 0.

Không gian$O(N)$

Thời gian$O(N)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.004s. Bản Python đúng 20/20 test, chạy lâu nhất 0.021s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Dùng int	12/20	sai test 6, 7, 11, 13, 14, 16, 17, 19
In hết $A$ rồi mới in $B$ (nối hai dãy)	2/20	sai test 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
Hiểu đúng từng chữ công thức gốc: $C_i = A_i$ ($i$ lẻ), $C_i = B_i$ ($i$ chẵn)	0/20	sai test 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Xen kẽ nhưng bắt đầu bằng $B$	0/20	sai test 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.004s	Full điểm
	Python	20/20	0.021s	Full điểm
Dùng int	C++	12/20	–	Mất 8 test
Nối hai dãy	C++	2/20	–	Mất 18 test
Chỉ N phần tử	C++	0/20	–	Mất 20 test
Bắt đầu bằng B	C++	0/20	–	Mất 20 test

Ghi chú của mình: khi một mảng "dài gấp đôi" mảng kia, hãy viết ra vài chỉ số đầu ($k = 1, 2, 3$) để tìm công thức, rồi kiểm tra lại với phần tử cuối $k = N$ ($2N - 1$ và $2N$ – vừa đủ, không tràn mảng).

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇