QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398507#5440. P-P-PalindromecaijianhongAC ✓72ms155060kbC++141.9kb2024-04-25 14:12:122024-04-25 14:12:13

Judging History

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

  • [2024-04-25 14:12:13]
  • 评测
  • 测评结果:AC
  • 用时:72ms
  • 内存:155060kb
  • [2024-04-25 14:12:12]
  • 提交

answer

// 
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
typedef long long LL;
template <int N>
struct palindam {
  unordered_map<int, int> ch[N + 10];
  int fail[N + 10], len[N + 10], dif[N + 10], tot, trans[N + 10];
  palindam() : tot(1) { fail[0] = 1, len[1] = -1; }
  int getfail(int p, const char* s, int rlen) {
    while (len[p] + 1 >= rlen || s[0] != s[-len[p] - 1]) p = fail[p];
    return p;
  }
  int expand(int p, int r, const char* s, int rlen) {
    p = getfail(p, s, rlen);
    if (ch[p][r]) return ch[p][r];
    int u = ++tot;
    len[u] = len[p] + 2;
    fail[u] = ch[getfail(fail[p], s, rlen)][r];
    dif[u] = len[u] - len[fail[u]];
    return ch[p][r] = u;
  }
};
int n;
palindam<1000010> M;
vector<int> g[1000010];
pair<int, int> stk[1000010];
int top, cnt[1000010];
void dfs(int u) {
  stk[++top] = make_pair(M.len[u], u);
  if (u > 1 && M.len[u] % M.dif[u] == 0) {
    auto [l, f] = *lower_bound(stk + 1, stk + top + 1, make_pair(M.dif[u], 0));
    debug("u = %d, len = %d, dif = %d, find f = %d, f.l = %d\n", u, M.len[u], M.dif[u], f, l);
    cnt[lower_bound(stk + 1, stk + top + 1, make_pair(M.dif[u], 0))->second] += 1;
  } else {
    cnt[u] += 1;
  }
  for (int v : g[u]) dfs(v);
  --top;
}
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);  
#endif
  cin >> n;
  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    for (int j = 0, lst = 1; j < (int)s.size(); j++)
      lst = M.expand(lst, s[j] - 'a', s.data() + j, j + 1);
  }
  for (int i = 0; i <= M.tot; i++) for (auto [r, v] : M.ch[i]) debug("%d %d %c\n", i, v, r + 'a');
  for (int i = 2; i <= M.tot; i++) g[M.fail[i]].push_back(i);
  dfs(0);
  LL ans = 0;
  for (int i = 2; i <= M.tot; i++) ans += 1ll * cnt[i] * cnt[i];
  cout << ans << endl;
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 12ms
memory: 86868kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

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

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

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

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

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

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1282

result:

ok 1 number(s): "1282"

Test #5:

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

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #6:

score: 0
Accepted
time: 31ms
memory: 95944kb

input:

5
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #7:

score: 0
Accepted
time: 35ms
memory: 108428kb

input:

3
abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...

output:

133586

result:

ok 1 number(s): "133586"

Test #8:

score: 0
Accepted
time: 22ms
memory: 105320kb

input:

3
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbabab...

output:

118967

result:

ok 1 number(s): "118967"

Test #9:

score: 0
Accepted
time: 45ms
memory: 102616kb

input:

3
bbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabb...

output:

114444

result:

ok 1 number(s): "114444"

Test #10:

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

input:

3
abbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbabab...

output:

115321

result:

ok 1 number(s): "115321"

Test #11:

score: 0
Accepted
time: 29ms
memory: 105880kb

input:

3
azzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazaz...

output:

131825

result:

ok 1 number(s): "131825"

Test #12:

score: 0
Accepted
time: 19ms
memory: 86640kb

input:

3
yazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbyb...

output:

6

result:

ok 1 number(s): "6"

Test #13:

score: 0
Accepted
time: 21ms
memory: 84452kb

input:

3
azbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazby...

output:

6

result:

ok 1 number(s): "6"

Test #14:

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

input:

3
byazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyaz...

output:

6

result:

ok 1 number(s): "6"

Test #15:

score: 0
Accepted
time: 28ms
memory: 99728kb

input:

1
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabba...

output:

113382

