QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#773375#2835. Number TheoryereothAC ✓924ms97600kbC++142.5kb2024-11-23 08:36:382024-11-23 08:36:38

Judging History

你现在查看的是最新测评结果

  • [2024-11-23 08:36:38]
  • 评测
  • 测评结果:AC
  • 用时:924ms
  • 内存:97600kb
  • [2024-11-23 08:36:38]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define int long long

using namespace std;

const int kmax = 5005;
const int kmaxM = 2e6 + 3;

long long g[6][kmaxM];
long long m, a[kmax], f[2][kmax][2];
long long res = 1e18;
long long pw[11];
long long o[6] = {0, 1, 11, 111, 1111, 11111};
string str;
long long lst, n;

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  for(int i = 0; i < 6; i++) {
    for(int j = 0; j < kmaxM; j++) {
      g[i][j] = 1e18;
    }
  }
  g[0][1000000] = 0;
  pw[0] = 1;
  for(int i = 1; i <= 10; i++) pw[i] = pw[i - 1] * 10;
  for(int i = 1; i < 6; i++) {
    for(int j = -1000000; j <= 1000000; j++) {
      if(g[i - 1][j + 1000000] != 1e18) {
        for(int k = -10; k <= 10; k++) {
          int v = j + k * o[i];
          if(-1000000 <= v && v <= 1000000) {
            g[i][v + 1000000] = min(g[i][v + 1000000], g[i - 1][j + 1000000] + i * abs(k));
          }
        }
      }
    }
  }
  while(cin >> str) {
    m = str.size() - 1;
    a[m + 1] = a[m + 2] = lst = n = 0;
    for(int i = 0; i <= m; i++) a[i] = str[m - i] - '0';
    for(int i = 0; i <= m; i++) {
      long long x = a[i] * 9 + lst;
      a[i] = x % 10, lst = x / 10;
      if(lst) m = max(m, i + 1);
    }
    if(m < 5) {
      long long n = 0;
      for(int i = 0; i <= m; i++) n += a[i] * pw[i];
      cout << g[5][n / 9 + 1000000] << '\n';
    } else {
      for(int i = 0; i < 2; i++) for(int j = 0; j <= m + 1; j++) for(int k = 0; k < 2; k++) f[i][j][k] = 1e18;
      f[(m + 1) & 1][0][0] = 0, f[(m + 1) & 1][0][1] = m + 1;
      for(int i = m; i >= 6; i--) {
        for(int j = 0; j <= m + 1; j++) {
          for(int k = 0; k < 2; k++) {
            f[i & 1][j][k] = 1e18;
          }
        }
        for(int j = 0; j <= m + 1; j++) {
          for(int k = 0; k < 2; k++) {
            if(f[(i & 1) ^ 1][j][k] == 1e18) continue;
            f[i & 1][j + k][0] = min(f[i & 1][j + k][0], f[(i & 1) ^ 1][j][k] + 1ll * i * abs(a[i] - 10ll * k));
            f[i & 1][j + k][1] = min(f[i & 1][j + k][1], f[(i & 1) ^ 1][j][k] + 1ll * i * abs(a[i] - 10ll * k + 1));
          }
        }
      }
      for(int i = 0; i < 6; i++) n += a[i] * pw[i];
      for(int i = 6; i <= m; i++) n += a[i];
      res = 1e18;
      for(int i = 0; i <= m + 1; i++) {
        for(int j = 0; j < 2; j++) {
          res = min(res, f[0][i][j] + g[5][(n - j * 999999 - i * 9) / 9 + 1000000]);
        }
      }
      cout << res << '\n';
    }
  }
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 7ms
memory: 97392kb

input:

12
100
998244353

output:

3
5
76

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 10ms
memory: 97396kb

input:

