[Bronze I] The Easiest Problem is This One - 6627
성능 요약
메모리: 110708 KB, 시간: 144 ms
분류
브루트포스 알고리즘, 구현, 수학
제출 일자
2025년 2월 12일 18:09:15
문제 설명
If you are the lucky one to advance to the ACM-ICPC World Finals, one of the situations you will face is the world finals competition itself. Wait, isn’t that the main reason to go there?
In the beginning of each ACM-ICPC competition, there are two separate goals each team tries to accomplish:
among the given set of problems, find the easiest one,
solve that problem as fast as possible.
To evaluate the performance of all teams in detail, we want to test your abilities for each of these two goals separately. The former goal (finding the easiest problem) is analyzed in another problem (difficult), here we deal with the latter goal (solving the easiest problem).
To isolate other influences, we will tell you clearly which problem is the easiest one to solve in this problem set (CTU Open Contest 2010). It is this one! What more can we do to emphasize that fact? The title says it. The problem name is easy. And believe us, it is true. This is indeed the easiest of all nine problems. We recommend you to do it first.
A positive integer number N can be expressed in the decimal system (numeral system with the base of 10) as the sequence of digits di
N=d1d2d3d4…dk
where ∀i, 1 ≤ i ≤ k : 0 ≤ di ≤ 9.
The digits express the value which has to be multiplied by a power of ten:
N=d1⋅10k−1+d2⋅10k−2+⋯+dk−1⋅10+dk=∑i=0k−1di+1⋅10k−i−1
The sum of the digits S(N) is then defined as the plain sum of all individual digits without multiplying them by powers of ten:
S(N)=d1+d2+d3+⋯+dk=∑i=0k−1di+1
For example:
N=3029=3⋅103+2⋅10+9S(N)=3+0+2+9=14
If we multiply the original number N with another number m, the sum of the digits typically changes. For example, if m1=26:
N⋅m1=78754=7⋅104+8⋅103+7⋅102+5⋅10+4S(N⋅m1)=7+8+7+5+4=31
However, there are some numbers that, if multiplied by N, will result in the same sum of the digits as the original number N. For example, consider m2=37:
N⋅m2=112073=105+104+2⋅103+7⋅10+3S(N⋅m2)=1+1+2+0+7+3=14=S(N)
Your task is to find the smallest positive integer p among those that will result in the same sum of the digits when multiplied by N. To make the task a little bit more challenging, the number must also be higher than ten.
입력
The input consists of several test cases. Each case is described by a single line containing one positive integer number N, 1 ≤ N ≤ 100 000. The last test case is followed by a line containing zero.
출력
For each test case, print one line with a single integer number p which satisfies all of the following conditions:
- p > 10
- S(N) = S(N⋅p)
- ∀q∈N:[S(N)=S(N⋅q)]⇒[(q≥p)∨(q≤10)]
풀이
def div_sum(num) :
res = 0
while num > 0 :
res += num % 10
num //= 10
return res
lst = []
while True :
N = int(input())
if N == 0 :
break
ans = div_sum(N)
for p in range(11, 1<<32 + 1) :
number = N * p
res = div_sum(number)
if res == ans :
print(p)
break영어로 되어 있기도 하고 문제의 의도를 잘 파악하지 못하여서 챗GPT의 도움을 조금 받았다. 챗 GPT에게 문제에 대해서 설명해달라고 하였고, 이후 문제의 의도를 파악할 수 있었다.
$N$의 각 자리마다의 수를 더해서 나오는 수와 $N \times p$의 값의 각 자리마다의 수를 더해서 나온 수가 같은 값이 나올때의 $p$값을 구하는 문제이다.
글로 하니까 좀 엉성하긴 한데, 결국 $S(N) = S(N \times p)$ 라는 것이다. 여기서 S는 코드 상의 div_sum 함수이다.
그 다음은 쉽게 풀이할 수 있다. 영어 공부를 충실히 해야 겠다는 생각이 들었다.
'알고리즘 스터디' 카테고리의 다른 글
| [백준/파이썬][Silver III] Password Problem (Large) - 12395 (0) | 2025.02.13 |
|---|---|
| [백준/파이썬][Silver III] Out of Place - 15594 (0) | 2025.02.13 |
| [백준/파이썬][Bronze II] 번호표 교환 - 11949 (0) | 2025.02.12 |
| [백준/파이썬][Gold IV] PC방 요금 - 9080 (0) | 2025.02.11 |
| [백준/파이썬][Gold IV] 떡 돌리기 - 20007 (1) | 2025.02.09 |