QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#735141#5312. Levenshtein Distancetx344AC ✓3654ms6496kbC++142.2kb2024-11-11 17:44:392024-11-11 17:44:40

Judging History

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

  • [2024-11-11 17:44:40]
  • 评测
  • 测评结果:AC
  • 用时:3654ms
  • 内存:6496kb
  • [2024-11-11 17:44:39]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define Ull unsigned ll
#define Int __int128
#define ld double
#define fi first
#define se second
#define PII pair<int,int>
#define PLI pair<ll,int>
#define PLL pair<ll,ll>
using namespace std;
const int N=1e5+5,M=35,Base=71;
int n,m,k,f[M][M*2],ans[M];
Ull ha[N],hb[N],pw[N];
char a[N],b[N];
inline void Max(int &x,int y){x=x<y?y:x;}
int ID(char x){return x>='a'&&x<='z'?x-'a':x>='A'&&x<='Z'?x-'A'+26:x-'0'+52;}
void Init()
{
    pw[0]=1;
    for(int i=1;i<N;i++)pw[i]=pw[i-1]*Base;
    for(int i=1;i<=n;i++)ha[i]=ha[i-1]*Base+ID(a[i]);
    for(int i=1;i<=m;i++)hb[i]=hb[i-1]*Base+ID(b[i]);
}
inline Ull Get1(int x,int y){return ha[y]-ha[x-1]*pw[y-x+1];}
inline Ull Get2(int x,int y){return hb[y]-hb[x-1]*pw[y-x+1];}
int LCP(int x,int y)
{
    int l=1,r=min(n-x,m-y)+1;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(Get1(x,x+mid-1)==Get2(y,y+mid-1))l=mid+1;
        else r=mid-1;
    }
    return r;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
    #endif

    scanf("%d%s%s",&k,a+1,b+1),n=strlen(a+1),m=strlen(b+1);
    Init();
    // printf("LCP : %d\n",LCP(2,5));
    for(int i=1;i<=m;i++)
    {
        memset(f,-63,sizeof(f));
        f[0][M]=0;
        for(int x=0;x<k;x++)
        {
            for(int y=M-x;y<=M+x;y++)if(f[x][y]>=0)
            {
                f[x][y]+=LCP(f[x][y]+1,i-1+f[x][y]+y-M+1);
                Max(f[x+1][y],f[x][y]);
                Max(f[x+1][y-1],f[x][y]);
                Max(f[x+1][y+1],f[x][y]);
                if(f[x][y]<n&&i-1+f[x][y]+y-M<m)Max(f[x+1][y],f[x][y]+1);
                if(f[x][y]<n)Max(f[x+1][y-1],f[x][y]+1);
                if(i-1+f[x][y]+y-M<m)Max(f[x+1][y+1],f[x][y]);
            }
        }
        for(int x=0;x<=k;x++)for(int y=M-x;y<=M+x;y++)if(f[x][y]>=0)
        {
            if(x==k)f[x][y]+=LCP(f[x][y]+1,i-1+f[x][y]+y-M+1);
            if(f[x][y]!=n||n+y-M<=0||i-1+n+y-M>m)continue;
            ++ans[x];
        }
    }
    for(int i=0,las=0;i<=k;i++)printf("%d\n",ans[i]-las),las=ans[i];

	fprintf(stderr,"%.15lf\n",(ld)clock()/CLOCKS_PER_SEC);
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 6252kb

input:

4
aaa
aabbaab

output:

0
5
15
7
1

result:

ok 5 number(s): "0 5 15 7 1"

Test #2:

score: 0
Accepted
time: 1885ms
memory: 5520kb

input:

30
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 31 numbers

Test #3:

score: 0
Accepted
time: 477ms
memory: 5640kb

input:

30
BBAAABAABBBA
ABBABBBBAABAAAABABBBAABAABBAABAAAAAABAABABBAAAABAAAAABABAABAABBABBAAAABBBBAABBABAAABAABAABBBBBABBABABBBBABBBBAAABBABABBBBAAABBBBAAAABABABABABABABAAABBBBBAABAABAABBAABBBAABBBBBBBABAABAABAABABAABAAABAABBBAABABBABBAAABAAAABABABBABBBAAABBBAAAABBBBABABABAABAABBBBBBBBBAABBBABABBBABAABBABBA...