4296
5370
8014
9532
6311
4070
2541
4782
5630
1487
2916
454
2020
5650
1851
5885
3556
6533
5044
1780
5746
5605
7860
4416
4495
8081
2416
3534
6045
3348
4536
8725
3505
1074
1531
937
7954
4451
7052
9586
3468
2679
6085
9908
3630
8046
6282
2883
9021
1436
5201
8166
8986
2167
7780
4156
101
3753
5732
5173
118...

output:

29
36
28
27
35
36
22
30
32
22
33
15
20
30
28
32
19
29
40
22
34
34
30
26
30
35
24
23
42
18
26
28
31
14
22
22
33
22
43
30
21
24
42
19
30
33
43
30
21
18
34
36
21
18
19
34
6
30
35
42
14
27
36
32
23
25
30
35
28
22
32
27
41
39
26
37
30
28
39
35
22
24
32
44
35
36
35
42
22
22
31
35
25
32
32
15
17
33
38
31
2...

result:

ok 9999 lines

Test #3:

score: 0
Accepted
time: 10ms
memory: 97416kb

input:

16528
11452
14198
11877
11309
14176
10807
19189
12063
11011
11618
18292
19862
13144
16834
16652
14120
17091
19836
16498
17655
19144
14088
13370
12709
17115
14482
10958
12306
17891
17979
10705
10036
17976
12035
18042
17495
14498
10163
15926
12209
18908
13033
19875
11699
14361
14785
14253
12647
14726
...

output:

37
19
29
21
17
33
24
37
24
10
32
47
30
25
40
30
30
44
33
40
32
34
31
23
30
42
28
18
21
31
37
28
18
38
23
42
48
28
25
41
13
29
28
26
26
30
31
31
28
38
26
20
30
36
43
31
40
40
38
31
27
26
28
35
33
39
19
24
36
36
20
20
27
32
43
23
20
28
29
40
31
35
25
20
31
32
40
41
40
41
33
39
39
42
37
12
21
10
30
39
...

result:

ok 10000 lines

Test #4:

score: 0
Accepted
time: 17ms
memory: 97328kb

input:

25172
29204
28892
23128
21312
28850
23340
27350
21632
29705
29655
24700
27992
23570
28822
21683
26260
26497
28092
22514
28528
23098
26446
27220
22261
28727
28177
23884
28830
24460
26841
29986
23893
28374
24608
22374
22731
26925
22753
24241
20202
24668
23072
21788
27823
23938
23414
22339
20247
20546
...

output:

45
48
34
28
25
43
20
50
33
47
39
31
42
26
42
32
49
42
47
30
50
24
34
42
22
48
50
33
45
25
43
32
34
55
33
24
35
42
31
31
30
26
32
25
40
43
26
19
31
32
36
42
50
35
51
36
39
22
27
34
47
48
42
40
46
31
37
43
29
37
49
48
33
26
13
40
46
43
34
40
38
47
35
30
24
26
33
49
27
46
29
28
46
33
34
37
53
42
42
42
...

result:

ok 10000 lines

Test #5:

score: 0
Accepted
time: 15ms
memory: 97376kb

input:

35458
30814
33590
33177
30718
35952
39315
37797
38544
32595
34013
36806
38978
37445
32117
35080
36177
36811
38996
33557
35833
36013
31989
33626
30095
30732
32497
32972
39513
35802
38572
36304
37335
39638
30390
30443
30181
37677
30341
33589
34504
37365
38395
38755
32061
37743
36823
34880
31171
38806
...

output:

31
41
29
27
47
46
55
37
46
40
35
40
43
41
28
43
48
37
41
23
40
40
27
36
37
42
37
34
57
36
52
46
45
55
48
40
44
36
41
28
34
50
60
42
36
38
40
36
38
48
32
46
37
49
33
35
48
34
41
41
32
37
49
29
32
40
53
48
42
26
30
40
35
37
30
43
56
32
37
32
32
24
33
39
48
37
39
35
46
52
53
57
35
24
33
40
34
45
53
33
...