result:

ok 1 number(s): "113382"

Test #16:

score: 0
Accepted
time: 26ms
memory: 99404kb

input:

5
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr...

output:

123447499

result:

ok 1 number(s): "123447499"

Test #17:

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

input:

5
tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...

output:

25319820

result:

ok 1 number(s): "25319820"

Test #18:

score: 0
Accepted
time: 16ms
memory: 90120kb

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

2746507

result:

ok 1 number(s): "2746507"

Test #19:

score: 0
Accepted
time: 23ms
memory: 108200kb

input:

3
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...

output:

1912677071

result:

ok 1 number(s): "1912677071"

Test #20:

score: 0
Accepted
time: 16ms
memory: 99772kb

input:

3
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxcxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

111259628

result:

ok 1 number(s): "111259628"

Test #21:

score: 0
Accepted
time: 7ms
memory: 86840kb

input:

3
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

13754174

result:

ok 1 number(s): "13754174"

Test #22:

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

input:

3
dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd...

output:

1867151

result:

ok 1 number(s): "1867151"

Test #23:

score: 0
Accepted
time: 23ms
memory: 92856kb

input:

1
jjqjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjvjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...

output:

1856484

result:

ok 1 number(s): "1856484"

Test #24:

score: 0
Accepted
time: 18ms
memory: 83620kb

input:

1
vvvvvvvvvvvvvvvvvvvvvvvvvvvqvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvsvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvnvvvvvvvvvvvvvvvvvvvv...

output:

190722

result:

ok 1 number(s): "190722"

Test #25:

score: 0
Accepted
time: 18ms
memory: 88596kb

input:

1
txxxxxxxxxxxxxxxxxxxxxxxxxxxxhxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxrxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxhxxxxxtxlxxxxxxxxxktxxxxxxxxxxxxxxxxxexxxxxxxxxxxxxxgxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxjxxxxxxxxxxxxxxxxxxxvxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzqxxjxxxxxxxxxxxxxxx...

output:

76004

result:

ok 1 number(s): "76004"

Test #26:

score: 0
Accepted
time: 22ms
memory: 94416kb

input:

1
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

81149988

result:

ok 1 number(s): "81149988"

Test #27:

score: 0
Accepted
time: 28ms
memory: 108600kb

input:

1
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

1272080790

result:

ok 1 number(s): "1272080790"

Test #28:

score: 0
Accepted
time: 41ms
memory: 122616kb

input:

1
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee...

output:

12890286923

result:

ok 1 number(s): "12890286923"

Test #29:

score: 0
Accepted
time: 23ms
memory: 100476kb

input:

5
dgasxxawfuzttbnrniddspiplejfqzzoadnogyemjktjqqjtkjmeygondaozzqfjelpipsddinrnbttzufwaxxsagdvkrreghjrkkrjhgerrkvdgasxxawfuzttbnrniddspiplejfqzzoadnogyemjktjqqjtkjmeygondaozzqfjelpipsddinrnbttzufwaxxsagdvkrreghjrkkrjhgerrkvdgasxxawfuzttbnrniddspiplejfqzzoadnogyemjktjqqjtkjmeygondaozzqfjelpipsddinrnbt...

output:

652993

result:

ok 1 number(s): "652993"

Test #30:

score: 0
Accepted
time: 29ms
memory: 98536kb

input:

5
jlpzojmatlmawicowbaazzfyzqdjodsyngoqfnxbshbjywkgafhdarnchbwcskosqxpdjffjdpxqsokscwbhcnradhfagkwyjbhsbxnfqognysdojdqzyfzzaabwociwamltamjozpljjlpzojmatlmawicowbaazzfyzqdjodsyngoqfnxbshbjywkgafhdarnchbwcskosqxpdjffjdpxqsokscwbhcnradhfagkwyjbhsbxnfqognysdojdqzyfzzaabwociwamltamjozpljjlpzojmatlmawicowb...

output:

425510

result:

ok 1 number(s): "425510"

Test #31:

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

input:

