2231 분해합

Digit Generator 성공 원문과 다름

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	192 MB	6457	3730	3065	56.249%

문제

For a positive integer N, the digit-sum of N is defined as the sum of N itself and its digits. When M is the digitsum of N, we call N a generator of M.

For example, the digit-sum of 245 is 256 (= 245 + 2 + 4 + 5). Therefore, 245 is a generator of 256.

Not surprisingly, some numbers do not have any generators and some numbers have more than one generator. For example, the generators of 216 are 198 and 207.

You are to write a program to find the smallest generator of the given integer.

입력

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case takes one line containing an integer N, 1 ≤ N ≤ 100,000.

출력

Your program is to write to standard output. Print exactly one line for each test case. The line is to contain a generator of N for each test case. If N has multiple generators, print the smallest. If N does not have any generators, print 0.

여기서 중요한건 N이 100,000까지 라는 것이다.

그렇다면 100,000을 만들수 있는 생성자는 아무리 억지를 부려도 99999

즉 원본을 제외한 각 숫자 자리의 합의 최대치는 아무리 억지를 부려도 9*5=45이다.

그러니까 N에서 45적은 숫자부터 1개씩 올려가며 그 숫자의 분해합을 구해서 N과 일치하는 것을 찾으면 된다.\

그리고 45전으로 돌아갈떄 음수가 안되도록 미리 조치를 취해주자.

아래는 코드

import sys

sys.stdin = open("input.txt", "r");

n = (sys.stdin.readline())

suc = False

a = (int(n)-45) if (int(n)>45) else int(n)

for i in range(46):

a_str = map(int,list(str(a+i)))

#print("{0} => {1}".format(a+i,a+i + sum(a_str)))

if (a+i + sum(a_str) is int(n)):

print(a+i)

suc = True

break

if(suc is False):

print(0)