100番のヒント

何を計算すればよいのか?

  • ある正の数を考えます。
  • もしその数が奇数なら3倍して1加算します。もし偶数なら2で割ります。
  • 上の計算を繰り返してゆくと,どんな数でもいつかは必ず1になります。
  • たとえば22なら,22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1となります。
  • この場合,上に示したように1になるまでに必要なサイクルは16となります。
  • 問題ではある範囲が与えられますので,その範囲の数で1になるまでのサイクルの最大値を求めます。
  • たとえば,問題のページの「Sample Input」の1行目を見てください。「1 10」となっています。1から10まで,すなわち1, 2, 3, …, 10がそれぞれ1になるまでのサイクルの中の最大値を求めればよいわけです。
  • 1のサイクルは1,2のサイクルは2,3のサイクルは8,…となり,9のサイクルは20となります。1から10までのサイクルの最大値は9の場合の20ですので,「Sample Output」の1行目では範囲「1 10」に続いてその最大値20を表示しています。
  • 入力データがなくなるまで上記の計算を繰り返します。

データの入出力

採点される際の入出力はすべて標準入出力が使用されます。入力にはscanf(),出力にはprintf()puts(), putchar()などを使うとよいでしょう。

この問題では入力データは1行ごとに一つのペア(スペースで区切られた二つの整数)が書かれていて,このペア(すなわち行)がどれだけ連続するかは不明です。scanf()関数は正常に読み込めた項目の数を返却値とすることを利用して,次のようするとよいでしょう。

int main()
{
    使用する変数の宣言

    while(scanf("%d %d", &a, &b) == 2){

        この部分で計算

        printf("%d %d %d\n", a, b, c);
    }

    return 0;
}

入力データがなくなるとscanf()関数から2以外の値(EOF)が返却されますから,条件が不成立でwhileループが終了します。

所要サイクルの計算

引数として与えられた数が1になるまでどれだけのサイクルを要するかを計算する関数を定義するとよいでしょう。

int cycle(int n)
{
    int count;

    for(count = 1; n != 1; count++){
        if(奇数)
            n ← 3n + 1
        else
            n ← n/2;
    }

    return count;
}

nが1以外の場合にループし,nが奇数か偶数かにより値を更新し,countに1ずつ加算しています。forの部分はもちろんwhileを用いても記述できます。

最大値の計算

この問題は指定された範囲の所要サイクルの最大値を求めるわけですから,この範囲の値を順に先ほど定義したcycle()関数に引数として渡し,それらの返却値の中の最大値を求めればOKです。
注意するのは,入力データ中の範囲を指定する二つの値の大小関係がどのような順になっているかわからない点です。すなわち,

1 10

のようになっている場合もあれば,

10 1

のようになっている場合もあるので,いずれも場合でも正しく処理できるようにする必要があります。参考までに,上述の入力データを計算した出力を記載しておきます。

Sample Input

1 10
10 1

Sample Output

1 10 20
10 1 20

プログラムのテスト方法

問題のページには実行例として「Sample Input」と「Sample Output」が記載されています。プログラムが完成したら,まずはこの「Sample Input」を入力してみて「Sample Output」とまったく同じ出力が得られるか確認しましょう。

「Sample Input」のデータ部分をコピーして入力データファイルを作成します。たとえば,100番の入力データファイルなら「100.in」という名前にして保存します。

実行ファイル名が「100」の場合,Windowsのコマンドプロンプトから,

100 < 100.in

とすることで,プログラム「100」を実行してファイル「100.in」の内容を標準入力から読み込ませることができます。もしUNIXの場合には,

./100 < 100.in

としてください。

「Sample Output」とまったく同じ出力が得られるようならプログラムを提出してみましょう。実際の採点の際は「Sample Input」に記載されているデータよりも複雑で大規模な入力データが使用されますので,「Sample Input」では正常に動いたからといって正解になるとは限りません。