result:

ok 10000 lines

Test #6:

score: 0
Accepted
time: 15ms
memory: 97392kb

input:

47583
45587
40557
41413
48126
43227
41361
49755
42400
48511
46835
42685
42425
44853
41732
45421
44157
41929
47256
42185
49905
47237
45004
40732
41670
44069
40082
42147
49510
40690
45655
41481
48052
40609
43269
48612
46900
46706
40691
48979
49898
46602
43411
47434
42544
40816
49880
40217
45017
47779
...

output:

48
31
48
49
48
32
48
50
42
53
44
47
41
40
50
32
39
49
51
38
51
50
40
51
46
39
49
40
61
49
29
51
50
57
38
53
37
40
50
45
46
42
33
44
39
52
48
47
43
34
45
32
42
43
38
41
44
53
31
48
51
45
41
55
29
41
42
36
42
47
38
54
37
35
40
34
45
45
35
42
41
42
33
37
44
56
41
54
29
50
37
51
47
50
39
47
40
39
55
40
...

result:

ok 10000 lines

Test #7:

score: 0
Accepted
time: 12ms
memory: 97392kb

input:

55562
56846
58105
54937
52692
50178
54319
54915
50557
52656
56355
57363
54038
52812
53176
59197
57326
59159
59531
57845
56859
57711
55867
50764
56134
52439
55360
52162
57155
52264
53214
59034
55078
59088
57901
56623
55475
56947
56875
59270
57531
56644
55171
54900
53866
59246
55120
50452
57034
58555
...

output:

31
45
47
54
57
55
37
50
57
52
42
54
52
55
46
52
51
56
59
45
45
45
39
55
46
48
40
52
50
47
41
48
43
47
40
38
36
49
39
59
45
33
48
44
49
53
41
56
46
46
46
53
49
44
46
45
40
45
62
40
55
56
50
45
40
47
44
52
49
59
49
50
53
41
32
43
54
47
50
44
44
43
49
40
52
55
42
31
41
55
49
42
54
41
58
45
53
46
50
51
...

result:

ok 10000 lines

Test #8:

score: 0
Accepted
time: 8ms
memory: 97336kb

input:

68733
60810
67393
64496
65059
60979
63486
67951
63442
63390
62976
67541
63288
61770
63615
62708
63675
64462
60143
67574
65757
62877
69434
60667
68109
65801
61749
60594
62448
61977
60014
69238
63419
63440
60449
64529
65693
65650
69566
62932
64440
64388
62977
67095
69177
65421
67034
63159
67234
64999
...

output:

46
60
52
48
54
53
52
49
44
49
54
42
48
58
58
65
52
42
50
44
41
54
52
58
41
41
63
68
51
54
47
50
49
46
59
46
41
41
53
60
39
46
53
45
52
39
42
55
44
47
47
44
51
54
40
61
41
48
41
52
49
50
42
41
35
54
49
42
48
54
56
42
63
43
50
41
51
58
57
57
43
41
54
59
63
66
56
45
43
63
65
41
43
38
57
54
47
43
46
51
...

result:

ok 10000 lines

Test #9:

score: 0
Accepted
time: 15ms
memory: 97376kb

input:

70451
77409
73192
73579
75086
78154
78238
75957
78550
75617
78564
73870
74725
70590
73332
74045
70687
76389
79692
74760
73538
74386
77646
76853
75878
79897
76404
71876
76587
73889
76008
73574
77829
72673
76321
74783
75211
70235
70292
74476
74216
71549
78231
77353
79686
71120
71752
78548
77730
70493
...

output:

56
39
48
48
49
39
40
50
40
45
39
54
52
61
39
53
60
42
45
50
51
47
29
40
40
37
42
55
36
49
46
51
35
59
38
47
41
48
58
41
45
60
37
40
45
46
62
39
33
63
48
30
53
47
42
44
44
49
47
48
41
57
50
40
63
45
48
44
47
54
51
51
48
43
59
49
33
42
46
39
53
42
32
38
44
43
64
50
56
46
56
41
46
33
48
34
57
42
58
53
...