5
zwzxfvwcwglyetqbpgxubiqntaydeqmdpassapdmqedyatnqibuxgpbqteylgwcwvfxzwzjeiveeviejzwzxfvwcwglyetqbpgxubiqntaydeqmdpassapdmqedyatnqibuxgpbqteylgwcwvfxzwzjeiveeviejzwzxfvwcwglyetqbpgxubiqntaydeqmdpassapdmqedyatnqibuxgpbqteylgwcwvfxzwzjeiveeviejzwzxfvwcwglyetqbpgxubiqntaydeqmdpassapdmqedyatnqibuxgpbqte...

output:

1180524

result:

ok 1 number(s): "1180524"

Test #32:

score: 0
Accepted
time: 22ms
memory: 97816kb

input:

5
rmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiq...

output:

4551019

result:

ok 1 number(s): "4551019"

Test #33:

score: 0
Accepted
time: 30ms
memory: 93328kb

input:

5
tnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskk...

output:

18042012

result:

ok 1 number(s): "18042012"

Test #34:

score: 0
Accepted
time: 39ms
memory: 98072kb

input:

5
wosalwxbdgvouchgnkqygjphbtpoxduzlpmpbuhhmwvgsbrfolbykyjzoukregdyxskkinjqzjeuublzpuukcaazbsggluyqlmyiallofjebbukuqcalufrqdjjkgvooretzaasgnpnztfalutzztulaftznpngsaazteroovgkjjdqrfulacqukubbejfollaiymlqyulggsbzaackuupzlbuuejzqjnikksxydgerkuozjykyblofrbsgvwmhhubpmplzudxoptbhpjgyqknghcuovgdbxwlasowovxg...

output:

61625

result:

ok 1 number(s): "61625"

Test #35:

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

input:

5
pyybsfiukgpneuwnykmxylcpaujvzpvcubdlvljkdwxkniwznzqvfblfedmydoqqrysksoobrwsqguocoxtfnisqmtbbieekshiwrzrbluflrtzfxwkvqtplcinkqqjsxogdsyucodbzhhnzaluymttfnzovqnevrqtbtqpmtgsfvnenstchzhdrequfxuasnkoxexafwpbgzqaobiicvmwugeugfgpmjvfphfojacdfhjplypqfoxzoacnfoucbhlqqnxxywfdaykxbsfkkkbwuryfwowvhecdgtnzcnp...

output:

57998

result:

ok 1 number(s): "57998"

Test #36:

score: 0
Accepted
time: 22ms
memory: 91452kb

input:

5
pndpupqzhnvxfilkpqdiabywphmclxjchfoctreacxnxwernjkhtyrgokfjpcuuqstsoserfmhfnrgdhzsioknvrhqflrjfkgkjrtoouchgeduceggstnsraurhpxgreryesioloxkcnndjdzyrfmksunizovolqltamzkmaggqftuvwjnkrhgyewthkqchdrgqrkwdfdwdoqunjulkpykaavlinxbzfuzzoqyvwrsfgmtvrzoyidesgkfwtbunicodseljtsxdzxpvpjnbaunefavrjjzhufqqsvekbpl...

output:

46840

result:

ok 1 number(s): "46840"

Test #37:

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

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

90000000000

result:

ok 1 number(s): "90000000000"

Test #38:

score: 0
Accepted
time: 20ms
memory: 88128kb

input:

5
nmnnmnnmnnmnnmmmnnmmmmmnnnnnmmnmnnnnnmmnmmmnnnmnmnmnmmmmmnnnnmnnnmnnnmmmnmnmmmmnmmnmmmnnnnmmmmmnmnnmmmnmmnmmnmmmnnnmmmnmmnnnmmmnnmnnnmnmmmnnnnmmmnmnnmnmmmmnnnnnnnmnnnmmmmnmmnnnmnnnmmmnnmmnmnmmnnmmmmnnmnnnmmmmmmnmmnnnmnnnnnmmnmnmmnmnnnmnmmnmnmmmnnmmnmnnnmnmmmmnmnnnmmmnmnmmnnnnnmmmnnmnnnnnnmmmmmmmnm...

output:

4526

result:

ok 1 number(s): "4526"

Test #39:

score: 0
Accepted
time: 20ms
memory: 87932kb

input:

