バックアップアルゴリズム4673号:セルフ・サービス番号

質問リンク

https://www.acmicpc.net/problem/4673

制限

質問する

セルフサービス番号は1949年にインドの数学者D.R.Kaprekarによって命名された.正の整数nについて、d(n)がnおよびnの各ビット数の関数を定義する.例えば、d(75)=75+7+5=87である.
正の整数nが与えられると、その数からn、d(n)、d(d(n)、d(d(d(n))、...無限数列を生成できます.
たとえば、33で始まると、次の数字は33+3+3=39、次の数字は39+3+9=51、次の数字は51+5+1=57となります.このようにして、次の数の列を生成できます.
33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...
nをd(n)の生成者と呼ぶ.上の数列において、33は39の生成者、39は51の生成者、51は57の生成者である.生成者が1つより多い場合もあります.例えば、101には2つの構造関数(91および100)がある.
生成されていない数字を自動番号と呼びます.100未満のセルフサービス番号は全部で13個です.1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97
10000以下のセルフ・サービス番号を出力するプログラムを作成します.

入力

入力していません.

しゅつりょく

10000以下の自己符号を行ごとに1つ追加する順序で出力します.

入力と出力の例

に答える

すべてのセルフサービス番号を見つけるのは難しいので、逆に探しているのはセルフサービス番号の数ではありません(作成者たち).

10001サイズのint型配列を宣言し、セルフ・サービス番号を求める関数を宣言します.

自動番号は、n単位でビット数を加算した生成者であるため、getSelfNumberでsumに入力したnを加算し、n>0まで各ビット数を加算し続けると、その数は自動番号ではないので、配列arrでsumのインデックスを1(TRUE)にすると、自動番号ではない数字を配列から除外することができる.

アレイarrで出力値が1の数字でない場合は、自己符号のみが出力されます.

プールコード

#include <stdio.h>
#define size 10001

int arr[size];

void getSelfNumber(int n){
  int sum = n;
  while(n > 0){
    sum += n % 10;
    n /= 10;
  }
  arr[sum] = 1;
}

int main(){
  for(int i = 1; i <= size - 1; i++){
    getSelfNumber(i);
    if(arr[i] != 1){
      printf("%d\n",i);
    }
  }
  return 0;
}

資格認定

ふくガス

問題自体は難しくありませんが、初めて近づくときは、自分の番号を求めて近づくのに時間がかかりました.