QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#84522 | #1875. Nein | magicduck | AC ✓ | 302ms | 3540kb | C++14 | 1.9kb | 2023-03-06 15:35:46 | 2023-03-06 15:35:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T> inline void read(T &FF) {
int RR = 1; FF = 0; char CH = getchar();
for(; !isdigit(CH); CH = getchar()) if(CH == '-') RR = -RR;
for(; isdigit(CH); CH = getchar()) FF = FF * 10 + CH - 48;
FF *= RR;
}
inline void file(string str) {
freopen((str + ".in").c_str(), "r", stdin);
freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 42;
LL g[N][N * 9];
void Add(LL &x, LL y) {
x += y; x = min(x, (LL)(2e18));
}
LL mul(LL x, LL y) {
return min((__int128)(2e18), (__int128)(x) * y);
}
void init() {
g[0][0] = 1;
for(int i = 1; i <= 40; i++)
for(int j = 0; j <= i * 8; j++)
for(int k = 0; k <= 8; k++)
if(k <= j) Add(g[i][j], g[i - 1][j - k]);
}
int k; LL n, f[N][N];
LL calc(__int128 x, int l) {
memset(f, 0, sizeof(f)); f[0][0] = 1;
for(int i = 1; i <= k; i++, x /= 10) {
const int len = (i <= l % k ? (l - 1) / k + 1 : l / k);
for(int j = 0; j <= 40; j++)
for(int k = (x - j + 40) % 10; k <= 320; k += 10)
Add(f[i][(j + k) / 10], mul(g[len][k], f[i - 1][j]));
}
x = min(x, (__int128)(40)); return f[k][x];
}
void print(__int128 x) {
if(x < 10) {
putchar('0' + x); return;
}
print(x / 10); putchar('0' + x % 10);
}
int main() {
//file("");
read(k), read(n); n++; init();
LL m = 1;
for(int i = 1; i <= k; i++) m = m * 10; m--;
LL s = 0; __int128 ans = 0;
for(int i = 38; i >= 1; i--) {
LL r = 1; __int128 G = 1;
for(int j = 1; j < i; j++) G = G * 10;
for(int j = 1; j < i; j++) r = (__int128)(r) * 10 % m;
for(int j = 0; j <= 8; j++) {
LL sum = 0;
for(int v = 0; v <= 20; v++)
Add(sum, calc(s + v * (__int128)(m), i - 1));
if(sum >= n) break;
n -= sum; ans += G; s = (s + m - r) % m;
}
}
//assert(ans % m == 0);
ans /= m; print(ans); puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 3404kb
input:
1 1
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 6ms
memory: 3460kb
input:
1 8
output:
9
result:
ok answer is '9'
Test #3:
score: 0
Accepted
time: 4ms
memory: 3472kb
input:
1 9
output:
12
result:
ok answer is '12'
Test #4:
score: 0
Accepted
time: 3ms
memory: 3432kb
input:
1 10
output:
13
result:
ok answer is '13'
Test #5:
score: 0
Accepted
time: 31ms
memory: 3384kb
input:
5 1
output:
11112
result:
ok answer is '11112'
Test #6:
score: 0
Accepted
time: 37ms
memory: 3412kb
input:
5 84
output:
11235
result:
ok answer is '11235'
Test #7:
score: 0
Accepted
time: 35ms
memory: 3472kb
input:
5 668
output:
12345
result:
ok answer is '12345'
Test #8:
score: 0
Accepted
time: 38ms
memory: 3400kb
input:
5 733942
output:
2281488
result:
ok answer is '2281488'
Test #9:
score: 0
Accepted
time: 286ms
memory: 3540kb
input:
18 528599760553218747
output:
30725517742188427234
result:
ok answer is '30725517742188427234'
Test #10:
score: 0
Accepted
time: 296ms
memory: 3480kb
input:
18 964828716126767591
output:
55758681752658348563
result:
ok answer is '55758681752658348563'
Test #11:
score: 0
Accepted
time: 293ms
memory: 3412kb
input:
18 401057671700316435
output:
22687686284122211545
result:
ok answer is '22687686284122211545'
Test #12:
score: 0
Accepted
time: 299ms
memory: 3464kb
input:
18 837286627273865280
output:
48255733668453323265
result:
ok answer is '48255733668453323265'
Test #13:
score: 0
Accepted
time: 297ms
memory: 3396kb
input:
18 273515582847414124
output:
15116382182883344554
result:
ok answer is '15116382182883344554'
Test #14:
score: 0
Accepted
time: 283ms
memory: 3460kb
input:
18 55923968082999579
output:
2876461768512185545
result:
ok answer is '2876461768512185545'
Test #15:
score: 0
Accepted
time: 84ms
memory: 3460kb
input:
8 715524960511324231
output:
12022650248772112989
result:
ok answer is '12022650248772112989'
Test #16:
score: 0
Accepted
time: 259ms
memory: 3540kb
input:
16 151753916084873076
output:
6182363727541142425
result:
ok answer is '6182363727541142425'
Test #17:
score: 0
Accepted
time: 16ms
memory: 3392kb
input:
2 587982875953389216
output:
4754915500630529532
result:
ok answer is '4754915500630529532'
Test #18:
score: 0
Accepted
time: 115ms
memory: 3396kb
input:
10 24211831526938061
output:
410770411555582497
result:
ok answer is '410770411555582497'
Test #19:
score: 0
Accepted
time: 302ms
memory: 3412kb
input:
18 460440787100486905
output:
26131416714411853682
result:
ok answer is '26131416714411853682'
Test #20:
score: 0
Accepted
time: 95ms
memory: 3460kb
input:
8 896669742674035749
output:
14750223579258782248
result:
ok answer is '14750223579258782248'
Test #21:
score: 0
Accepted
time: 168ms
memory: 3412kb
input:
12 556270735102360402
output:
13827553636696643430
result:
ok answer is '13827553636696643430'
Test #22:
score: 0
Accepted
time: 25ms
memory: 3540kb
input:
2 992499694970876542
output:
8147123087598806742
result:
ok answer is '8147123087598806742'
Test #23:
score: 0
Accepted
time: 102ms
memory: 3480kb
input:
9 191349424180689911
output:
3224103375245122149
result:
ok answer is '3224103375245122149'
Test #24:
score: 0
Accepted
time: 12ms
memory: 3384kb
input:
1 1000000000000000000
output:
7317596822929805779
result:
ok answer is '7317596822929805779'
Test #25:
score: 0
Accepted
time: 21ms
memory: 3388kb
input:
2 1000000000000000000
output:
8207298656583156714
result:
ok answer is '8207298656583156714'
Test #26:
score: 0
Accepted
time: 29ms
memory: 3456kb
input:
3 1000000000000000000
output:
10124840976332612776
result:
ok answer is '10124840976332612776'
Test #27:
score: 0
Accepted
time: 44ms
memory: 3480kb
input:
4 1000000000000000000
output:
11134918859204347753
result:
ok answer is '11134918859204347753'
Test #28:
score: 0
Accepted
time: 45ms
memory: 3392kb
input:
5 1000000000000000000
output:
12248384925950595769
result:
ok answer is '12248384925950595769'
Test #29:
score: 0
Accepted
time: 73ms
memory: 3408kb
input:
6 1000000000000000000
output:
13481441167144812720
result:
ok answer is '13481441167144812720'
Test #30:
score: 0
Accepted
time: 77ms
memory: 3516kb
input:
7 1000000000000000000
output:
14851839567286627600
result:
ok answer is '14851839567286627600'
Test #31:
score: 0
Accepted
time: 76ms
memory: 3476kb
input:
8 1000000000000000000
output:
16400312227388843586
result:
ok answer is '16400312227388843586'
Test #32:
score: 0
Accepted
time: 95ms
memory: 3412kb
input:
9 1000000000000000000
output:
18070802619848417970
result:
ok answer is '18070802619848417970'
Test #33:
score: 0
Accepted
time: 123ms
memory: 3392kb
input:
10 1000000000000000000
output:
18876263506622668979
result:
ok answer is '18876263506622668979'
Test #34:
score: 0
Accepted
time: 129ms
memory: 3428kb
input:
11 1000000000000000000
output:
22516357784746378893
result:
ok answer is '22516357784746378893'
Test #35:
score: 0
Accepted
time: 160ms
memory: 3384kb
input:
12 1000000000000000000
output:
25606071173776613626
result:
ok answer is '25606071173776613626'
Test #36:
score: 0
Accepted
time: 165ms
memory: 3428kb
input:
13 1000000000000000000
output:
30153652575287329992
result:
ok answer is '30153652575287329992'
Test #37:
score: 0
Accepted
time: 184ms
memory: 3404kb
input:
14 1000000000000000000
output:
34032144146113465692
result:
ok answer is '34032144146113465692'
Test #38:
score: 0
Accepted
time: 233ms
memory: 3520kb
input:
15 1000000000000000000
output:
38476235652741893950
result:
ok answer is '38476235652741893950'
Test #39:
score: 0
Accepted
time: 246ms
memory: 3476kb
input:
16 1000000000000000000
output:
44453843638835448269
result:
ok answer is '44453843638835448269'
Test #40:
score: 0
Accepted
time: 273ms
memory: 3396kb
input:
17 1000000000000000000
output:
51178357488582512218
result:
ok answer is '51178357488582512218'
Test #41:
score: 0
Accepted
time: 288ms
memory: 3520kb
input:
18 1000000000000000000
output:
57644143667246653868
result:
ok answer is '57644143667246653868'
Test #42:
score: 0
Accepted
time: 153ms
memory: 3432kb
input:
11 169906399332236675
output:
3542071158723189134
result:
ok answer is '3542071158723189134'
Test #43:
score: 0
Accepted
time: 118ms
memory: 3392kb
input:
10 836507396055528616
output:
15844261021999264957
result:
ok answer is '15844261021999264957'
Test #44:
score: 0
Accepted
time: 284ms
memory: 3468kb
input:
18 271736347334110166
output:
14838142784382116438
result:
ok answer is '14838142784382116438'
Test #45:
score: 0
Accepted
time: 189ms
memory: 3540kb
input:
13 705965302907659012
output:
20780554485617714682
result:
ok answer is '20780554485617714682'
Test #46:
score: 0
Accepted
time: 276ms
memory: 3540kb
input:
17 141194262776175153
output:
6535463816612312328
result:
ok answer is '6535463816612312328'
Test #47:
score: 0
Accepted
time: 139ms
memory: 3464kb
input:
12 575423218349724000
output:
14318523724188758677
result:
ok answer is '14318523724188758677'
Test #48:
score: 0
Accepted
time: 128ms
memory: 3408kb
input:
11 10652178218240141
output:
201716847375538682
result:
ok answer is '201716847375538682'
Test #49:
score: 0
Accepted
time: 226ms
memory: 3408kb
input:
15 677253166351597490
output:
25718425137845667325
result:
ok answer is '25718425137845667325'
Test #50:
score: 0
Accepted
time: 224ms
memory: 3416kb
input:
14 112482121925146336
output:
3478827471866842353
result:
ok answer is '3478827471866842353'
Test #51:
score: 0
Accepted
time: 165ms
memory: 3460kb
input:
13 138182159835368774
output:
3736504553128889177
result:
ok answer is '3736504553128889177'
Test #52:
score: 0
Accepted
time: 286ms
memory: 3436kb
input:
17 572411115408917620
output:
28263577418567266116
result:
ok answer is '28263577418567266116'
Test #53:
score: 0
Accepted
time: 241ms
memory: 3404kb
input:
16 7640070982466466
output:
275752565647555878
result:
ok answer is '275752565647555878'
Test #54:
score: 0
Accepted
time: 230ms
memory: 3476kb
input:
15 441869026556015312
output:
16212131234378684940
result:
ok answer is '16212131234378684940'
Test #55:
score: 0
Accepted
time: 192ms
memory: 3412kb
input:
14 876097982129564158
output:
30138111462733879719
result:
ok answer is '30138111462733879719'
Test #56:
score: 0
Accepted
time: 287ms
memory: 3436kb
input:
18 543698978852856099
output:
31531851816668641477
result:
ok answer is '31531851816668641477'
Test #57:
score: 0
Accepted
time: 265ms
memory: 3392kb
input:
17 977927934426404945
output:
50224732558555875933
result:
ok answer is '50224732558555875933'
Test #58:
score: 0
Accepted
time: 257ms
memory: 3476kb
input:
16 413156889999953790
output:
17247527871564162333
result:
ok answer is '17247527871564162333'
Test #59:
score: 0
Accepted
time: 219ms
memory: 3472kb
input:
15 847385845573502637
output:
32858466436756182939
result:
ok answer is '32858466436756182939'
Test #60:
score: 0
Accepted
time: 121ms
memory: 3520kb
input:
10 282614801147051482
output:
5234025743251842898
result:
ok answer is '5234025743251842898'
Test #61:
score: 0
Accepted
time: 217ms
memory: 3540kb
input:
15 973760833528793663
output:
37522313475261748199
result:
ok answer is '37522313475261748199'
Test #62:
score: 0
Accepted
time: 138ms
memory: 3520kb
input:
10 408989789102342508
output:
7507683644212199226
result:
ok answer is '7507683644212199226'
Test #63:
score: 0
Accepted
time: 292ms
memory: 3400kb
input:
18 843218748970858650
output:
48517453136216784320
result:
ok answer is '48517453136216784320'
Test #64:
score: 0
Accepted
time: 282ms
memory: 3460kb
input:
17 278447704544407496
output:
13445647446417261863
result:
ok answer is '13445647446417261863'
Test #65:
score: 0
Accepted
time: 265ms
memory: 3412kb
input:
16 712676664412923638
output:
31626684778484371838
result:
ok answer is '31626684778484371838'
Test #66:
score: 0
Accepted
time: 125ms
memory: 3408kb
input:
11 147905615691505187
output:
3115037238176298995
result:
ok answer is '3115037238176298995'
Test #67:
score: 0
Accepted
time: 201ms
memory: 3392kb
input:
14 814506608119829833
output:
27141557811571426774
result:
ok answer is '27141557811571426774'
Test #68:
score: 0
Accepted
time: 285ms
memory: 3460kb
input:
18 249735567988345974
output:
13745718855311428535
result:
ok answer is '13745718855311428535'
Test #69:
score: 0
Accepted
time: 276ms
memory: 3436kb
input:
17 683964523561894820
output:
34462588212244874220
result:
ok answer is '34462588212244874220'
Test #70:
score: 0
Accepted
time: 188ms
memory: 3408kb
input:
12 119193479135443666
output:
2777183132661531726
result:
ok answer is '2777183132661531726'
Test #71:
score: 0
Accepted
time: 289ms
memory: 3416kb
input:
18 577967474662410047
output:
33372657423746582198
result:
ok answer is '33372657423746582198'