Tri ân khách hàng (tìm vị trí)

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

Đề bài

Một cửa hàng thiết bị điện tử tổ chức tuần lễ tri ân khách hàng: mỗi khách đến mua hàng được bốc thăm một con số may mắn trong khoảng từ $1$ đến $5000$ (mỗi số chỉ được bốc một lần, nên các khách có số khác nhau). Cửa hàng lưu lại số may mắn của khách theo thứ tự mua hàng.

Kết thúc chương trình, cửa hàng quay ra số trúng thưởng $k$, chắc chắn $k$ là một trong những số khách hàng đã bốc. Hãy cho biết số thứ tự của khách hàng trúng thưởng (khách hàng đầu tiên có số thứ tự $1$).

Dữ liệu vào:

• Dòng đầu tiên là số nguyên $n$ – số khách hàng.
• Dòng thứ hai gồm $n$ số nguyên $a_1, a_2, \ldots, a_n$, trong đó $a_i$ là số may mắn của khách thứ $i$.
• Dòng thứ ba là số nguyên $k$ – số trúng thưởng.

Kết quả:

In ra số thứ tự của khách hàng trúng thưởng.

Giới hạn:

• $1 \le n \le 4999$
• $1 \le a_i \le 5000$, các $a_i$ đôi một khác nhau
• $k$ là một trong các $a_i$

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

4
4 2 3 8
8

Ví dụ 1 – output

4

Số $8$ là số của khách hàng thứ $4$.

Nguồn: phỏng theo bài "TRI ÂN KHÁCH HÀNG" – vinhdinhcoder.net (chủ đề Mảng 1 chiều).

Lời mở đầu

Bài tìm kiếm tuần tự cơ bản nhất: đi từ đầu tới cuối mảng, gặp số trúng thưởng thì in vị trí. Cần chú ý vị trí khách hàng đánh số từ 1 còn mảng đánh chỉ số từ 0. Ghi chú: đề gốc ghi ràng buộc "$|A_i| < 5 \cdot 10^3$" mâu thuẫn với mô tả (số từ 1 tới 5000); mình chốt $1 \le a_i \le 5000$, các số khác nhau (mỗi số chỉ bốc được một lần) và $1 \le n \le 4999$.

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ưởngduyệt tới khi a[i] = kLờ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. Mọi test có $n \le 4999$, các số khác nhau.

Test	Nội dung kiểm tra
1	Ví dụ của đề
2–3	$n = 1$; khách trúng thưởng là người đầu tiên
1, 8, 11, 16, 17	Khách trúng thưởng là người cuối cùng – bắt lỗi vòng lặp bỏ sót phần tử cuối
4–7, 10, 12–20	Ngẫu nhiên, $n$ tới 4999

Ý tưởngTìm kiếm tuần tự

Duyệt i từ đầu tới cuối mảng; gặp a[i] == k thì in vị trí và dừng (break).

Vị trí đếm từ 1

Nếu lưu mảng từ chỉ số 0 thì khách thứ i + 1 nằm ở a[i] – nhớ in i + 1. Cách khác (như lời giải C++ bên dưới) là lưu luôn từ a[1] tới a[n] để chỉ số trùng số thứ tự.

Em nhập dữ liệu rồi bấm Tiếp để xem chương trình duyệt mảng từng bước:

a = k =

Ví dụ nhanh:

Lời giảiDuyệt và break

Mảng lưu từ chỉ số 1 để số thứ tự khách trùng với chỉ số.

C++▶ Chạy tay từng dòng codeLưu a[1..n], tìm i có a[i] = k.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Vì các số khác nhau nên chỉ có đúng một vị trí – break ngay khi tìm thấy để đỡ duyệt thừa.
2. Mảng khai báo a[5005] vì dùng tới chỉ số $n \le 4999$.

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.069s. 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ú
Lưu mảng từ 0 rồi in i (quên +1)	0/20	sai test 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
In số trúng thưởng $k$ thay vì số thứ tự	1/20	sai test 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Lưu từ 1 nhưng vòng tìm viết i < n (sót khách cuối)	13/20	sai test 1, 2, 5, 8, 11, 16, 17

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.069s	Full điểm
	Python	20/20	0.045s	Full điểm
Quên +1	C++	0/20	–	Mất 20 test
In k	C++	1/20	–	Mất 19 test
Sót khách cuối	C++	13/20	–	Mất 7 test

Ghi chú của mình: lưu mảng từ 0 hay từ 1 đều được, miễn là nhất quán: vòng đọc, vòng duyệt và câu lệnh in phải cùng một quy ước.

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 😇