Task: | Numerot |
Sender: | tykkipeli |
Submission time: | 2020-10-18 02:46:52 +0300 |
Language: | Python3 (CPython3) |
Status: | READY |
Result: | 12 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | TIME LIMIT EXCEEDED | 0 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.88 s | 1, 2, 3 | details |
#2 | TIME LIMIT EXCEEDED | -- | 2, 3 | details |
#3 | TIME LIMIT EXCEEDED | -- | 3 | details |
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 = 0while n > 0:ans = max(ans, n%10)n //= 10return ansdef solve(a,b,c,d):if done[a][b][c][d]:return dp[a][b][c][d]done[a][b][c][d] = Trueif a == 1:dp[a][b][c][d] = (0,d)return dp[a][b][c][d]if c == 1:if a == 2:val = 10+dcnt = 0while val >= 10:val -= max(b,maxdigit(val))cnt += 1dp[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 = 0if d > 0:lisa += 1dp[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 = 0digit = x%10ind = 1while 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 //= 10ind += 1return ans + 1def pienempi(x, raja):return ratkaise(x) < rajafor 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 = 0b = 10**20while b >= 1:while(pienempi(x+b, a)):x += bb //= 2print(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: TIME LIMIT EXCEEDED
input |
---|
1000 224995 413660 249827 2125 ... |
correct output |
---|
1731724 3216040 1940719 14585 532612 ... |
user output |
---|
(empty) |
Test 3
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 627887018110416188 785474884983906653 653772166720939773 784335285960673683 ... |
correct output |
---|
5530371754830260284 6918696171534226533 5757755627065159149 6908439780325129803 3223801064342340738 ... |
user output |
---|
(empty) |