Xếp que

Nguồn: CLUE OJ Độ khó: Dễ Rẽ nhánh Tìm quy luật

Đề bài

Xu đang dạy em Xốp học toán lớp một. Xu dùng que tính để em Xốp xếp thành các phép cộng $A + B = C$, trong đó $A, B, C$ là các số nguyên dương, mỗi số được xếp bằng đúng số que bằng giá trị của nó (dấu $+$ và dấu $=$ không cần que). Ví dụ phép tính $1 + 2 = 3$ cần $1 + 2 + 3 = 6$ que tính, phép tính $1 + 1 = 2$ cần $4$ que tính.

Xu đưa cho em Xốp $N$ que tính. Hỏi em Xốp cần lấy thêm ít nhất bao nhiêu que tính nữa để có thể dùng hết tất cả số que đang có xếp thành một phép cộng đúng?

Ví dụ: với $N = 1$, em Xốp cần lấy thêm ít nhất $3$ que để xếp $1 + 1 = 2$. Với $N = 20$, em Xốp không cần lấy thêm que nào vì xếp được ngay $4 + 6 = 10$.

Dữ liệu vào:

Một số nguyên dương $N$.

Kết quả:

In ra một số nguyên không âm là số que tính ít nhất cần lấy thêm.

Giới hạn:

• $1 \le N \le 10^9$

Subtask:

• Subtask 1 (60% số điểm): $N \le 20$.
• Subtask 2 (40% số điểm): $21 \le N \le 10^9$.

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

Ví dụ 1 – output

1

Ví dụ 2 – input

20

Ví dụ 2 – output

0

• Ví dụ 1: có 3 que, lấy thêm 1 que để xếp $1 + 1 = 2$.
• Ví dụ 2: xếp được ngay $4 + 6 = 10$ (dùng đủ $4 + 6 + 10 = 20$ que).

Nguồn: phỏng theo bài "XẾP QUE" – vinhdinhcoder.net (chủ đề Rẽ nhánh).

Lời mở đầu

Bài "tư duy" đầu tiên: không cần thử từng phép cộng, chỉ cần nhận ra số que của một phép cộng đúng luôn có một tính chất đặc biệt. Ghi chú: đề gốc ghi "in ra số nguyên dương" nhưng đáp án có thể bằng 0 (như $N = 20$), mình sửa thành "số nguyên không âm".

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ưởngchẵn và ≥ 4Lờ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–12 thuộc subtask 1 ($N \le 20$), test 13–20 có $N$ tới $10^9$.

Test	Nội dung kiểm tra
1–12	$N = 1, 2, 3$ (chưa đủ 4 que), $N = 4$, các số chẵn / lẻ tới 20
13–20	$N$ lớn tới $10^9$, chẵn và lẻ

Ý tưởngSố que luôn chẵn và ít nhất 4

Phép cộng $A + B = C$ dùng $A + B + C$ que. Vì $C = A + B$ nên số que là $A + B + C = 2C$ – luôn là số chẵn. Và $A, B \ge 1$ nên $C \ge 2$, số que $\ge 4$.

Ngược lại, mọi số chẵn $M \ge 4$ đều xếp được: lấy $C = M / 2$, $A = 1$, $B = C - 1$. Vậy bài toán thành: tìm số chẵn $M \ge 4$ nhỏ nhất mà $M \ge N$.

• $N < 4$: cần lấy thêm $4 - N$ que.
• $N \ge 4$, $N$ chẵn: không cần thêm (0 que).
• $N \ge 4$, $N$ lẻ: thêm 1 que.

Gọn lại

Nếu $N < 4$ in $4 - N$, ngược lại in N % 2.

Em nhập dữ liệu rồi bấm Tiếp để xem chương trình xét từng điều kiện:

N =

Ví dụ nhanh:

Lời giảiHai trường hợp

Một câu if / else.

C++▶ Chạy tay từng dòng codeChưa đủ 4 que thì bù cho đủ, ngược lại xét chẵn lẻ.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Phép % (chia lấy dư): n % 2 bằng 0 khi $n$ chẵn, bằng 1 khi $n$ lẻ – đúng bằng số que cần thêm.
2. Không cần vòng lặp thử từng số que: tìm ra quy luật "số chẵn ≥ 4" là xong trong $O(1)$.

Không gian$O(1)$

Thời gian$O(1)$

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.023s. 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ỉ xét chẵn lẻ (cout << n % 2), quên trường hợp $N < 4$	18/20	sai test 2, 3

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.023s	Full điểm
Quên N < 4	C++	18/20	–	Mất 2 test

Ghi chú của mình: trước khi code, hãy thử tay vài giá trị nhỏ ($N = 1, 2, 3, 4, 5$) để tìm quy luật – bài này chỉ cần nhận ra "số que luôn chẵ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 😇