Tìm vị trí đầu tiên bằng K

Nguồn: CLUE OJ Độ khó: Dễ Mảng 1 chiều Tìm kiếm tuần tự

Đề bài

Cho số nguyên dương $N$, số nguyên dương $K$ và dãy số nguyên $A_1, A_2, \ldots, A_N$. Hãy cho biết trong dãy có phần tử nào bằng $K$ hay không; nếu có thì cho biết vị trí bé nhất (vị trí đánh số từ $1$) của phần tử bằng $K$.

Dữ liệu vào:

• Dòng đầu gồm hai số nguyên dương $N$ và $K$.
• Dòng thứ hai gồm $N$ số nguyên $A_1, A_2, \ldots, A_N$.

Kết quả:

• Nếu có, in ra CO K O VI TRI p với $p$ là vị trí bé nhất của phần tử bằng $K$ (chữ K in nguyên văn, xem ví dụ).
• Nếu không có, in ra KHONG CO K.

Giới hạn:

• $1 \le N \le 10^5$
• $1 \le K \le 10^{18}$
• $|A_i| \le 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

5 2
3 5 2 8 2

Ví dụ 1 – output

CO K O VI TRI 3

Ví dụ 2 – input

5 4
3 5 2 8 2

Ví dụ 2 – output

KHONG CO K

• Ví dụ 1: $K = 2$ xuất hiện ở vị trí 3 và 5, vị trí bé nhất là 3.
• Ví dụ 2: không có phần tử nào bằng $4$.

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

Lời mở đầu

Tìm kiếm tuần tự: duyệt từ trái sang phải, gặp phần tử bằng $K$ lần đầu tiên là dừng. Hai chi tiết cần cẩn thận: dừng đúng lúc để lấy vị trí bé nhất, và $K$, $A_i$ tới $10^{18}$ nên phải dùng long long.

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ưởngbreak ở lần gặp đầuLờ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–2	Hai ví dụ của đề
3–6	$N = 1$, $K$ ở cuối, tất cả phần tử bằng $K$
7–8, 14	$K = 10^{18}$, $A_i = \pm 10^{18}$
9–10, 15–16, 20	$K$ hoặc $A_i$ lớn hơn $2^{32}$ – bản int đọc sai, nhận nhầm
11–20	$N$ tới $10^5$: $K$ ở cuối, không có $K$, $K$ xuất hiện nhiều lần

Ý tưởngDuyệt và dừng ở lần gặp đầu tiên

Dùng biến vt = 0 (0 nghĩa là "chưa thấy"). Duyệt $i = 1..N$, gặp a[i] == k thì gán vt = i và break ngay. Sau vòng lặp: vt == 0 → in KHONG CO K, ngược lại in CO K O VI TRI vt.

Vì sao cần break?

Nếu không dừng, vt sẽ bị ghi đè bởi các lần gặp sau và cuối cùng là vị trí lớn nhất, không phải bé nhất. break còn giúp chương trình kết thúc sớm.

Em nhập K và dãy rồi bấm Tiếp:

K = Dãy A =

Ví dụ nhanh:

Lời giảiTìm kiếm tuần tự với break

$N$ tới $10^5$ nên C++ nên thêm ios::sync_with_stdio(false); cin.tie(0); để đọc nhanh hơn.

C++▶ Chạy tay từng dòng codeDuyệt mảng, gặp K lần đầu thì dừng.

Dữ liệu vào (stdin) – sửa thoải mái5 2 3 5 2 8 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Chữ K trong thông báo được in nguyên văn (không thay bằng giá trị của $K$).
2. Python: duyệt for i in range(n) rồi in i + 1 vì danh sách đánh số 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.032s. Bản Python đúng 20/20 test, chạy lâu nhất 0.045s. 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 cho $K$ và mảng	12/20	sai test 7, 9, 10, 11, 14, 15, 17, 18
Không break (ra vị trí cuối cùng)	12/20	sai test 1, 5, 7, 13, 14, 17, 18, 19
In vị trí đếm từ 0	6/20	sai test 1, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 18, 19
In thông báo mỗi lần gặp $K$	12/20	sai test 1, 5, 7, 13, 14, 17, 18, 19

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.032s	Full điểm
	Python	20/20	0.045s	Full điểm
Dùng int	C++	12/20	–	Mất 8 test
Thiếu break	C++	12/20	–	Mất 8 test
Vị trí từ 0	C++	6/20	–	Mất 14 test
In nhiều lần	C++	12/20	–	Mất 8 test

Ghi chú của mình: mẫu "biến cờ/vị trí + break" dùng cho mọi bài tìm kiếm: khởi tạo giá trị "chưa thấy", duyệt, thấy thì ghi nhận và dừng, cuối cùng kiểm tra biến để in kết quả.

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 😇