全国統一プログラミング王決定戦 エキシビジョン F - コラッツ問題 (300 点)

一発芸問題

問題へのリンク

問題概要

整数 に対し、

• のとき
• それ以外で のとき
• それ以外で が偶数のとき
• それ以外で が奇数のとき

で定義される。

整数 が与えられます。となるような 以下の正整数 をいずれか 1 つ出力してください。

ただし、 であることがわかっている。

制約

• 

解法

になにを入れても、いつかは

• 
• 

に行き着いて、そこで 0 となり、そこから再帰を戻って行って、1, 2, 3, ... となって行く。

例えば

という具合になる。ここからわかることは、 だったら だし だし...ということ。

つまり我々は という情報を得ているので、これを利用して、 として、

• a が偶数だったら 2 で割る
• a が奇数だったら 3 をかけて 1 を足す

という操作を順々に行っていくと、 のときの解が得られるものと考えることができる。

#include <iostream>
using namespace std;

long long Next(long long n) {
    if (n % 2 == 0) return n/2;
    else return n*3 + 1;
}

int main() {
    int P; cin >> P;
    long long start = 1789997546303LL;
    for (int i = 0; i < 1000 - P; ++i) {
        start = Next(start);
    }
    cout << start << endl;
}