JOI 一次予選 2024 (第 2 回) D - 繰り返し (6Q, 難易度 3)

for 文や while 文を書き慣れている人でも、終了条件を「反復回数満了」以外の方法で記述するのは、意外と戸惑うかもしれない。

• 問題へのリンク
• editorial

問題概要

黒板に書かれた整数に対して、以下の操作を繰り返し行う。

• 書かれた整数 が 3 で割り切れるとき： に 1 を足す
• 書かれた整数 を 3 で割った余りが 1 のとき： に 2 をかける
• 書かれた整数 を 3 で割った余りが 2 のとき： に 3 をかける

最初に が書かれている。黒板に書かれた数が 以上になるまでの操作回数を求めよ。

制約

• 

解法

while 文などが使えます。黒板に書かれた数が 以上になるまで操作を繰り返すとは、言い換えれば

---

黒板に書かれた数が 未満であるうちは、操作を繰り返す

---

となります。このように、「〜以上になるまで繰り返す」を「〜未満であるうちは繰り返す」と読み替えることは、今後とても大切なスキルになります。

よって、次のように書けばよいでしょう。

int res = 0;  // 操作回数を表す変数
while (X < N) {
    (X に対する操作);
    ++res;  // 操作回数を増やす
}

解答例コード

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

int main() {
    int x, N, res = 0;
    cin >> x >> N;
    while (x < N) {
        if (x % 3 == 0) x += 1;
        else if (x % 3 == 1) x *= 2;
        else x *= 3;
        ++res;
    }
    cout << res << endl;
}