5
aaupapuupauuauapupapauauuuuuaapauuaaapppuauuppupuapappuapuuuuaupappaauupapppuppauuaauppuappaappaupaaapaapupuuapaauuuppppuaapaaauuapupuaaapppuuaaapuuuapuaupaaapupaauaapuaapaaaaupuuuupupuapaaaapaupaaaapppuapapuauauapuaauuapapuappauauappuappppuppaauapapuapuauuapupaupaauauupaauapuaupauauuapaappaapaapp...

output:

2372

result:

ok 1 number(s): "2372"

Test #40:

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

input:

5
bkdbddddvddkvkvdbkvdvbbdkkkvvkbvbvbvvbvvvkdbdkkkdvbdkdkvbbbbkbbvbkddkbdvbkkkbdvvdkkdvkbkkdvddbdvdkkdkvbkkdkkbvddddvdvvkkvbbdvkkvkbkkkkkvddbbkdkbvdkbkkdvkvvvvkbkkvkbbdvbkdbkdbkvkkkkvkvkkvvkkvkbbvbvbbbvkbvbvkkvkvkbvbdvvdkkvdbkvbdvvdkvddvvddvkdbkbbvkbvdbvvdddkbdddvbbbdvvdddvdkbdkbkkdbvbkdvdddvddbkkvk...

output:

2339

result:

ok 1 number(s): "2339"

Test #41:

score: 0
Accepted
time: 20ms
memory: 81956kb

input:

2
afffafafaa
afaafaafaf

output:

29

result:

ok 1 number(s): "29"

Test #42:

score: 0
Accepted
time: 22ms
memory: 82260kb

input:

5
wjdulwwjulujdddljudwwlddduddujljjjdluljwddjuddddljwjuujdllllljuudddjwududddudllwudluldwudddwdllldlwwwdjlwuwwlddlluluwdlldjuudujdjujddwduwwjwlluudjjujjdudlljwdwduwjdljlwdjddwddddludwuuwlddddddljddlduddwldwddllduwjwddjdulwddjwddddwujwluujjjludwjddwwdjwddulldjwljudjljljduddjlddjujdddddudduljduuuljwul...

output:

2063

result:

ok 1 number(s): "2063"

Test #43:

score: 0
Accepted
time: 47ms
memory: 81956kb

input:

1000000
i
n
l
f
q
i
s
m
u
x
r
v
v
u
b
m
o
u
s
q
k
t
t
c
n
t
y
m
x
q
k
v
h
q
s
w
o
b
o
y
n
s
f
w
d
d
y
d
l
i
e
r
c
l
e
d
h
h
c
l
x
q
f
l
v
j
q
j
p
o
e
s
l
w
u
h
q
f
j
g
l
h
v
x
k
w
t
h
o
b
e
s
x
c
m
v
r
r
p
w
d
g
r
u
g
d
j
a
a
c
w
t
u
h
x
i
l
s
o
z
i
m
p
h
j
u
p
t
g
f
p
w
x
f
o
w
u
m
a
k
p
p
q
x
n
r
...

output:

26

result:

ok 1 number(s): "26"

Test #44:

score: 0
Accepted
time: 36ms
memory: 87812kb

input:

1000000
u
i
n
f
z
i
g
y
o
t
a
t
y
q
m
g
u
z
t
j
j
s
f
r
f
z
a
e
k
s
q
u
p
e
o
l
x
g
q
b
l
w
x
c
u
x
j
e
s
e
y
r
r
v
v
i
d
p
q
e
q
q
z
a
d
i
e
y
w
p
e
x
m
n
e
f
j
l
c
y
x
i
d
a
m
k
w
q
y
j
c
u
y
h
k
l
y
j
r
e
r
b
n
i
w
r
o
i
q
m
o
r
x
d
s
u
n
i
w
r
t
g
c
i
d
h
n
a
x
h
t
c
s
h
c
j
c
i
b
z
u
z
c
b
e
k
...

output:

26

result:

ok 1 number(s): "26"

Test #45:

score: 0
Accepted
time: 40ms
memory: 81988kb

input:

