QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#431270#4187. Decrypting Zodiackevinyang#AC ✓6834ms10936kbC++1415.0kb2024-06-05 08:45:122024-06-05 08:45:14

Judging History

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

  • [2024-06-05 08:45:14]
  • 评测
  • 测评结果:AC
  • 用时:6834ms
  • 内存:10936kb
  • [2024-06-05 08:45:12]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <cstdint>
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<double, double> pd;
typedef pair<ld, ld> pld;
typedef tuple<int, int, int> ti;
typedef tuple<ll, ll, ll> tll;
typedef tuple<double, double, double> td;
typedef complex<double> cd;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> bbst;
 
 
mt19937 g1;
int get_random_int(int a, int b) {
    return uniform_int_distribution<int>(a, b)(g1);
}
 
//const ll MOD = 100000000105583;
//const int MOD = 1e9 + 7;
const int MOD = 998244353;
struct Mint {
    int v;
    Mint() {v = 0;}
    Mint(int nv) {v = nv;}
    Mint(const Mint &a) {v = a.v;}
    Mint pow(int a) {
        long long ret = 1;
        long long base = v;
        if(a < 0) {
            a = -a;
            base = Mint(v).inv().v;
        }
        while(a > 0) {
            if(a & 1) ret = (ret * base) % MOD;
            base = (base * base) % MOD;
            a >>= 1;
        }
        return Mint((int)ret);
    }
    Mint inv() {return this->pow(MOD - 2);}
    Mint operator + (int a) const {return Mint((v + a) % MOD);}
    Mint operator + (const Mint &a) const {return Mint((v + a.v) % MOD);}
    Mint& operator += (int a) {
        v = (v + a) % MOD;
        return *this;
    }
    Mint& operator += (const Mint &a) {
        v = (v + a.v) % MOD;
        return *this;
    }
    Mint operator - (int a) const {return Mint((v - a + MOD) % MOD);}
    Mint operator - (const Mint &a) const {return Mint((v - a.v + MOD) % MOD);}
    Mint& operator -= (int a) {
        v = (v - a + MOD) % MOD;
        return *this;
    }
    Mint& operator -= (const Mint &a) {
        v = (v - a.v + MOD) % MOD;
        return *this;
    }
    Mint operator * (int a) const {return Mint(((long long)v * a) % MOD);}
    Mint operator * (const Mint &a) const {return Mint(((long long)v * a.v) % MOD);}
    Mint& operator *= (int a) {
        v = ((long long)v * a) % MOD;
        return *this;
    }
    Mint& operator *= (const Mint &a) {
        v = ((long long)v * a.v) % MOD;
        return *this;
    }
    Mint operator / (int a) const {return Mint(v) * Mint(a).inv();}
    Mint operator / (const Mint a) const {return Mint(v) * Mint(a).inv();}
    Mint& operator /= (int a) {
        v = ((long long)v * Mint(a).inv().v) % MOD;
        return *this;
    }
    Mint& operator /= (const Mint &a) {
        v = ((long long)v * Mint(a).inv().v) % MOD;
        return *this;
    }
    Mint& operator = (int a) {
        v = a;
        v %= MOD;
        if(v < 0) v += MOD;
        return *this;
    }
    bool operator == (int a) const {return v == a;}
    bool operator == (const Mint &a) const {return v == a.v;}
    bool operator != (int a) const {return v != a;}
    bool operator != (const Mint &a) const {return v != a.v;}
    friend ostream& operator << (ostream &os, const Mint &a) {
        os << a.v;
        return os;
    }
};
 
const int MAX = 2e6;
const int BLK = 1000;
 
int n, m;
 
string s, t;
 
bool match(char a, char b) {
    if(a == b || a == '-' || b == '-') return true;
    return false;
}
 
bool match(const string& a, const string& b) {
    if(a.length() != b.length()) return false;
    for(int i = 0; i < a.length(); i++) {
        if(!match(a[i], b[i])) return false;
    }
    return true;
}
 
