CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Numerot
Sender:tykkipeli
Submission time:2020-10-18 02:46:52 +0300
Language:Python3 (CPython3)
Status:READY
Result:12
Feedback
groupverdictscore
#1ACCEPTED12
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.88 s1, 2, 3details
#2--2, 3details
#3--3details

Code

dp = [[[[(0,0)]*11 for i in range(11)] for k in range(11)] for j in range(30)]
done = [[[[False]*11 for i in range(11)] for k in range(11)] for j in range(30)]
def maxdigit(n):
ans = 0
while n > 0:
ans = max(ans, n%10)
n //= 10
return ans
def solve(a,b,c,d):
if done[a][b][c][d]:
return dp[a][b][c][d]
done[a][b][c][d] = True
if a == 1:
dp[a][b][c][d] = (0,d)
return dp[a][b][c][d]
if c == 1:
if a == 2:
val = 10+d
cnt = 0
while val >= 10:
val -= max(b,maxdigit(val))
cnt += 1
dp[a][b][c][d] = (cnt,val)
return dp[a][b][c][d]
else :
if b > d:
p = solve(a-1,9,1,10+d-b-1)
pp = solve(a-1,b,9,p[1])
dp[a][b][c][d] = (p[0] + pp[0], pp[1])
return dp[a][b][c][d]
else:
x = max(1,b)
p = solve(a-1,9,1,10-x-1)
pp = solve(a-1,b,9,p[1])
lisa = 0
if d > 0:
lisa += 1
dp[a][b][c][d] = (p[0] + pp[0] + lisa, pp[1])
return dp[a][b][c][d]
else:
kaytossa = max(b,c)
if b >= c or a == 2:
p = solve(a,kaytossa,1,d)
pp = solve(a,b,c-1,p[1])
dp[a][b][c][d] = (p[0] + pp[0], pp[1])
return dp[a][b][c][d]
else:
if c > d:
p = solve(a,c-1,1,d-1)
pp = solve(a,b,c-1,p[1])
dp[a][b][c][d] = (p[0] + pp[0], pp[1])
return dp[a][b][c][d]
else:
p = solve(a,b,c,0)
dp[a][b][c][d] = (p[0] + 1, p[1])
return dp[a][b][c][d]
def ratkaise(x):
ans = 0
digit = x%10
ind = 1
while x > 0:
if x%10 != 0:
maxi = maxdigit(x//10)
#print(ind,maxi,x%10,digit)
p = dp[ind][maxi][x%10][digit]
ans += p[0]
digit = p[1]
x //= 10
ind += 1
return ans + 1
def pienempi(x, raja):
return ratkaise(x) < raja
for i in range(1,22):
for j in range(10):
for k in range(1,10):
for l in range(10):
solve(i,j,k,l)
t = int(input())
for i in range(t):
a = int(input())
x = 0
b = 10**20
while b >= 1:
while(pienempi(x+b, a)):
x += b
b //= 2
print(x+1)

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000
1
2
3
4
...

correct output
1
10
11
20
22
...

user output
1
10
11
20
22
...
Truncated

Test 2

Group: 2, 3

Verdict:

input
1000
224995
413660
249827
2125
...

correct output
1731724
3216040
1940719
14585
532612
...

user output
(empty)

Test 3

Group: 3

Verdict:

input
1000
627887018110416188
785474884983906653
653772166720939773
784335285960673683
...

correct output
5530371754830260284
6918696171534226533
5757755627065159149
6908439780325129803
3223801064342340738
...

user output
(empty)