1000000
c
c
b
c
b
b
a
c
c
b
c
b
a
a
a
a
c
b
a
c
c
c
c
b
c
a
c
c
b
a
a
a
c
c
b
b
c
a
c
a
c
c
c
c
a
b
c
b
a
b
c
a
a
a
b
c
a
c
b
c
b
a
c
b
a
b
c
c
a
c
b
c
a
b
c
c
b
a
a
a
c
b
c
a
b
b
c
b
a
a
c
c
c
b
b
a
b
a
c
b
a
b
c
b
b
b
a
b
a
a
c
a
b
b
c
a
a
c
c
b
a
a
c
b
a
b
a
b
b
b
b
b
c
a
b
b
c
a
a
a
b
a
b
b
a
c
...

output:

3

result:

ok 1 number(s): "3"

Test #46:

score: 0
Accepted
time: 28ms
memory: 88480kb

input:

1
alngdzgfsplrmhhyblurpjxyqhrxmbyyubvvxtmuwrnfimiggwhsoluetintakqfohgtmtampxljpkawolbuyrsrmdjapecfytjcfxcdcyymbfaqshkujxxypteohceukrejaveenkmsdxrmpdlapcnsnowykiiqisgdratbqcwxfzspkglkqghmcsiqwemkilaisqucgithhcrjvoydpnmtmxdwsmjfjtimsqpvesagpqucssfwyricarvcpcujfsxupluoxxkzelyjqewsptiyobhrvdatjhbcohcdfd...

output:

3195

result:

ok 1 number(s): "3195"

Test #47:

score: 0
Accepted
time: 34ms
memory: 88388kb

input:

1
ghbhcdfhccifjigghcfhejhfcaibghfhehehjichadijbiihajddhgjgbdibecjjcaagedfaafejcfjjgdaiebcjihecjicadacefgbajeafccjdbafdjhjddjggbdhgdijbbiadeabbaiieacbeighagbaajgdbdajgajcabhcgfcadbadigjhehaibighhdjhaeggefhgfcfhaahhchedcjhbaedihgfgjiejeifbdieacghbghfjdjfehfgdfadeeghdjdcghibjdhiiggdchdbihfchbhchaeefccb...

output:

3395

result:

ok 1 number(s): "3395"

Test #48:

score: 0
Accepted
time: 32ms
memory: 82516kb

input:

1
fgffhhghheehgggfgghdeeeedgfdhdfehghhegeeggfhgdfhgfgedgdgdegedhegeedddefdfedhfgdhghehhggehdffdfgddhegeghefffgddedfeeggfheghhgghhhehfefhfegfgghfffdhfddgheegdgefdhhegfffefghhehgggheegdggddeggdehddhdfefgeffdgfdghefgegdhegdfggeggddhhddefghfgedhhdeghgfedhddefdhfhfdhfdghhegedfhdeefffegedddgfgefheffeeeedd...

output:

4178

result:

ok 1 number(s): "4178"

Test #49:

score: 0
Accepted
time: 35ms
memory: 84472kb

input:

100
xuxmuutatmmtxmautmmttuuaatmtamxmutxautxxttmuamtxaaumaautaaattmmmxumtxaaxmxxmmumuttmututmtmuauutuuuumtuaxmaaxattxattuuxumxtummmttmmutmmataxuuttattmatumxxatuxumatxutmtuuaaatxatutmmtutauauuuuxumataxtamauttaaxxuttaaxtauamammxumauxumuuutmuxmauxutuxuxtutmtatuxttxtummtxutxmaxuuxxtxuatuamuxaatuatuauxxmu...

output:

30276

result:

ok 1 number(s): "30276"

Test #50:

score: 0
Accepted
time: 45ms
memory: 92240kb

input:

100
wddldawddddlwwawawdwdldldldldawdwwdwaaddlddddadwladdddaddawadladlwldlalldddlddlddwdlwwddaddllwwdldddwwldddaadwadddddlddlwwdawawdwaawadadadldddwaaldadallwdwlwdlddadlddladdlddddaaddddlwwdaalddddwldaddadaddwawwalaalladdalllddadwddddadlwlddlddwldaadlwddwlldddadwwaddaaldddwwlddddddwddadddalwawddwdawd...

output:

30213

result:

ok 1 number(s): "30213"

Test #51:

score: 0
Accepted
time: 40ms
memory: 88812kb

input:

