Phát kẹo 2

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp for Kiểu dữ liệu

Đề bài

Thầy Phú mang kẹo đến lớp để phát cho học sinh theo quy tắc sau: em đầu tiên nhận $1$ cái kẹo, mỗi em tiếp theo nhận nhiều hơn em trước đúng $3$ cái (tức là $1, 4, 7, 10, \ldots$).

Lớp có $N$ học sinh nhưng thầy chỉ mang theo $K$ cái kẹo. Thầy phát lần lượt từng em, đúng quy tắc trên; khi số kẹo còn lại không đủ để phát cho em tiếp theo thì thầy dừng lại và mang phần kẹo thừa về.

Hãy cho biết có nhiều nhất bao nhiêu học sinh nhận được kẹo.

Dữ liệu vào:

Một dòng gồm hai số nguyên dương $N$ và $K$.

Kết quả:

In ra một số nguyên là số học sinh nhận được kẹo (không vượt quá $N$).

Giới hạn:

• $1 \le N \le 10^5$
• $1 \le K \le 10^{15}$

Subtask:

• Subtask 1 (50% số điểm): $K \le 10^9$.
• Subtask 2 (50% 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.

Ví dụ 1 – input

3 10

Ví dụ 1 – output

2

Ví dụ 2 – input

3 12

Ví dụ 2 – output

3

• Ví dụ 1: em thứ nhất nhận 1 cái, em thứ hai nhận 4 cái (đã phát 5 cái), em thứ ba cần 7 cái nhưng chỉ còn 5 cái nên thầy dừng. Có 2 em nhận kẹo.
• Ví dụ 2: $1 + 4 + 7 = 12$ vừa đủ cho cả 3 em.

Nguồn: phỏng theo bài "PHÁT KẸO 2" – vinhdinhcoder.net (chủ đề Lặp FOR).

Lời mở đầu

Bài vòng lặp "mô phỏng" đầu tiên: cứ làm đúng như thầy Phú – phát cho từng em, trừ dần số kẹo, hết kẹo thì dừng. Có hai chỗ dễ sai: dừng đúng lúc (vừa đủ kẹo thì em đó vẫn được nhận) và kiểu dữ liệu – $K$ tới $10^{15}$, tổng số kẹo phát cho $10^5$ em lên tới khoảng $1{,}5 \cdot 10^{10}$, đều vượt int. Ghi chú: đề gốc không nói rõ, nhưng số em nhận kẹo không thể vượt quá số học sinh $N$ – mình ghi rõ trong đề.

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ưởngphát từng emLờ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 1–10 thuộc subtask 1 ($K \le 10^9$), test 11–20 có $K$ tới $10^{15}$.

Test	Nội dung kiểm tra
1–4, 6–8, 10	Số nhỏ: kẹo vừa đủ (ví dụ 2, test 6, 10), thiếu 1 viên (test 7), $K = 1$
5, 9	$K$ cỡ $10^9$: với $N = 1$ đáp án bị chặn bởi $N$; với $N = 10^5$ chỉ khoảng 25 nghìn em nhận được kẹo
11–14, 18	$K$ lớn tới $10^{15}$, đủ kẹo cho cả lớp, vừa đủ / thiếu 1 viên cho $10^5$ em
15–17, 19–20	$K$ vượt $2^{31}$ nhưng không đủ cho cả lớp: tổng đã phát vượt int

Ý tưởngPhát lần lượt từng em

Dùng biến keo là số kẹo em tiếp theo cần nhận (bắt đầu bằng 1). Với mỗi em $i = 1, 2, \ldots, N$:

• nếu keo > K (số kẹo còn lại) thì không đủ → dừng (break);
• ngược lại phát cho em: K = K - keo, tăng biến đếm, rồi keo = keo + 3 cho em sau.

Vòng lặp chạy tối đa $N \le 10^5$ lần – rất nhanh.

Kiểu dữ liệu

$K$ tới $10^{15}$ → phải dùng long long. Kể cả khi em cộng dồn "tổng đã phát" thay vì trừ dần $K$, tổng đó cũng lên tới $1 + 4 + \ldots + 299\,998 \approx 1{,}5 \cdot 10^{10}$ – vượt int.

Em nhập $N$, $K$ rồi bấm Tiếp để xem thầy phát kẹo cho từng em:

N = K =

Ví dụ nhanh:

Lời giảiVòng for + break

Vòng for chạy qua từng em, break khi hết kẹo. Mọi biến dùng long long.

C++▶ Chạy tay từng dòng codePhát kẹo cho từng em, không đủ thì break.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. break thoát ngay khỏi vòng lặp – em thứ $i$ không đủ kẹo thì các em sau (cần nhiều hơn) chắc chắn cũng không đủ.
2. Điều kiện là keo > k (không đủ), không phải keo >= k: còn vừa đúng keo cái thì em đó vẫn nhận được.
3. Vòng for chỉ chạy tới $N$ nên tự động không phát quá số học sinh.

Không gian$O(1)$

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.005s. Bản Python đúng 20/20 test, chạy lâu nhất 0.049s. 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 int cho $N$, $K$	11/20	sai test 11, 12, 13, 14, 15, 17, 18, 19, 20
Đọc $K$ bằng long long nhưng cộng dồn tổng đã phát bằng int	14/20	sai test 13, 15, 16, 17, 19, 20
while (keo <= k) – quên giới hạn $N$ học sinh	16/20	sai test 5, 11, 14, 18
Tăng biến đếm trước rồi mới kiểm tra (while (tong <= k)) → thừa 1 em	9/20	sai test 1, 4, 7, 8, 9, 13, 15, 16, 17, 19, 20
So sánh chặt: dừng khi tong + keo >= k (vừa đủ kẹo cũng dừng)	13/20	sai test 2, 3, 4, 6, 10, 12, 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.005s	Full điểm
	Python	20/20	0.049s	Full điểm
Dùng int	C++	11/20	–	Mất 9 test
Tổng kiểu int	C++	14/20	–	Mất 6 test
Quên giới hạn N	C++	16/20	–	Mất 4 test
Đếm trước, thừa 1	C++	9/20	–	Mất 11 test
So sánh chặt	C++	13/20	–	Mất 7 test

Ghi chú của mình: với bài "phát dần đến khi hết", hãy thử tay trường hợp vừa đủ (ví dụ 2: $1 + 4 + 7 = 12$) và thiếu đúng 1 để chắc chắn điều kiện dừng đúng.

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 😇