output:

17
662
8230
50302
166666
310121
345469
280387
227200
209178
203013
198561
105117
102147
99771
97730
96058
94730
93633
92720
92060
91525
91143
90831
90585
90419
90288
90200
90120
90068
90035

result:

ok 31 numbers

Test #4:

score: 0
Accepted
time: 1047ms
memory: 5576kb

input:

30
AAABBAAAAAAAAAAAAABAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAABAAAAABAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABABAAAABAAAABAAAABAAAAABAAAAAABAAAAAAAAABAAABAAABBAAAAAAAAAAAAAAAABAABAAABAAAAAAAAAAAAABAAAAAAAAAAAAAAAABAAABBAAAAAAAAAAAAAAAAAAAAAAAAAABAABAABABAAAAAAAAAAAAAAA...

output:

0
0
0
0
1
28
263
1410
6434
22523
56017
115080
189633
263874
316906
339254
332825
312943
286470
263283
246310
235032
227182
221294
216978
213734
211178
208848
206945
205393
204279

result:

ok 31 numbers

Test #5:

score: 0
Accepted
time: 510ms
memory: 6136kb

input:

30
ABABAABAAABAAAA
AABBABABBBBBAAABABAABBAAABBBAABABBBABABABABABBABBBAAAAABBAAABBABABABABABBAAABBAAABAAABBBBBBBAABABBBAAAAABAABBBABBABBBABBBABABAABABBBAAABBABBAAABBBBBBBAABAABABAAAAAABBAABAAABBBAABBAABBAABBABABAAAAAAAABBBBBAAABABABBABAAAAABAABAABAABAABAAABABBABBBABAAABBBABABAABAABBBAABABBAABBAAAABAB...

output:

2
125
1938
15793
70756
178090
282937
325020
310617
277899
244094
217672
206966
202456
198644
105535
102767
100355
98411
96655
95310
94124
93217
92487
91872
91414
91039
90741
90555
90397
90276

result:

ok 31 numbers

Test #6:

score: 0
Accepted
time: 1106ms
memory: 5564kb

input:

30
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

0
0
0
0
1
91
1082
14598
58877
123681
212928
258264
253856
277926
265254
243456
217809
198008
190004
184665
184470
183593
183524
183406
183335
183255
183185
183142
183078
182991
182922

result:

ok 31 numbers

Test #7:

score: 0
Accepted
time: 587ms
memory: 5616kb

input:

30
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAABABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

1
460
44032
126686
201431
222795
213509
199190
187254
184699
184159
183907
183818
183558
183500
183466
183412
183393
183343
183299
183275
183236
183163
183127
183105
183056
183010
182971
182910
182719
182437

result:

ok 31 numbers

Test #8:

score: 0
Accepted
time: 588ms
memory: 5520kb

input:

30
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

29
25121
100687
175758
199099
210112
187931
180903
178707
178497
178494
178497
178495
178496
178492
178492
178492
178491
178490
178491
178490
178490
178492
178489
178489
178488
178487
178487
178487
178488
178487

result:

ok 31 numbers

Test #9:

score: 0
Accepted
time: 616ms
memory: 6260kb

input:

30
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

17
12879
77552
170649
187824
198210
200962
189247
181730
180843
178608
178607
178607
178605
178599
178599
178599
178596
178595
178592
178594
178595
178593
178594
178593
178595
178593
178593
178594
178593
178591

result:

ok 31 numbers

Test #10:

score: 0
Accepted
time: 1105ms
memory: 6176kb

input:

30
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

0
0
0
0
73
320
52858
125690
177498
270124
217932
192611
177148
228465
180709
166240
162360
162360
162359
162359
162359
162359
162358
162358
162359
162357
162357
162357
162357
162358
162358

result:

ok 31 numbers

Test #11:

score: 0
Accepted
time: 681ms
memory: 5612kb

input:

