Đổi điểm cộng lấy kẹo

Nguồn: CLUE OJ Độ khó: Dễ Mảng 1 chiều Tìm max

Đề bài

Có $N$ bạn học sinh, trong học kỳ vừa qua bạn thứ $i$ đã giành được $a_i$ điểm cộng. Thầy Phú cho phép đổi điểm lấy kẹo như sau: bạn có $x$ điểm cộng sẽ được đổi $x$ cái kẹo. Riêng các bạn có điểm cộng cao nhất (nếu có nhiều bạn cùng đạt điểm cao nhất thì tất cả các bạn đó) được nhân đôi số kẹo.

Hỏi thầy Phú phải chuẩn bị bao nhiêu cái kẹo?

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$ là số điểm cộng của $N$ bạn.

Kết quả:

In ra số kẹo mà thầy Phú cần chuẩn bị.

Giới hạn:

• $1 \le N \le 50$
• $0 \le a_i \le 1000$

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

Ví dụ 1 – output

12

Bạn thứ ba có điểm cao nhất ($3$) nên được $6$ kẹo. Tổng số kẹo: $2 + 1 + 6 + 1 + 2 = 12$.

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

Lời mở đầu

Một bài "duyệt mảng hai lần" kinh điển: lần đầu tìm điểm cao nhất, lần sau mới biết bạn nào được nhân đôi. Điểm dễ sai là có nhiều bạn cùng đạt điểm cao nhất. Ghi chú: đề gốc ghi "các bạn cao điểm nhất" nhưng không có giới hạn điểm; mình hiểu là tất cả các bạn có điểm bằng điểm cao nhất đều được nhân đôi, và bổ sung $0 \le a_i \le 1000$.

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ưởngtìm max, rồi cộngLờ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 50$.

Test	Nội dung kiểm tra
1	Ví dụ của đề
2–4	$N = 1$, toàn điểm 0
5, 8, 9, 12	Nhiều bạn cùng điểm cao nhất – bắt lỗi chỉ nhân đôi một bạn
6–7, 15	Bạn cao điểm nhất đứng đầu / đứng cuối mảng – bắt lỗi vòng lặp tìm max bỏ sót phần tử cuối
10–20	Ngẫu nhiên, $N$ tới 50, điểm tới 1000

Ý tưởngDuyệt hai lần

Lần 1: tìm điểm cao nhất mx (khởi tạo mx = a[0], gặp số lớn hơn thì cập nhật).

Lần 2: cộng số kẹo: bạn nào có a[i] == mx được 2 * a[i], còn lại được a[i].

Vì sao không làm một lần?

Khi đang duyệt giữa chừng ta chưa biết điểm cao nhất là bao nhiêu (có thể có bạn ở phía sau cao hơn), nên chưa thể quyết định nhân đôi. Lưu điểm vào mảng giúp ta duyệt lại lần thứ hai.

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 =

Ví dụ nhanh:

Lời giảiTìm max rồi cộng có điều kiện

Hai vòng for riêng biệt trên cùng một mảng.

C++▶ Chạy tay từng dòng codeVòng 1 tìm mx, vòng 2 cộng kẹo.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Khởi tạo mx = a[0] an toàn hơn mx = 0 (ở bài này điểm không âm nên 0 cũng được, nhưng nên tập thói quen).
2. Điều kiện là a[i] == mx chứ không phải "vị trí của max" – vì có thể nhiều vị trí cùng đạt max.

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.002s. Bản Python đúng 20/20 test, chạy lâu nhất 0.019s. 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ú
Chỉ nhân đôi một bạn cao điểm nhất (nhớ vị trí max)	16/20	sai test 5, 8, 9, 12
Quên nhân đôi, chỉ cộng tổng điểm	2/20	sai test 1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Vòng tìm max viết i < n - 1 (bỏ sót bạn cuối)	18/20	sai test 7, 15

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.002s	Full điểm
	Python	20/20	0.019s	Full điểm
Nhân đôi 1 bạn	C++	16/20	–	Mất 4 test
Quên nhân đôi	C++	2/20	–	Mất 18 test
Sót phần tử cuối	C++	18/20	–	Mất 2 test

Ghi chú của mình: "tìm max rồi xử lý những phần tử bằng max" là mẫu rất hay gặp – nhớ là có thể có nhiều phần tử cùng bằng max.

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 😇