result:

ok 10000 lines

Test #10:

score: 0
Accepted
time: 11ms
memory: 97456kb

input:

86492
82042
82395
85456
82379
83405
84464
80074
82438
88208
81516
82815
87181
88276
81288
89085
80748
82539
84837
88160
85818
83695
89219
89825
81747
88241
84428
87307
83517
81371
80557
89236
80342
83252
82503
89808
86584
82599
80539
86491
84521
81155
86352
80720
86012
87141
86667
83075
80697
80963
...

output:

41
53
56
33
50
51
39
42
49
37
57
60
45
43
48
30
51
53
55
42
46
55
28
37
57
39
40
41
54
50
46
30
42
49
57
35
37
54
51
40
43
41
41
55
43
45
24
52
54
46
32
42
44
34
46
36
43
53
44
27
42
47
45
52
41
39
61
57
35
25
52
43
38
50
41
54
37
47
26
44
35
30
39
28
49
42
49
26
51
28
53
35
45
43
37
44
52
53
54
32
...

result:

ok 10000 lines

Test #11:

score: 0
Accepted
time: 24ms
memory: 97420kb

input:

98444
95686
99650
91810
92829
90145
94267
90093
95597
92642
94279
97359
91044
99840
92439
97572
99845
92132
92676
96111
91222
97743
96688
99396
95545
95983
98381
98418
92309
92481
98112
92293
94426
90088
99648
92689
93574
96073
94906
98190
97349
91640
98879
92966
94198
94040
98573
98144
91707
93616
...

output:

28
37
28
47
56
30
45
31
38
46
44
38
35
27
39
32
22
36
43
39
27
27
28
39
29
47
41
36
37
44
29
43
38
28
27
45
45
50
51
38
37
47
18
48
44
55
32
34
50
54
30
30
51
41
45
32
47
32
41
19
49
46
42
30
27
54
37
37
33
43
29
36
48
35
52
47
28
28
29
30
38
46
45
34
35
45
41
45
41
51
45
38
40
51
23
27
35
34
54
51
...

result:

ok 10000 lines

Test #12:

score: 0
Accepted
time: 11ms
memory: 97544kb

input:

99647655441310714404533248973861508920
2073756854781
97786932
697203586561561
220
92603944
857
4913
37162832688008526170899875515887671731826673
1480102698509
402012655841707502050341636832
75136137088485508854715245558132922867818030309
4114635151757
770
75
82646730706547052
496224488355898625
2477...

output:

1421
213
59
356
8
122
17
35
2713
194
1267
2802
247
18
12
460
440
1402
13
243
108
2776
111
2054
119
3722
58
2381
785
2822
65
26
1443
1931
57
153
382
64
247
876
3088
78
1344
518
390
889
1323
215
690
2814
1352
1640
1775
1963
108
655
8
1539
1647
57
522
44
1798
1800
1369
22
583
11
585
138
1325
544
3044
1...

result:

ok 1000 lines

Test #13:

score: 0
Accepted
time: 27ms
memory: 97380kb

input:

126998323603155082976006666666666666666666666702
724300000000000000000000000000000000000000000023
568647043683731006786720864777777777777777777811
1019443265090537888888888888888888888888888888926
1037609645580130544702710000000000000000000000023
72503489262191057308222222222222222222222222252
86696...

output:

2098
701
2333
1495
1945
2255
2296
1148
2933
2384
1179
2802
3063
3073
1363
1110
2297
2701
1730
2251
2845
423
2008
2833
3117
3124
1454
2631
1237
2363
2260
2935
2772
1019
2343
2886
1973
1441
1544
875
2019
934
3019
1138
2865
3141
3366
376
2690
1684
1338
1641
2181
2235
201
1538
2496
1614
2503
2403
2777
1...