30
ABBABABABAAABAAAAAAABAAABBAAAA
BABBABBBAAABBAAAAABBBBBAAAABAAAAAABBAABAAAABAAABAAAAAAAABAAABAABAABAABBBAAAABAAAABABBABBAAABABAAAAAAAABAABBAAAAAABABAAAAABABAAAAAAABAAAAAAAABAAABBBAAAAABAABAABAAAAABAAAAAAAAAAAABABAAAABABAAAABAABBAAAAABBAAABABBBBBBAABABAAAAABABBBAABABBAAAABAAAAABABABBAAAAAAAABABBBAB...

output:

0
0
1
38
617
4567
22647
76780
180046
296249
362349
361655
325883
289074
263906
246552
233312
221488
212319
205320
200921
198057
196229
194923
193749
192649
191581
190728
189773
188925
98116

result:

ok 31 numbers

Test #12:

score: 0
Accepted
time: 472ms
memory: 6140kb

input:

30
Y3YYY
wwwwwwwYYwwwww3ww3w33Yww3wYY3w3w33w3Y3YY33wYwY33wwYwY33Y3w3wwwY333ww333Ywww3w3Y33wwYw3YYwY3Y3w33YwwwwwYYYw3YYYYYYww3w3333Yw3Y3wY3wYw3w3w3Y3w33YY33YwwY3Y3wY33w3333Yw333wYYw3Yw33w3YwYYYYYwwwwY3wwYYYYY33Y3YwYY3Yw3www3Ywww333w3YYY333YY3Y3333Y3Y33ww33333wwYY3YYYww3YYYYYYwwYYYwwYY33Y33wYY3w3wY3w3...

output:

412
9896
68598
212288
338054
201716
131998
125202
120710
117075
114099
111708
109603
107820
106320
105086
104074
103198
102592
102094
101640
101290
101006
100767
100571
100430
100305
100226
100158
100109
100074

result:

ok 31 numbers

Test #13:

score: 0
Accepted
time: 1649ms
memory: 5684kb

input:

30
BnAnnBB3fn33BffBBn3nfAABnBnfBfffBfBAf3Ann3nnfAnAAA
3Bn33ABnBnn3ffnfnnn3fB3Af33fBf3fnnBnBAAffBB33BnB3A3nBAnnABnf33AAAB3nnBA33nf33n3nBfnfnfABB3nBAA3ABAnAAB33A33ABfnAnA33f3fBBnBBfBnB3f3BBf3AAfBAAB3A3BnffBnf33nnffA33fAnffnBBB3nnBBfnBB33BffABn3n3BnAffBBA3nnnAfBfBnn3nn3fn3fn3B3AB3fBn3ABf3BAfAnAB3AAABB3...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
71
377
1675
6225
20231
54946
129079
258834
431560

result:

ok 31 numbers

Test #14:

score: 0
Accepted
time: 3418ms
memory: 6448kb

input:

30
BlXI1hCXN7XMD3h6ZFl8BFVBTgyh3R8oo74unTVVFKwjZCUjTzGqap3FSDU7KxycOFmh1au29Me8OEuSkS4Hd7DAzMVznUbBNuf3pqpud9t2B8F2M1OYziAPbmNynplDCtD3gbIkwSWV6H7Z2Uw4X12pPkFHM5Aisr4uVqggN2hdZGEhEVXNTbHSJ2teCsrO8pRUzKOnYDXIJ3hpkgELyRc7bn8UgQ2Rnhf4r2QA9kQqSSjqrCjGmzicFB9KjqOS2hq75WZRb1ZoI9cPyeOsYE6K9egR12hYCazoIQH8O...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 31 numbers

Test #15:

score: 0
Accepted
time: 3575ms
memory: 6144kb

input:

30
TmQyTaLuQVLUJdDWghdXyiWItuIYQ9GAw6TL0cyEvfBjrxXx2uBsynB5BCYxn6O6FPu9jzFj4wNA6YUaczxKT6yutPwAYo97NT7ygBXxLOnRn7aCwR6NN6m2Pj9J6bzZg3RUFU4MKomMuEYLo5jhB8P3RLp7SBmaCrzU8gumSb4W29YcIp4fHHzuGM4pfk0UFJoMHAsVSlvREO33TL24tgzFGJeZimMuZ1UKyVH6uk5kwCOcRu1N0FqRr33gTcFrNZO6CeUdDvlhhhJK5zJ9W4BUDtM9YUz2Xg2sWMs21...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 31 numbers

