Tèo và Tí xoá số

Nguồn: CLUE OJ Độ khó: Trung bình Mảng 1 chiều Sắp xếp nổi bọt Trò chơi

Đề bài

Tí và Tèo cùng chơi một trò chơi. Ban đầu có $n$ số nguyên $A_1, A_2, \ldots, A_n$ được viết trên bảng. Mỗi lượt, người chơi chọn một số bất kỳ trên bảng và xoá nó đi. Trò chơi tiếp tục cho tới khi trên bảng chỉ còn lại đúng một số. Tèo đi trước, sau đó hai người lần lượt thay phiên nhau.

Tèo muốn số cuối cùng còn lại trên bảng nhỏ nhất có thể, còn Tí muốn số đó lớn nhất có thể. Hãy cho biết số nào sẽ còn lại trên bảng nếu cả hai đều chơi tối ưu.

Dữ liệu vào:

• Dòng đầu tiên là số nguyên $n$.
• Dòng thứ hai gồm $n$ số nguyên $A_1, A_2, \ldots, A_n$.

Kết quả:

In ra số còn lại trên bảng.

Giới hạn:

• $1 \le n \le 999$
• $|A_i| < 10^6$

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
2 1 3

Ví dụ 1 – output

2

Tèo xoá $3$ (số lớn nhất), Tí xoá $1$ (số nhỏ nhất), trên bảng còn lại $2$.

Nguồn: phỏng theo bài "TÈO VÀ TÍ" – vinhdinhcoder.net (chủ đề Mảng 1 chiều).

Lời mở đầu

Một trò chơi hai người nghe có vẻ phải "thử mọi nước đi", nhưng thật ra đáp án chỉ là phần tử đứng giữa sau khi sắp xếp. Bài này luyện cách suy luận trò chơi và kỹ thuật sắp xếp nổi bọt trên mảng. Ghi chú: đề gốc ghi ràng buộc $0 < n < 1000$ và $|A_i| < 10^6$, mình giữ nguyên ($1 \le n \le 999$).

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ưởngsắp xếp, lấy giữaLờ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 999$.

Test	Nội dung kiểm tra
1	Ví dụ của đề
2	$n = 1$: không ai phải xoá
3–4, 6–7, 9, 12–13, 15, 17–18	$n$ chẵn: Tèo được xoá nhiều hơn Tí một lần – đáp án lệch về bên trái
5, 16	Nhiều số bằng nhau
8, 13, 17	Số âm, số ở biên $\pm 999999$
13–20	$n$ gần 999, dãy tăng / giảm / ngẫu nhiên

Ý tưởngMỗi người xoá phía "có hại" cho mình

Có $n - 1$ lượt xoá; Tèo đi trước nên Tèo xoá $\lceil (n-1)/2 \rceil$ số, Tí xoá $\lfloor (n-1)/2 \rfloor$ số.

Tèo muốn số còn lại nhỏ → mỗi lượt Tèo xoá số lớn nhất. Tí muốn số còn lại lớn → Tí xoá số nhỏ nhất. Không ai có cách làm tốt hơn (xoá số ở giữa chỉ giúp đối thủ).

Kết quả

Sắp xếp tăng dần (chỉ số từ 0): Tí bỏ đi $\lfloor (n-1)/2 \rfloor$ số đầu, Tèo bỏ đi các số cuối, còn lại đúng phần tử a[(n - 1) / 2]. Với $n$ chẵn, đây là phần tử giữa lệch trái – không phải a[n / 2].

Em nhập dãy số rồi bấm Tiếp để xem hai bạn lần lượt xoá:

a =

Ví dụ nhanh:

Lời giảiNổi bọt rồi in phần tử giữa

Chương mảng chưa dùng hàm sort có sẵn, nên mình tự viết sắp xếp nổi bọt: mỗi lượt đổi chỗ các cặp kề nhau bị ngược thứ tự, số lớn nhất "nổi" dần về cuối.

C++▶ Chạy tay từng dòng codeSắp xếp nổi bọt, in a[(n - 1) / 2].

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Nổi bọt tốn khoảng $n^2/2 \approx 5 \cdot 10^5$ phép so sánh với $n = 999$ – rất nhanh.
2. Với $n = 1$ vòng lặp sắp xếp không chạy, (n - 1) / 2 = 0, in luôn số duy nhất.
3. Chỉ cần so sánh, không cần tính tổng nên int là đủ.

Không gian$O(n)$

Thời gian$O(n^2)$ (nổi bọt, $n \le 999$)

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.007s. Bản Python đúng 20/20 test, chạy lâu nhất 0.111s. 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ú
Sắp xếp rồi in a[n / 2]	9/20	sai test 3, 4, 6, 7, 9, 10, 12, 13, 17, 18, 20
Nghĩ Tèo đi trước nên in số nhỏ nhất	4/20	sai test 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
In trung bình cộng của dãy	8/20	sai test 3, 4, 10, 11, 12, 13, 14, 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.007s	Full điểm
	Python	20/20	0.111s	Full điểm
a[n / 2]	C++	9/20	–	Mất 11 test
In min	C++	4/20	–	Mất 16 test
Trung bình cộng	C++	8/20	–	Mất 12 test

Ghi chú của mình: với trò chơi "mỗi người chơi tối ưu", hãy thử tự chơi vài ván nhỏ trên giấy – thường sẽ thấy ngay chiến thuật tham lam và công thức đáp án.

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 😇