result:

ok 1000 lines

Test #14:

score: 0
Accepted
time: 25ms
memory: 97424kb

input:

59532290089430871062798612381094347142661940871177777777777777777777777777777777777777777777777848
19803770000000000000000000000000000000000000000000000000000000000000000000000000000000000000000012
100168466590022100356739170155928857723974996593165201135686100258266187972210428683157533333333382
80...

output:

8993
1795
10154
12075
5687
2262
2913
4041
9459
495
11524
8993
11753
13357
9143
8609
10247
9502
12290
11803
11668
10550
11055
11921
11276
6081
4409
6894
10690
8807
11232
8560
10954
5833
11646
6406
6470
4033
6713
487
5154
12653
6782
9253
10035
4673
9949
1073
11133
3509
791
11266
8978
9759
10425
10478
...

result:

ok 500 lines

Test #15:

score: 0
Accepted
time: 49ms
memory: 97352kb

input:

509087787306975183230863727273315566485734244653446194871812034352257204743513363579607563255287250873346461273339171084705119057585690396708334944336106309102141850499987705330404193756655153637104556966214174557044320510803165885320466813158011405886923133519056898001053
77281772454408400255174658...

output:

89942
53603
28963
175124
31865
6099
109664
15111
19266
175
150210
290455
249386
70611
132911
8897
82005
66071
115536
157604
80824
21558
55766
107086
83731
261497
47143
128063
275763
65490
48198
31999
43914
68692
102870
262589
75730
266619
198
22457
59673
205811
191020
180503
150195
198228
19465
2049...

result:

ok 100 lines

Test #16:

score: 0
Accepted
time: 104ms
memory: 97412kb

input:

537976124202599239286562342276420439613194571442768047599527420451111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

76329
130492
233795
318715
35926
205392
239365
250341
286535
218852
63863
186782
196183
248875
131708
286161
5977
30944
274943
106807
312427
2512
225546
308730
127370
272780
193954
273193
102195
287941
235307
306633
301413
234865
290306
252303
217927
210308
59334
304958
302257
289925
162230
79826
28...

result:

ok 100 lines

Test #17:

score: 0
Accepted
time: 197ms
memory: 97452kb

input:

989245628059044817746612863885482054090024574989147155076861099317572046427908692659059532290089430871062798612381094347142661940871177777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777...

output:

295796
734356
1248090
1227474
1222296
694768
1248924
803555
1114796
1173887
1213993
1178806
169021
914690
914149
178387
548986
1114089
1094591
1099017
1187151
1178788
774545
593806
660687
938445
809273
587001
771269
1129676
1036018
980572
678920
728738
1076989
1005858
1206241
1134874
946040
431661
9...

result:

ok 50 lines

Test #18:

score: 0
Accepted
time: 924ms
memory: 97600kb

input:

641847714851513327347323081332028131449897370428546626988117712284919008045806702519159655456244267417984504656414425298120573963938488765776323402029410084388553837824816914898279682108906697839161343986288686955497961980683045191452550017854156235782484534411134481308697868899390785687035874294324...

output:

30259734
30903118
31027297
31085277
30838673
30275861
30266951
30813594
30792935
30656894

result:

ok 10 lines

Test #19:

score: 0
Accepted
time: 910ms
memory: 97584kb

input:

410457317448274811284301998444876891280459713188523525491759164097602189759521289969587829710757809098041661906390001810465547988780240720850705403176138461661920035913654013077336212472627340934051027009725057610297247552407340231295449311009538244081818596239957964872484406735887888983335845467736...

output:

18430116
19761815
28794025
21668249
30473828
675872
28903739
6943570
26310926
29220266

result:

ok 10 lines

Test #20:

score: 0
Accepted
time: 108ms
memory: 97560kb

input:

999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...

output:

10002

result:

ok single line: '10002'