病院の部屋番号

パソコン甲子園2009 問題04 病院の部屋番号

問題文

4と6の数字を使わない数字の列S = {1, 2, 3, 5, 7, 8, 9, 10, 11, 12, 13, 15, ...} のn番目の数を求めよという問題です。ただし、nの値は最大1,000,000,000です。

nの値が非常に大きいため、数列を生成して解くことはできません。4と6の2つの数字を用いてはいけないので、10 – 2 = 8 進数でnを表せばよいことになります。ただし、基数変換後の数の各桁の数字をdとすると、dが0～3の場合はそれぞれ0～3、dが4の場合はd+1(4の分)= 5、dが5以上の場合はd+2(4と6の分)に変換して出力します。文字列”01235789”のd番目の文字を返す関数を定義しても良いでしょう。

#include<iostream>
using namespace std;

int getValue(int x){
    if ( x == 4 ) return 5;
    return (x < 4) ? x : x+2;
}

void convert( int n ){
    if ( n == 0 ) return;
    convert( n/8 );
    cout << getValue(n%8);
}

main(){
    int n;
    while( cin >> n && n ) { convert(n); cout << endl; }
}