100
ygripyrkwoyooyykfppktyktktikoyyogttiorfyptgtogkygrtkiwgyoipkpkkiiikypgftggfpktrwoygfwptwpwfyptpwrwyigyokwprkfpkfkfwpfykrfygoyykkgfigyktyryrfpkfwoipoipotypiifpyooykkpokgopooykywyiwgoypwtwygfikorpoirptfffkwirriyyyypfpkiwrpyfgtwrtfyfotpttfrwpfoprftpyigfrtggpwifypwyfpowpripgtfrgkyirkrorfgrorwpopioig...

output:

16720

result:

ok 1 number(s): "16720"

Test #52:

score: 0
Accepted
time: 67ms
memory: 138904kb

input:

100
ywwcynkynntwwqtcyjcnkjtkwctnqwcttnnqwqjjqjjwykwwyjwnywkwqwnjytqkyyjwqwwycyycjtqyqyjyqqynqwwtnwcjwjckjnnywjwwjntnwwjywywwwkwwtcqnkqqjqqwkknnykjcynwnyyqwjwyjckkcnqyqwkywyykkwcwwwkcknkwttnqyqytnttyjqtwwywqyytywkcwyqnqwywwwtwywjwqjwcwcqwkqcqnywkkwyncjwtkcwqtjycywtjkywyknyjqcwqwtywqjktwytkcwykwknnwyj...

output:

346933

result:

ok 1 number(s): "346933"

Test #53:

score: 0
Accepted
time: 72ms
memory: 143408kb

input:

100
nmxxmmvdyyfnmmvmmunvmfmvrnddnryrmdrvuurmuvnmudnnrrmyvmvuvdxvyxvmumnnrxummffuvdrmxnydfxnxfnxmnvmyfnmuyxruxfymyryunrmfmdmmxmufnmmmmmryrnfmrrvrfvfdxumymxmmxmxxmnfyddmmurvfvumfmxrmvfmnxnmnrvmyxfyrvnyfyyvvrmryynruyxmfmvmxxmrxrvmxudyvfxndrnvunvmnyxvyfvvxrndmffdvrfvfmmufdumxdvmumvmmxnmxdudyyfrdvmrxvyyx...

output:

354764

result:

ok 1 number(s): "354764"

Test #54:

score: 0
Accepted
time: 52ms
memory: 129140kb

input:

100
hohohoohoohhoohhhhhhohohhhooohhohoooohohhhoooohohhhoohhooohhhooohhoooohooooooohohhhoohohohhhohoohhohhohhoohohhhohohoohhhohooooooohoooohhooohhhooohhoohhhohoooohhhohoooohohhooohhhohohhhhhhoohhoohoohohohhohhoohohhhohohoohhhohooooooohoooohhooohhhooohhoohhhohoooohhhohoooohohhooohhhohohhhhhhoohhoohooh...

output:

400202791

result:

ok 1 number(s): "400202791"

Test #55:

score: 0
Accepted
time: 40ms
memory: 125664kb

input:

100
yyyyyjyyjjjyyjjjjjyjyyyjyyjyyjyyyjyyyyjjyyjjjyyyjyyyyjjjyyyjjyjyyyyyyyyyjjjyyjjyjjjyyyyjjjyyyyjyyyyyyyyyyjyyyyjjjyyyyjjjyjjyyjjjyyyyyyyyyjyjjyyyjjjyyyyjyyyjjjyyjjyyyyjyyyjyyjyyjyyyjyjjjjjyyjjjyyjyyyyyyyyyyjyyjjjyyjjjjjyjyyyjyyjyyjyyyjyyyyjjyyjjjyyyjyyyyjjjyyyjjyjyyyyyyyyyjjjyyjjyjjjyyyyjjjyyyyjy...

output:

200209587

result:

ok 1 number(s): "200209587"

Test #56:

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

input:

100
coppocpcpccpccppocopcooccopopccopccocccpocooccocpcppccocoppcocoppcoocoopopoooopppopppoccppccpcppccoccoccppcpccppccopppopppoooopopoocoocppococppococcppcpcoccoocopcccoccpoccpopoccoocpocoppccpccpcpcoppoccoccppcpccppccopppopppoooopopoocoocppococppococcppcpcoccoocopcccoccpoccpopoccoocpocoppccpccpcpco...

output:

203651

result:

ok 1 number(s): "203651"