Test #16:

score: 0
Accepted
time: 3651ms
memory: 6236kb

input:

30
C0HKyslC6jquIZTK1eOiuyIv0wzje05Gvt8lvE2HauhsL8HYfTZ1dqKytoLKwWzryEsHBX3c5RGQ2KufkALf1DCHTafpG2drqjgLEwjwCpDyjRXRlskNCUkSOMONoB0yKiKCLcnNlWiZSlWlEcAiP62PvWjhAG2py5prF69coe4N7jANXk7hCvlIvYy5of0RT0eDhmXfSrnCk4C6lZ387hP7srzdqpjr2siBLXDmoehj6dyKwQmDZNuKUojOiUhqARlTIyiS7SvFUg5MZZ8HSk5s413XnEy489HKtqRLH...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 31 numbers

Test #17:

score: 0
Accepted
time: 3420ms
memory: 5892kb

input:

30
54n5bJBnw3pL2ufWznguJip98eTm3TZwBYnqD27KtOY99HpCbVWlN5WgUyYIvgLAY30XUeFbrG9MBqn39pigY0IoXz2E05YqDp7kCjj6RvO62ZmRxE8wXq0MZaHwiE2OdKPQuK4VVU4H4k4YPw1jOSsSoMfGd87a7ZDgd3bjXAXcz5GDVzapW8FmDzoqp5SCwZDO9ufWAJlSInx0VhYYTxuS3PyBsd9hLkXK2psGN59m1UcKOHWWMgGtBC5HMOkuo0Y1ipMvczy7KCBJZ08Mi6FT4TC1ghWdkWP4XLLtz...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 31 numbers

Test #18:

score: 0
Accepted
time: 3565ms
memory: 6076kb

input:

30
vt0ZfveKIwQqxHhk49gHI5EEK5y9Tsp9f0Cx1IKHwwvsrrTlE9xR2f2agCjhUAap8sHAR5zeQkQoAFQs3MqH1M2CYK0leBkVwIVP5Qt8vUNj8DEkR0TuuitiajMuKiAhDyd9CLkakRilkPL6nzDTwRaBF54S5rw3QXFDDTDDQceOH9YXA1JaFWS7zuggRx4E8dEAR4bcoRdHsizCzxDNawonNbjOKvxXYkIHcyBaPInsroxYkJTMn95k2CO6eT4MEioRWuz0Bhzab3UwHzzT0pH50zrUJeNHpUsN0RUqK...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 31 numbers

Test #19:

score: 0
Accepted
time: 469ms
memory: 6060kb

input:

30
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...

output:

50001
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002

result:

ok 31 numbers

Test #20:

score: 0
Accepted
time: 693ms
memory: 5732kb

input:

30
GwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwGwG...

output:

2940
16575
47788
100929
178911
239421
260209
247737
229004
217495
206635
201055
195458
194778
194093
194093
194093
194093
194093
194093
194093
194093
194093
194093
194093
194093
194093
194093
194093
194093
194093

result:

ok 31 numbers

Test #21:

score: 0
Accepted
time: 471ms
memory: 6084kb

input:

30
hxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhxh...

output:

25001
100002
125002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002
100002

result:

ok 31 numbers

Test #22:

score: 0
Accepted
time: 462ms
memory: 6496kb

input:

30
zZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZzZz...

output:

5001
20002
25002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002
20002

result:

ok 31 numbers

Test #23:

score: 0
Accepted
time: 3654ms
memory: 6036kb

input:

