CSES 1068 - Weird Algorithm

題目

Problem#

給你一個正整數 $n$，如果 $n$ 是偶數則除 $2$；如果 $n$ 是奇數則乘以 $3$ 加上 $1$，一直做下去直到變成 $1$
問你數字的變化過程

測資限制#

• $1 \le n \le 10^6$

想法#

3n+1 問題，模擬即可

• 時間複雜度: $\mathcal{O}(n)$
• 空間複雜度: $\mathcal{O}(1)$

AC Code#

Copy

/*
 * CSES 1068 - WeirdAlgorithm
 * author: roy4801
 * AC(C++)
 */
#include <bits/stdc++.h>
using namespace std;
 
#define PROB "WeirdAlgorithm"
#define TESTC ""
 
#define USE_CPPIO() ios_base::sync_with_stdio(0); cin.tie(0)
typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int, int> P;
typedef pair<LL, LL> PLL;
#define F first
#define S second
#define INF 0x3f3f3f3f
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PPB pop_back
#define PF push_front
#define PPF pop_front
 
LL n;
int main()
{
    cin >> n;
    printf("%lld", n);
    while(n != 1)
    {
        if(n % 2 != 0)
            n = n*3 + 1;
        else
            n /= 2;
        printf(" %lld", n);
    }
}

view raw cses/Weird_Algorithm.cpp delivered with ❤ by emgithub