Mức độ thành công
Đề bài
Ban tổ chức một kỳ thi lập trình muốn ước lượng mức độ thành công của kỳ thi dựa trên khả năng giải bài của các thí sinh. Mỗi thí sinh được xếp vào đúng một trong ba loại:
| Loại | Khả năng | Điểm đánh giá |
|---|---|---|
| 1 | giải được ít nhất 1 bài | 500 |
| 2 | giải được ít nhất 3 bài | 1000 |
| 3 | giải được toàn bộ các bài | 1500 |
Ban tổ chức dự đoán có $a$ thí sinh loại 1, $b$ thí sinh loại 2 và $c$ thí sinh loại 3. Mức độ thành công là tổng điểm đánh giá của tất cả thí sinh. Hãy tính giá trị đó.
Dữ liệu vào: Một dòng gồm ba số nguyên dương $a, b, c$ cách nhau bởi dấu cách.
Kết quả: In ra mức độ thành công của kỳ thi.
Giới hạn: $1 \le a, b, c \le 10^9$.
Subtask:
- Subtask 1 (40% số điểm): $a, b, c \le 100$.
- Subtask 2 (60% số điểm): không có ràng buộc gì thêm.
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.
2 1 135001 1 13000Giải thích: Ví dụ 1: $2 \cdot 500 + 1 \cdot 1000 + 1 \cdot 1500$ $= 3500$.
Nguồn: phỏng theo bài "MỨC ĐỘ THÀNH CÔNG" – vinhdinhcoder.net.
Lời mở đầu
Công thức thì ai cũng thấy ngay: $S = 500a + 1000b + 1500c$. Cái khó duy nhất (và là lý do bài này có subtask) là độ lớn của kết quả: với $a = b = c = 10^9$ thì $S = 3 \cdot 10^{12}$, lớn gấp hơn một nghìn lần số lớn nhất mà kiểu int chứa được. Mình sẽ cho các bạn thấy hai cái bẫy tràn số kinh điển – trong đó bẫy thứ hai bẫy được cả những bạn "biết" phải dùng long long – kèm kết quả chạy thật trên bộ test.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 20 test, mỗi test là một dòng 3 số. Mình đã kiểm tra: test 1–8 thoả $a, b, c \le 100$ (subtask 1), test 9–20 là subtask 2.
| Nhóm | Test | $a, b, c$ lớn nhất | Đáp án nhỏ nhất | Đáp án lớn nhất | Số test đáp án vượt quá int |
|---|---|---|---|---|---|
| Subtask 1 | 1–8 | 100 | 3.000 | 300.000 | 0 |
| Subtask 2 | 9–20 | 1.000.000.000 | 500.000.002.500 | 3.000.000.000.000 | 12 |
- Ở subtask 1, đáp án lớn nhất chỉ là $3000 \cdot 100 = 300\,000$,
intchứa thoải mái. - Ở subtask 2, cả 12 test đều có đáp án lớn hơn $2^{31} - 1 = 2\,147\,483\,647$ (giới hạn của
int), lớn nhất tới $3 \cdot 10^{12}$.
Kết quả chạy thật của các cách viết bên dưới theo từng subtask:
| Subtask | Test | Bẫy 1int | Bẫy 2long long s = biểu thức int | Lời giảilong long |
|---|---|---|---|---|
| Subtask 1 (40%) | 1–8 | 8/8 | 8/8 | 8/8 |
| Subtask 2 (60%) | 9–20 | 0/12 | 0/12 | 12/12 |
Ý tưởngCông thức và "đồng hồ" int
Có $a$ thí sinh loại 1, mỗi bạn 500 điểm → $500a$; tương tự $1000b$ và $1500c$. Vậy
$$S = 500a + 1000b + 1500c.$$
Còn chuyện tràn số: kiểu int có 32 bit, chỉ chứa được các số từ $-2\,147\,483\,648$ tới $2\,147\,483\,647$ (khoảng $\pm 2{,}1$ tỉ). Hãy tưởng tượng int như một đồng hồ hình tròn: đi từ 0 theo chiều kim đồng hồ là các số dương, tới $2\,147\,483\,647$ mà cộng thêm 1 thì kim nhảy sang $-2\,147\,483\,648$ (nửa màu đỏ) rồi đi tiếp lên 0, quay hết vòng này tới vòng khác. Máy chỉ nhớ vị trí của kim, không nhớ đã quay bao nhiêu vòng – nên kết quả bị sai mà không hề báo lỗi.
Em nhập $a, b, c$ rồi bấm Tiếp để xem tổng được cộng dần và kim đồng hồ int quay:
Bẫy 1Dùng int cho tất cả
Code này đúng với hai ví dụ của đề và cả subtask 1. Nhưng với $a = b = c = 10^9$, ngay phép nhân $500 \cdot a = 5 \cdot 10^{11}$ đã vượt xa giới hạn int. Em bấm dữ liệu mẫu a = b = c = 10^9 trong khung chạy tay để xem kim đồng hồ quay hàng trăm vòng.
Kết quả chạy thật: bản C++ đúng 8/20 test, sai ở test 9–20; test đúng chạy lâu nhất 0.003s. Với trường hợp lớn nhất $a = b = c = 10^9$, chương trình in 2112827392, trong khi đáp án là 3000000000000. Tất cả 12 test của subtask 2 đều sai → chỉ được 40% số điểm.
Bẫy 2Gán vào long long vẫn tràn
Nhiều bạn biết kết quả lớn nên sửa đúng một chỗ: đổi biến tổng thành long long, còn a, b, c vẫn để int:
int a, b, c;
cin >> a >> b >> c;
long long s = 500 * a + 1000 * b + 1500 * c; // BẪY: vế phải tính bằng int, tràn TRƯỚC khi gán
cout << s;Vấn đề là C++ tính vế phải trước, theo kiểu của các toán hạng: 500 là int, a là int nên 500 * a được tính bằng int và đã tràn ngay lúc nhân. Gán kết quả (đã sai) vào long long sau đó cũng chẳng cứu được gì – giống như rót nước tràn ly rồi mới đổi sang cái xô.
Kết quả chạy thật: bản C++ đúng 8/20 test, sai ở test 9–20; test đúng chạy lâu nhất 0.003s – y hệt bẫy 1, in ra đúng những con số sai như bẫy 1.
long long: hoặc khai báo luôn long long a, b, c (cách mình dùng), hoặc viết 500LL * a + 1000LL * b + 1500LL * c (hậu tố LL biến hằng số thành long long, kéo cả phép nhân lên long long), hoặc 1LL * 500 * a.Lời giảiDùng long long ngay từ đầu
long long có 64 bit, chứa được tới khoảng $9{,}2 \cdot 10^{18}$ – dư sức cho $3 \cdot 10^{12}$. Khai báo $a, b, c$ là long long thì mọi phép nhân, phép cộng đều tính bằng long long:
- Python không có bẫy này: số nguyên của Python tự lớn lên bao nhiêu cũng được, nên chỉ một dòng là xong.
- Mẹo kiểm tra nhanh trước khi code: ước lượng kết quả lớn nhất có thể có ($3000 \cdot 10^9 = 3 \cdot 10^{12}$). Lớn hơn khoảng $2 \cdot 10^9$ là phải nghĩ ngay tới
long long.
Kết quả chạy thật: Bản C++ đúng 20/20 test; test đúng chạy lâu nhất 0.003s. Bản Python đúng 20/20 test; test đúng chạy lâu nhất 0.017s. Full điểm.
Tổng kếtKết quả chạy thật trên bộ test
| Cách viết | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
Bẫy 1: toàn bộ là int | C++ | 8/20 | 0.003s | Sai test 9–20 → mất subtask 2 |
Bẫy 2: long long s nhưng a, b, c là int | C++ | 8/20 | 0.003s | Sai test 9–20 → mất subtask 2 |
Lời giải: long long | C++ | 20/20 | 0.003s | Full điểm |
| Python | 20/20 | 0.017s | Full điểm |
long long thì phải có toán hạng long long ngay trong phép nhân.
Nhận xét
Đăng nhận xét