bool suffixMatch(string& a, string& b) {
    int l = min(a.length(), b.length());
    for(int i = 0; i < l; i++) {
        if(!match(a[i], b[i])) return false;
    }
    return true;
}
 
void case1() {
    string ssuf, tsuf;
    for(int i = 0; i < n; i++) {
        if(s[i] == '*') break;
        ssuf += s[i];
    }
    for(int i = 0; i < m; i++) {
        if(t[i] == '*') break;
        tsuf += t[i];
    }
    if(!suffixMatch(ssuf, tsuf)) {
        cout << "No\n";
        return;
    }
    ssuf = "";
    tsuf = "";
    for(int i = n - 1; i >= 0; i--) {
        if(s[i] == '*') break;
        ssuf += s[i];
    }
    for(int i = m - 1; i > 0; i--) {
        if(t[i] == '*') break;
        tsuf += t[i];
    }
    if(!suffixMatch(ssuf, tsuf)) {
        cout << "No\n";
        return;
    }
    cout << "Yes\n";
    return;
}
 
void case2() {
    if(n != m) {
        cout << "No\n";
        return;
    }
    for(int i = 0; i < n; i++) {
        if(!match(s[i], t[i])) {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
    return;
}
 
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
 
template<typename T> tuple<T, T, T> ext_gcd(T a, T b) {
    if (!a) return {b, 0, 1};
    auto [g, x, y] = ext_gcd(b%a, a);
    return {g, y - b/a*x, x};
}
 
template<typename T = ll> struct crt {
        T a, m;
 
        crt() : a(0), m(1) {}
        crt(T a_, T m_) : a(a_), m(m_) {}
        crt operator * (crt C) {
                auto [g, x, y] = ext_gcd(m, C.m);
                if ((a - C.a) % g) a = -1;
                if (a == -1 or C.a == -1) return crt(-1, 0);
                T lcm = m/g*C.m;
                T ans = a + (x*(C.a-a)/g % (C.m/g))*m;
                return crt((ans % lcm + lcm) % lcm, lcm);
        }
};
 
template<int p> struct mod_int {
        ll pow(ll b, ll e) {
                if (e == 0) return 1;
                ll r = pow(b*b%p, e/2);
                if (e%2 == 1) r = (r*b)%p;
                return r;
        }
        ll inv(ll b) { return pow(b, p-2); }
 
        using m = mod_int;
        int v;
        mod_int() : v(0) {}
        mod_int(ll v_) {
                v = v_;
                if (v >= p or v <= -p) v %= p;
                if (v < 0) v += p;
        }
        m& operator+=(const m &a) {
                v += a.v;
                if (v >= p) v -= p;
                return *this;
        }
        m& operator-=(const m &a) {
                v -= a.v;
                if (v < 0) v += p;
                return *this;
        }
        m& operator*=(const m &a) {
                v = v * ll(a.v) % p;
 
                return *this;
        }
        m& operator/=(const m &a) {
                v = v* inv(a.v) % p;
                return *this;
        }
        m operator-(){ return m(-v); }
        m& operator^=(ll e) {
                if (e < 0){
                        v = inv(v);
                        e = -e;
                }
                v = pow(v, e%(p-1));
                return *this;
        }
        bool operator==(const m &a) { return v == a.v; }
        bool operator!=(const m &a) { return v != a.v; }
 
        friend istream &operator>>(istream &in, m& a) {
                ll val; in >> val;
                a = m(val);
                return in;
        }
        friend ostream &operator<<(ostream &out, m a) {
                return out << a.v;
        }
        friend m operator+(m a, m b) { return a+=b; }
        friend m operator-(m a, m b) { return a-=b; }
        friend m operator*(m a, m b) { return a*=b; }
        friend m operator/(m a, m b) { return a/=b; }
        friend m operator^(m a, ll e) { return a^=e; }
};
 
// const int MOD = 998244353;
const long long MOD2 = (long long) MOD * MOD;
const int root = 3;
const int alim = 64; // Bound for using O(n^2) polynomial mult
 
int modpow(int b, int e) {
    int ans = 1;
    for (; e; b = (long long) b * b % MOD, e /= 2)
        if (e & 1) ans = (long long) ans * b % MOD;
    return ans;
}
 
const int MODinv = 2 - MOD; // pow(-MOD, -1, 2**32)
inline int m_reduce(long long x) {
    int m = x * MODinv;
    return (x>>32) - (((long long) m * MOD) >> 32);
}
 
const int r2 = modpow(2, 64);
inline int m_transform(int x) {
    return m_reduce((long long)x * r2);
}
 
inline int m_add(int x, int y) {
    int z = x + y;
    return z < 0 ? z + MOD : z - MOD;
}
 
inline int m_sub(int x, int y) {
    int z = x - y;
    return z < 0 ? z + MOD : z - MOD;
}
 
inline int m_mult(int x, int y) {
    return m_reduce((long long) x * y);
}
 
vector<int> rt = {1};
vector<int> transformed_rt;
vector<int> transformed_rt2;
 
template<int a>
void transform(vector<int> &P) {
    int m = P.size();
    int n = m / a;
 
    int size = rt.size();
    while (2 * size < n) {
        rt.resize(n / 2);
        int r = modpow(root, MOD / (4 * size));
        for (int i = 0; i < size; ++i)
            rt[i + size] = (long long) r * rt[i] % MOD;
        size *= 2;
    }
 
    // For montgomery
    for (int i = transformed_rt.size(); i < (int)rt.size(); ++i) {
        transformed_rt.resize(rt.size());
        transformed_rt[i] = m_transform(rt[i]);
        transformed_rt2.resize(rt.size());
        transformed_rt2[i] = (unsigned int) MODinv * transformed_rt[i];
    }
 
    // Radix 4 recursive NTT
    auto dfs = [&](auto &&self, int i, int k) -> void {
        if (k == 1)
          return;
        int step = k * a;
        int quarter_step = step / 4;
 
        int R20 = transformed_rt2[2 * i];
        int RR0 = transformed_rt[2 * i];
 
        int R21 = transformed_rt2[2 * i + 1];
        int RR1 = transformed_rt[2 * i + 1];
 
        int R2 = transformed_rt2[i];
        int RR = transformed_rt[i];
 
        int *P1 = &P[i * step];
        int *P2 = P1 + quarter_step;
        int *P3 = P2 + quarter_step;
        int *P4 = P3 + quarter_step;
 
        #pragma GCC ivdep
        for (int j = 0; j < quarter_step; ++j) {
            int z0;
            {
                int z = P3[j];
                int m = (unsigned int) R2 * z;
                z0 = ((long long) z * RR - (long long) m * MOD) >> 32;
            }
 
            int z1;
            {
                int z = P4[j];
                int m = (unsigned int) R2 * z;
                z1 = ((long long) z * RR - (long long) m * MOD) >> 32;
            }
 
            int sum0 = m_add(P1[j], z0);
            int diff0 = m_sub(P1[j], z0);
            int sum1 = P2[j] + z1;
            int diff1 = P2[j] - z1;
 
            // [sum0, sum1, diff0, diff1]
 
            int zz0;
            {
                int z = sum1;
                int m = (unsigned int) R20 * z;
                zz0 = ((long long) z * RR0 - (long long) m * MOD) >> 32;
            }
 
            int zz1;
            {
                int z = diff1;
                int m = (unsigned int) R21 * z;
                zz1 = ((long long) z * RR1 - (long long) m * MOD) >> 32;
            }
 
            P1[j]  = m_add(sum0, zz0);
            P2[j]  = m_sub(sum0, zz0);
            P3[j]  = m_add(diff0, zz1);
            P4[j]  = m_sub(diff0, zz1);
        }
 
        self(self, 4*i+0, k/4);
        self(self, 4*i+1, k/4);
        self(self, 4*i+2, k/4);
        self(self, 4*i+3, k/4);
    };
 
    int k = n;
    while (k >= 4) k /= 4;
 
    if (k == 2) {
        int step = n * a;
        int half_step = step / 2;
        for (int j1 = 0; j1 < half_step; ++j1) {
            int j2 = j1 + half_step;
 
            int diff = m_sub(P[j1], P[j2]);
            P[j1] = m_add(P[j1], P[j2]);
            P[j2] = diff;
        }
        k = n/2;
        dfs(dfs, 0, k);
        dfs(dfs, 1, k);
    } else {
        k = n;
        dfs(dfs, 0, k);
    }
 
    for (int i = 0; i < m; ++i)
        if (P[i] < 0) P[i] += MOD;
}
 
template<int a>
void inverse_transform(vector<int> &P) {
    int m = P.size();
    int n = m / a;
    int n_inv = m_transform(modpow(n, MOD - 2));
 
    vector<int> rev(n);
    for (int i = 1; i < n; ++i) {
        rev[i] = rev[i / 2] / 2 + (i & 1) * n / 2;
    }
 
    // P = [p * n_inv for p in P]
    for (int i = 0; i < m; ++i)
        P[i] = m_mult(n_inv, P[i]);
 
    // P = [P[a * rev[i // a] + (i % a)] for i in range(m)]
    for (int i = 1; i < n; ++i)
        if (i < rev[i])
            swap_ranges(P.begin() + a * i, P.begin() + a * i + a, P.begin() + a * rev[i]);
 
    // P = [P[-a * (i // a) + (i % a)] for i in range(m)]
    for (int i = 1; i < n/2; ++i)
        swap_ranges(P.begin() + a * i, P.begin() + a * i + a, P.begin() + a * (n - i));
 
    transform<a>(P);
 
    // P = [P[a * rev[i // a] + (i % a)] for i in range(m)]
    for (int i = 1; i < n; ++i)
        if (i < rev[i])
            swap_ranges(P.begin() + a * i, P.begin() + a * i + a, P.begin() + a * rev[i]);
}
 
template<int a>
void fast_polymult_mod(vector<int> &P, vector<int> &Q) {
    int m = P.size();
    int n = m / a;
 
    transform<a>(P);
    transform<a>(Q);
 
    vector<int> &PQ = P;
    for (int i = 0; i < n; ++i) {
        vector<unsigned long long> res(2 * a);
        for (int j = 0; j < a; ++j) {
            if (j >= 10 && j % 9 == 8)
                for (int k = j; k < j + a - 10; ++k)
                    res[k] -= (res[k] >> 63) * 9 * MOD2;
            for (int k = 0; k < a; ++k)
                res[j + k] += (long long) P[i * a + j] * Q[i * a + k];
        }
 
        int c = rt[i/2];
        if (i & 1) c = MOD - c;
        for (int j = 0; j < a; ++j)
            PQ[i * a + j] = (res[j] + c * (res[j + a] % MOD)) % MOD;
    }
 
    inverse_transform<a>(PQ);
}

template <size_t... N>
void work(std::index_sequence<N...>, int x, std::vector<int>& a, std::vector<int>& b) {
    static void (*ptrs[])(std::vector<int>&, std::vector<int>&) = {&fast_polymult_mod<N+1>...};
    ptrs[x - 1](a, b);
}
 
void fast_polymult(vector<int> &P, vector<int> &Q) {
    int m1 = P.size();
    int m2 = Q.size();
    int res_len = m1 + m2 - 1;
 
    int b = 1;
    while ((alim << b) < res_len) ++b;
    int a = ((res_len - 1) >> b) + 1;
    int m = a << b;
 
    P.resize(m);
    Q.resize(m);
 
    // Call fast_polymult_mod<a>(P, Q);
    work(std::make_index_sequence<alim>{}, a, P, Q);
 
    P.resize(res_len);
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    string s,t;
    cin >> s >> t;
    vector<int>a(n);
    vector<int>b(n);
    for(int i = 0; i<n; i++){
        a[i] = s[i]-'a';
        b[i] = t[i]-'a';
    }
    vector<vector<int>>idx(26);
    vector<vector<int>>idx2(26);
    for(int i = 0; i<n; i++){
        idx[a[i]].push_back(i);
        idx2[b[i]].push_back(i);
    }
    int ans = 0;
    for(int dx = 0; dx<26; dx++){
        vector<int>dp(n);
        
        for(int x = 0; x<26; x++){
            vector<int>ar(n+1);
            vector<int>br(n+1);
            for(int i: idx[x]){
                ar[i] = 1;
            }
            for(int i: idx2[(x+dx)%26]){
                br[n-i] = 1;
            }
            fast_polymult(ar,br);
            for(int i = 0; i<ar.size(); i++){
                dp[i%n]+=ar[i];
            }
        }
        for(int i = 0; i<n; i++){
            ans = max(ans,dp[i]);
        }
    }
    cout << n-ans << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

6
drhmex
zodiac

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

8
dicepara
paradise

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 1ms
memory: 4008kb

input:

13
lvlvdvdqsonwk
thisisasample

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 5668ms
memory: 10532kb

input:

150000
ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

144230

result:

ok single line: '144230'

Test #5:

score: 0
Accepted
time: 6834ms
memory: 10604kb

input:

150000
cccccccccccccmtccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccmfcrcccccccucccccccccccucccccccccyccoccccccccccccacccccbccccccccccccccccccccnccccccccccccccccccccclcccccccccccccccccccccckcccccccccccccccpcccccccccccccccccccccccbcccccqcccccccqccccccnycccceksckccccccccocccccccccccccc...

output:

144104

result:

ok single line: '144104'

Test #6:

score: 0
Accepted
time: 5741ms
memory: 10612kb

input:

150000
cccccccccccccctccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccckcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

144188

result:

ok single line: '144188'

Test #7:

score: 0
Accepted
time: 5676ms
memory: 10464kb

input:

150000
mlskccoxctpexrrfygtjtckjutzjaictbppyuovjxmgqdsxliigkbtdwuujwvbxcmmrahkynldbzdrhoanxhutnowdtrxjnenxplkrvzmvepxxnqoocplxcsidexplfcxzceufqfmghnkheurcllsnemhezbfqwmybtwqzjcxbbkarxeksjpnybqsomqfvpthtmrxvvhudntwobvhaklxmrqztpgfookwjdiypuljrpaduxbcoetirlejsbrknpojgtpusveqhegiuldicojiouondcjuehkbimsr...

output:

144230

result:

ok single line: '144230'

Test #8:

score: 0
Accepted
time: 5791ms
memory: 10564kb

input:

150000
kstbnrifsftqcvylmcfdxdmhtcjwauffntzfngdkztotkdasmxxrbicyfwdedwvkitqafpgemzuwvdypuoxtjnxdtzbmrrxpwtfxofrlxznfwhvwbwmgnqjmskuouimivuptfllnagthwbpjyrqbyrlagkhfqtseudnsojuxbauugljbaejyqqebggfwzjmkbmjogjmaoyrwvlbfccbhqksebvcfiuflnuuyxpoblmqbqdymcnqjjcitsynoqsuziolbutginragxhepqzkheqvfueumttctqoxkp...

output:

144090

result:

ok single line: '144090'

Test #9:

score: 0
Accepted
time: 5631ms
memory: 10360kb

input:

150000
kstbnrifsftqcvylmcfdxdmhtcjwauffntzfngdkztotkdasmxxrbicyfwdedwvkitqafpgemzuwvdypuoxtjnxdtzbmrrxpwtfxofrlxznfwhvwbwmgnqjmskuouimivuptfllnagthwbpjyrqbyrlagkhfqtseudnsojuxbauugljbaejyqqebggfwzjmkbmjogjmaoyrwvlbfccbhqksebvcfiuflnuuyxpoblmqbqdymcnqjjcitsynoqsuziolbutginragxhepqzkheqvfueumttctqoxkp...

output:

144187

result:

ok single line: '144187'

Test #10:

score: 0
Accepted
time: 5678ms
memory: 10728kb

input:

150000
nznanssdgutbwweyrmqhsotgvpcmajgeadjfexuzplxsivkozqowgigmoqdcwxmghhxyvszawdfclouotbxgfbzlpkaqoaibnynprylvcmsiuednvvktkejdxumuzgbgjlbtihkngtfeylpaqjvpefwthivnyzcvdhbgpachfwedzoftelhqhxuoekikmwuvvsfddirosgexgavdvgmroyrymssksjlefclhukwydtlkxtocgmkaajstnrisujibvzryeveimcqjniivemqnsmrdpwgvecmyazttd...

output:

143804

result:

ok single line: '143804'

Test #11:

score: 0
Accepted
time: 6075ms
memory: 10736kb

input:

150000
bhftmhqtqmltcxnygxqkozrwaqxuxczsiwrlcvsrbhzepxeggxlypsrabjessnegslpshvoaisjhranqqbhbeyebgfyozkchylzblleblohrjtfwrzbolmrkznqvkjnvclxdbeekzcbkewywjcdaubuuclsmxcslyzjiqagvrhqcktoadebtvyutdcawpfryybymlhcyxvbueumjaaclysshpttutcdfltsbzrbdcskomliuboedgdhnknrewztlbscoxnvzpdshqiaawnmenhkbbjmdgpupoqhgo...

output:

143849

result:

ok single line: '143849'

Test #12:

score: 0
Accepted
time: 5670ms
memory: 10752kb

input:

150000
fpagchsakklabymmpmyrsluqaqlupcshghcsnxkczhzhfzoztumdxgfubgpejktldbosntfuvraojcrvhwaasesmytilkwxecqewxzpitjowvrbdbdcahyigvonvqzasixpazorauoohlekwedequqhtuixyepiqnjotjhxdryyhwafsfcpidwzzplbfjdlutbmxlojjfaoeuqxgtitwcpzinbxacumzezlpjotuzvaymdjocnsfkzohmgosbnbhrbcxkzogplntxwweoshuuroeonqhhxbkpdqkh...

output:

143837

result:

ok single line: '143837'

Test #13:

score: 0
Accepted
time: 5735ms
memory: 10936kb

input:

150000
gjodcowfpbskvjhwilokpquumtimojricrslxqibrlesfbvlzyzidfscqtunhcmcbilztxsktwkcwfashgqbfesfbjwbtkykbfjyfbcxtvbftmyideiigieuhwhfoywkexdjlttpdskgarwujsasnbpgbegewrzqenohsxxicuxexnvxitfejocqscxyaqaczzarplydezbolwnunueyeygbfltdatzusyieotlexeqmlqexqmkrzxkbuiexstdemftnjqykqmdmxnozakbuvwhrjlnhgyjhixodd...

output:

143811

result:

ok single line: '143811'

Test #14:

score: 0
Accepted
time: 5719ms
memory: 10652kb

input:

150000
koyqowexlfpmfayhxjgnjysiwjlmhxtvymxwuglrckdwjwbnrnhsfqhgsrodzmzrvpgboqaimsssofirxfzrcnqcwbjmzcrqredlkfdbfwqtmkjqkamtjkdtlhhvsdldpapeqyyaueosatvoptdsxxojxenjlfivtjpofziaxajrarlptfwxekujrlqzvblimmzvndhctolswmygpcdkizuggfeuqblufxptosakasoseecrfspxxmxhlvfscslhruafsgpirpikhfhoxbclgnbuxeqpfhekqupov...

output:

143871

result:

ok single line: '143871'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

6
dabccd
dddcaa

output:

4

result:

ok single line: '4'

Test #16:

score: 0
Accepted
time: 1ms
memory: 4040kb

input:

5
aaabb
aabbb

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

9
aaaaabbbb
aaaabbbba

output:

0

result:

ok single line: '0'

Test #18:

score: 0
Accepted
time: 1ms
memory: 3780kb

input:

26
abcdefghijklmnopqrstuvwxyz
zabcdefghijklmnopqrstuvwxy

output:

0

result:

ok single line: '0'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

27
abcdefghijklmnopqrstuvwxyzz
zabcdefghijklmnopqrstuvwxyy

output:

0

result:

ok single line: '0'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3912kb

input:

27
abcdefghijklmnopqrstuvwxyzz
zabcdefghijklmnopqrstuvwxyz

output:

0

result:

ok single line: '0'

Test #21:

score: 0
Accepted
time: 1ms
memory: 3920kb

input:

6
dabcbc
dccbdb

output:

4

result:

ok single line: '4'

Test #22:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

4
ahfa
ddgc

output:

2

result:

ok single line: '2'

Test #23:

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

input:

630
wkwyxtwpzwrjyvejrfpkucfycvypdlbvmkdjmqtekyyjgpqbipesqsgwjylhzzmqnempgwnqdrulvwdzgqvazopkwokqatoympmqwryctalziacdrkuaouwpnyrogvslrvkwtyldxatuvavtwzghlcjdrmvkocbnlzmpctcjqzcgieeevankgwpltjizarhvusncppcnizrgknhqigjgvafkdlfbnifzgwsnpiuaroejqbtortuitqzkwdusgeetqdxoxdiojqcejqrocmlyirbggfotvujllgfjlhgs...

output:

572

result:

ok single line: '572'

Test #24:

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

input:

511
ifiiieiihihihiigfghhhifiigghhiiiihifiihhiiiiihehihiieiieiighhigigighihhiiedhihidgiiiiiighgigiiiighghgiicihhhhiiihiihfggihiiihhheigighhifihiighihhfiiihgiigiiiihifhiiigiihhgiigiificiihibifgghhhihgihhifiihfhidghiiihihihhhihiiiihihihfhiihiieiigihhhghahhiiigiihgiihhihfdhheigihhifhhghfiiiihifiihiiiiii...

output:

342

result:

ok single line: '342'

Test #25:

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

input:

630
lhgyfhveuevynekxrpdznfjptsajghiqzsonmxktelvxbmfzwkdxsuzaoavxivezsryqnbfhslsrsroplapvvoazujudfatzoijkelxdprhkktlfzwoohzqszjmmrfyofcqahavmluplqoocffxesjmduxgnmdevhhuksfkoompcaagujirfscajkbenarpidfzoproxbgkmvnvsqlixxtmhxtujoixjjonfiojriyrdqbeewcblvnahqxlolacawirgwzpryrbwpecwhxtwbsxnxzpedylwnzsthjsz...

output:

588

result:

ok single line: '588'

Test #26:

score: 0
Accepted
time: 14ms
memory: 3720kb

input:

511
hiighiigiiihfgiifighiiiigfiihfiihiiggihiiihihiiiighihghiiihciieihihgiiifiihgihihihiifihhiiiiihigiihiihhhgeiigfiigiihiiiiighihiehhifihihcihggiihhehhghididhiiiciifiihhieiihiiihhchhhhihhihhhbighiiiiighhiiihhdiggihiiieiiihgihigiegehiihiifhhiigigiiifiihiihiihfieghhiggigiighhhifidiigieiihiiifafgiiihig...

output:

364

result:

ok single line: '364'

Test #27:

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

input:

511
hhiiiiigiidiiihidihiihhehhigdihgiighiifiigiiifihiigfiighigiiiiihiiiheegihiiiggiiiiiiihghhiicigggigihihfhihgghgfiiigfhihihiifgiehfiihghehfhhhigihhhihfiggifihhiiihhgihihgighgihhhihhighiiiihfiigiifhhigiihigiihahieehhiihhifiihiifhfhhihhhiihhiiifhiihiiiiihhgigfihiheigfigiihiihifhihiiiiiihhhihhhiiihgi...

output:

476

result:

ok single line: '476'

Test #28:

score: 0
Accepted
time: 1ms
memory: 3768kb

input:

4
aabb
abba

output:

0

result:

ok single line: '0'