QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#605088 | #2945. 1's For All | xyyy | TL | 0ms | 0kb | Python3 | 785b | 2024-10-02 15:26:27 | 2024-10-02 15:26:30 |
Judging History
answer
import sys
input = sys.stdin.read
n = int(input())
a = [2 * 10**9] * (n + 1) # 初始化数组,a[0] = 2e9,相当于无穷大
a[1] = 1
a[2] = 2
for i in range(3, n + 1):
a[i] = 2 * 10**9 # 设置为无穷大
for j in range(1, i):
if j > i - j:
break
a[i] = min(a[i], a[j] + a[i - j])
if i % j == 0:
k = i // j
a[i] = min(a[i], a[j] + a[k])
ji = 10
for k in range(1, 6): # k 从 1 到 5
aa = i % ji
bb = i // ji
if ji == 100 and aa < 10:
continue
if ji == 1000 and aa < 100:
continue
if ji == 10000 and aa < 1000:
continue
a[i] = min(a[i], a[aa] + a[bb])
ji *= 10
print(a[n])
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
100000