Trò chơi nhân ba cộng một (CSES 1068)

Nguồn: CSES Problem Set Độ khó: Dễ Vòng lặp CSES 1068

Đề bài

Bạn Minh nghĩ ra một trò chơi với một số nguyên dương $n$. Ở mỗi lượt, Minh biến đổi $n$ như sau:

• nếu $n$ là số chẵn thì thay $n$ bằng $n / 2$;
• nếu $n$ là số lẻ thì thay $n$ bằng $3n + 1$.

Trò chơi kết thúc ngay khi $n$ trở thành $1$. Người ta đã kiểm chứng rằng với mọi $n$ trong giới hạn của bài, trò chơi luôn kết thúc.

Hãy in ra toàn bộ các giá trị mà $n$ nhận được trong quá trình chơi, bắt đầu từ giá trị ban đầu và kết thúc bằng số $1$.

Dữ liệu vào:

Một dòng duy nhất chứa số nguyên $n$.

Kết quả:

In trên một dòng các giá trị của $n$ theo đúng thứ tự xuất hiện, cách nhau bởi dấu cách.

Giới hạn:

• $1 \le n \le 10^6$
• Lưu ý: trong quá trình biến đổi, giá trị của $n$ có thể lớn hơn nhiều so với giá trị ban đầu.

Giới hạn thời gian: 1 giây, bộ nhớ: 512 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

6

Ví dụ 1 – output

6 3 10 5 16 8 4 2 1

Giải thích:

$6$ chẵn → $3$; $3$ lẻ → $10$; $10$ → $5$; $5$ → $16$; rồi $8, 4, 2, 1$. Nếu $n = 1$ ngay từ đầu thì chỉ in một số $1$.

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

Bài gốc tiếng Anh

Đề gốc trên CSES Problem Set, em cũng có thể nộp thử ở đó.

Mở bài trên CSES

Ý tưởng

Bài này chỉ cần mô phỏng đúng như đề: in $n$, rồi lặp while (n != 1): chẵn thì chia 2, lẻ thì nhân 3 cộng 1, mỗi lần biến đổi xong lại in $n$.

Chạy tay với $n = 6$: in 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1, dừng vì $n = 1$.

Điều quan trọng nhất: dù $n \le 10^6$ nhưng giá trị trung gian có thể lên tới khoảng $5,7 \cdot 10^{10}$ (ví dụ bắt đầu từ $704511$), vượt quá int, nên thầy dùng long long.

Lưu ý / bẫy thường gặp

• Dùng int → tràn số với những $n$ có giá trị trung gian lớn (ví dụ $n = 113383$).
• Quên in giá trị ban đầu, hoặc dừng vòng lặp trước khi in số $1$.
• Dùng do ... while (biến đổi trước rồi mới kiểm tra): với $n = 1$ sẽ in 1 4 2 1 thay vì 1.

Lời giải

Code chuẩn bên dưới đã chấm đúng toàn bộ 20 test trên CLUE OJ.

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 😇