30
wsMcrQ1i7cQbRu6ChwsMcrQ1i7cQbRu6ChwsMcrQ1i7cQbRu6ChwsMcrQ1i7cQbRu6ChwsMcrQ1i7cQbRu6ChwsMcrQ1i7cQbRu6ChwsMcrQ1i7cQbRu6ChwsMcrQ1i7cQbRu6ChwsMcrQ1i7cQbRu6ChwsMcrQ1i7cQbRu6ChwsMcrQ1i7cQbRu6ChwsMcrQ1i7cQbRu6ChwsMcrQ1i7cQbRu6ChwsMcrQ1i7cQbRu6ChwsMcrQ1i7cQbRu6ChwsMcrQ1i7cQbRu6ChwsMcrQ1i7cQbRu6ChwsMcrQ1i...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 31 numbers

Test #24:

score: 0
Accepted
time: 2410ms
memory: 6300kb

input:

30
v90JRqutBRmdP95O4v90JRqutBRmdP95O4v90JRqutBRmdP95O4v90JRqutBRmdP95O4v90JRqutBRmdP95O4v90JRqutBRmdP95O4v90JRqutBRmdP95O4v90JRqutBRmdP95O4v90JRqutBRmdP95O4v90JRqutBRmdP95O4v90JRqutBRmdP95O4v90JRqutBRmdP95O4v90JRqutBRmdP95O4v90JRqutBRmdP95O4v90JRqutBRmdP95O4v90JRqutBRmdP95O4v90JRqutBRmdP95O4v90JRqut...

output:

0
0
0
0
0
0
0
0
0
0
0
15
369
2181
6876
14558
24304
35430
47155
58923
70691
82458
94223
105990
117757
129522
141290
153091
165211
172759
165243

result:

ok 31 numbers

Test #25:

score: 0
Accepted
time: 3503ms
memory: 6148kb

input:

30
fhF5OawojWdaTvjuFbUBzlfX4ziBAMXEfGxnX1OevUW0P3ejLvl4k5gBn2KUFGR9eEvQS07HDHKvpWCi5T76rIgFH3ljytFBmM7SFLYxltxxTIjuBe92uQhFdS5X2LEobPAbntdm5qmuvdVeXY91fiMiO1j7EdGSrGrF2ek4PIpLYWorlwAhIcECg3pU84bi8cGFfytKqJbuas1bdOsM6oihwXjatbvq5DejPperOfhF5OawojWdaTvjuFbUBzlfX4ziBAMXEfGxnX1OevUW0P3ejLvl4k5gBn2KUFGR9...

output:

0
0
0
0
0
0
0
0
0
3
39
196
567
1153
1887
2706
3559
4417
5275
6134
6993
7851
8709
9567
10425
11283
12141
12999
13857
14716
15575

result:

ok 31 numbers

Test #26:

score: 0
Accepted
time: 3576ms
memory: 6132kb

input:

30
tsPnmYDfhxDbjUKfusmeKiDBffDMABWuxIiSnBiiUIVpc63CejvexMduUz9jCysafNa8R66l3Sg2Xe8p2mLluTxTbha1PhbxEGdMQ8QxnFzTkL4fZmUHKmieWga1kfeIC8cFCodOp260R7nqEwMVm95jdFHdxZEBtkmduZPOawvNxMpWwyJbOcX6c7hSYE2by9uV3LLFEcMdCGnMrLuorC7K4I9ZZW9l8sbJ18droy5Eql2B61G3nUzGuZLnxlaC6sFYg9sYruCvvM5sRNTej9uE81HfWw8j6KScvLrY8...

output:

0
0
0
0
0
0
0
0
1
8
31
74
132
203
285
371
457
543
629
715
801
887
973
1060
1147
1233
1319
1405
1491
1577
1663

result:

ok 31 numbers

Test #27:

score: 0
Accepted
time: 3566ms
memory: 6080kb

input:

30
4InvyDh20sJz28bC4tnk8up7fI7vlidMq7iDyWHZbyYts7cdEeKCOrIQTfSJj3K1RjejCTLALpPc5bXtnAVPwoomrpNpgUTUTmZ5P6F7sW9cUZuAfSVwxGVCuvycuenCg8z8BfzakvsTJVZswPxoATGR5aCi6jxSCCyxxBaD7OKrjqeOXybJn7OcGuAq41v1SVtTJWwTejfA31nj6G7JgasPsMXaioj3lyWOhamJ25gPzukGxOTYfAFIdAugkQSv8Hp1GLZRX9oUQwWXHLwL1mciFdcrcZg7xIU1tlxd3...

