Hướng dẫn giải của [Beginner Free Contest 18] GIFT


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Hướng dẫn giải

Với mỗi số n, thực hiện biến đổi n → n/2 nếu n chẵn và n → 3n+1 nếu n lẻ cho đến khi n = 1. Đếm số phép biến đổi (T ≤ 1000, n ≤ 10^6).

Sub 1: Mô phỏng trực tiếp — ~O(steps) mỗi test~

Làm đúng theo đề: lặp lại phép biến đổi và đếm số bước cho đến khi n = 1. Số bước với n ≤ 10^6 rất nhỏ (vài trăm), nên cách này đủ nhanh. Dùng long long vì 3n+1 có thể vượt int.

Kết quả chấm: 6/6 (PASS 6/6)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        long long n;
        cin >> n;
        // Mo phong dung cong thuc: n chan thi n/2, n le thi 3n+1; dem so buoc den khi n = 1.
        // Gia tri co the lon hon int nen dung long long.
        int buoc = 0;
        while (n != 1) {
            if (n % 2 == 0) n /= 2;
            else n = 3 * n + 1;
            buoc++;
        }
        cout << buoc << "\n";
    }
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.