分解結合(2231)

2618 ワード
白駿 テキストリンク

Brute Force


質問する


ある自然数Nがある場合、その自然数Nの分解とは、NとNの各ビット数の和を意味する.ある自然数Mの分解とNであれば、MはNの生成者である.例えば、245の分解は256(=245+2+4+5)である.したがって、245は256の生成者となる.もちろん、いくつかの自然数の場合、構造関数がない可能性があります.逆に,生成者が複数ある自然数もある.
自然数Nが与えられた場合,Nの最小生成者を解くプログラムを作成する.

入力


第1行は自然数N(1≦N≦1000000)を与える.

しゅつりょく


最初の行に答えを印刷します.ジェネレータがない場合は0を出力します.
import sys

N = int(sys.stdin.readline())
start = 0
answer = 0

while start < N:
    check = start
    a = list(map(int, str(start)))
    check += sum(a)
            
    if (check == N):
        answer = start
        break;
        
    start += 1
    
print(answer)
数値=>文字列=>各ビット数を要素とする配列->配列の値を加算(繰り返し文よりsum()で処理する方が時間効率が良い)
[PRODrammers]キーボードを押す
hp-ux11.31オペレーティングシステム上のfilecacheパラメータ:filecache_maxとfilecache_min