output:

0
0
0
0
0
0
0
0
0
1
4
8
12
18
27
37
47
57
67
77
87
97
107
117
127
137
147
157
167
177
187

result:

ok 31 numbers

Test #28:

score: 0
Accepted
time: 3565ms
memory: 6056kb

input:

30
bBovIcBRGxHntM3x06HeMJGa0yipLIC1oszgQEnV5wJRcO6yt5vIWa8H0ndAejTjga3b2Ku0xeV2XZIfmVJ2hlk3saZZhwTCQA3Vbllh9UKKzv5Ofk6yj2tsfoGJ6RYFRgYmUyLad4IQCNtKpXCZ3faixtClaTW9Rixp9yYuyyNn9rFDmshKD68Wd7z0Z6cxEBJHrfFbjI05uC5k8zIcKMTUNK5ELF7vDUcoKkBnZa82ygsXzi345gyZqZggOw2gSHV3jKKgQf5K4OEZS4YUnh1EiOcRV5CyJYVzkMcLs...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
2
7
13
19
25
31
37
43
49
55
61
67
73
79
85
91
97
103

result:

ok 31 numbers

Test #29:

score: 0
Accepted
time: 3563ms
memory: 6120kb

input:

30
cBuTSYusjkQuRKSKZAjHwhTZOwsk7ue5WFiaT5TE9LT7nymtLKho8XlaXzWxDbCB7PTQpmxKTkppaIT7duA5zOx4GCqwQ6LckJLlzXUwN09qzUAabZkWpKMCAXBBJ3Nozp5HcZlSV2Q7gHjz5OksFvdb4PduC5Nk7cRWrJ7R2MxV52oS2eyPxsFoFP2wU4WE4ETKIs8lygGR5qHhfE97PIIDIsEBIn1Sj66QX1jva9FMkfuO1fj2Wk0puCY6tzlc1P9bbtr5UZG3SGAVtEs6kFp1guRwEEPlFGZdOkYx2...

output:

0
0
0
0
0
0
0
0
0
1
3
5
7
9
11
13
16
20
24
28
32
36
40
44
48
52
56
60
64
68
72

result:

ok 31 numbers

Test #30:

score: 0
Accepted
time: 1804ms
memory: 6252kb

input:

30
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...

output:

0
0
0
0
0
0
0
0
0
35285
27946
65059
86462
83569
52630
85019
51203
63998
112260
203934
247341
211464
120981
100002
100002
100002
100002
100002
100002
100002
100002

result:

ok 31 numbers

Test #31:

score: 0
Accepted
time: 1949ms
memory: 6080kb

input:

30
HKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKH...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
2783
19369
48486
69067
94730
130377
151683
153835
149942
149939
149936
149933
149930
149927
147197
144472
138997
133520

result:

ok 31 numbers

Test #32:

score: 0
Accepted
time: 1831ms
memory: 6144kb

input:

30
nXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXsnXs...

output:

0
0
0
0
0
0
0
0
0
0
0
2420
14660
44087
78325
98303
113677
129371
129951
126939
125227
126030
123924
126028
123921
126026
123918
126024
123915
126022
123912

result:

ok 31 numbers

Test #33:

score: 0
Accepted
time: 2124ms
memory: 6160kb

input:

30
K8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK8bdK...

output:

0
0
0
0
0
0
0
0
0
0
2106
10007
23837
43350
56473
63980
81186
103713
115013
121530
120866
116941
121169
118189
115201
117923
116830
115198
117920
116830
115193

result:

ok 31 numbers

Test #34:

score: 0
Accepted
time: 2284ms
memory: 6140kb

input:

30
aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aWJe6aW...

output:

0
0
0
0
0
0
0
0
0
1091
5317
14334
28961
49835
67902
81744
89579
96790
102587
112733
120993
125784
123682
119537
114598
114972
112952
112702
111928
113216
112116

result:

ok 31 numbers