Tổng số chẵn ở vị trí lẻ

Nguồn: CLUE OJ Độ khó: Dễ Mảng 1 chiều unsigned long long

Đề bài

Hãy nhập vào $20$ số nguyên không âm $A_1, A_2, \ldots, A_{20}$, tính tổng các phần tử là số chẵn nằm ở vị trí lẻ (vị trí $1, 3, 5, \ldots, 19$, đánh số từ $1$) trong dãy $20$ số đó.

Dữ liệu vào:

• Dòng đầu chứa số $20$.
• Dòng thứ hai chứa $20$ số nguyên không âm $A_1, A_2, \ldots, A_{20}$.

Kết quả:

In ra tổng tính được.

Giới hạn:

• $0 \le A_i \le 2^{60}$ ($2^{60} = 1\,152\,921\,504\,606\,846\,976$)

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

20
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 2 2 2

Ví dụ 1 – output

20

Các vị trí lẻ $1, 3, \ldots, 19$ đều chứa số $2$ (chẵn), có $10$ vị trí nên tổng là $10 \times 2 = 20$. Các số $2$ ở vị trí chẵn $18, 20$ không được tính.

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

Lời mở đầu

Bài tưởng như chỉ cần một vòng lặp và một câu if, nhưng giới hạn $A_i \le 2^{60}$ giấu một cái bẫy lớn: tổng 10 số cỡ $2^{60}$ là khoảng $1{,}15 \cdot 10^{19}$ – vượt quá long long (tối đa khoảng $9{,}22 \cdot 10^{18}$)!

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ưởngi = 1, 3, 5, ... và unsigned long longLờ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, 4–6	Toàn số 0, toàn số lẻ, dãy $1..20$, $20..1$
7–8, 10	Số chẵn chỉ ở vị trí chẵn hoặc chỉ ở vị trí lẻ – lấy nhầm vị trí là sai
3, 7, 10, 13, 15, 17, 19	Tổng lớn hơn $9{,}22 \cdot 10^{18}$ – long long bị tràn
9, 11–20	Số lớn, ngẫu nhiên tới $2^{60}$ – double làm tròn sai

Ý tưởngBước nhảy 2 và kiểu unsigned long long

Các vị trí lẻ là $1, 3, 5, \ldots, 19$, nên vòng lặp chạy for (i = 1; i <= 20; i += 2); số nào chẵn (a[i] % 2 == 0) thì cộng vào tổng.

Tổng có thể vượt long long

Có 10 vị trí lẻ, mỗi số tới $2^{60}$, nên tổng tới $10 \cdot 2^{60} \approx 1{,}15 \cdot 10^{19} > 2^{63} - 1 \approx 9{,}22 \cdot 10^{18}$. Kiểu unsigned long long (số nguyên không âm 64 bit) chứa được tới $2^{64} - 1 \approx 1{,}8 \cdot 10^{19}$ – vừa đủ. Python không bị giới hạn nên không phải lo.

Em nhập 20 số (hoặc ít hơn để thử) rồi bấm Tiếp:

Dãy A =

Ví dụ nhanh:

Lời giảiVòng lặp bước 2, tổng kiểu unsigned long long

Cả mảng và biến tổng đều khai báo unsigned long long.

C++▶ Chạy tay từng dòng codeCộng các số chẵn ở vị trí 1, 3, 5, ...

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Khi đọc bằng cin, số tới $2^{60}$ vừa với cả long long lẫn unsigned long long; cái vượt giới hạn là tổng.
2. Python: danh sách đánh số từ 0 nên vị trí lẻ 1, 3, 5 ứng với chỉ số 0, 2, 4 – vòng lặp range(0, n, 2).
3. double chỉ giữ khoảng 15–16 chữ số có nghĩa, không biểu diễn chính xác được số cỡ $10^{19}$.

Không gian$O(1)$

Thời gian$O(1)$ (đúng 20 số)

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.003s. Bản Python đúng 20/20 test, chạy lâu nhất 0.017s. 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 long long cho tổng	13/20	sai test 3, 7, 10, 13, 15, 17, 19
Lấy nhầm các vị trí chẵn 2, 4, 6, ...	6/20	sai test 1, 5, 6, 7, 8, 10, 13, 14, 15, 16, 17, 18, 19, 20
Cộng tất cả số chẵn (quên điều kiện vị trí)	6/20	sai test 1, 3, 5, 8, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Dùng double	11/20	sai test 9, 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.003s	Full điểm
	Python	20/20	0.017s	Full điểm
long long tràn	C++	13/20	–	Mất 7 test
Nhầm vị trí chẵn	C++	6/20	–	Mất 14 test
Quên vị trí	C++	6/20	–	Mất 14 test
Dùng double	C++	11/20	–	Mất 9 test

Ghi chú của mình: luôn ước lượng kết quả lớn nhất có thể (ở đây $10 \cdot 2^{60}$) trước khi chọn kiểu dữ liệu – giá trị từng phần tử vừa kiểu không có nghĩa là tổng cũng vừa.

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 😇