HW #8

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0)

int dif(string a , string b){
    int cnt = 0;
    for(int i = 0; i < a.size(); i++){
        cnt += a[i] != b[i];
    }
    return cnt;
}

int sum(int n){
    int s = 0;
    while(n){
        s += n % 10;
        n /= 10;
    }
    return s;
}

signed main()
{
    _FastIO;
    /*
    // A
    int n;
    string s;
    cin >> n >> s;
    int cnt = 0 , ans = 0;
    for(char i : s){
        if(i == 'I')
            cnt++;
        else
            cnt--;

        ans = max(ans , cnt);
    }

    cout << ans << '\n';
    */
    /*
    // B
    string s;
    cin >> s;
    int n = s.size() , a , z;
    for(int i = 0; i < n; i++){
        if(s[i] == 'A'){
            a = i;
            break;
        }
    }
    for(int i = n - 1; i >= 0; i--){
        if(s[i] == 'Z'){
            z = i;
            break;
        }
    }
    cout << z - a + 1 << '\n';
    //cout << s.rfind("Z") - s.find("A") + 1 << '\n';
    */
    /*
    // D
    int n;
    cin >> n;
    for(int i = 1; i <= 15; i++){
        int x = powl(i , i);

        if(x == n){
            cout << i << '\n';
            return 0;
        }
        //cout << x << '\n';
    }
    cout << -1 << '\n';
    */
    /*
    // E
    string s;
    cin >> s;
    int n = s.size();
    int ans = LLONG_MAX;
    for(int i = 0; i + 2 < n; i++){
        int x = stoll(s.substr(i , 3));
        ans = min(ans , abs(x - 753));
    }
    cout << ans << '\n';
    */
    /*
    // F
    int n , m , k , x;
    cin >> n >> m;
    map<int , int> cnt;
    for(int i = 0; i < n; i++){
        cin >> k;
        while(k--){
            cin >> x;
            cnt[x]++;
        }
    }
    int ans = 0;
    for(int i = 1; i <= m; i++){
        if(cnt[i] == n)
            ans++;

        //ans += cnt[i] == n;
    }

    //for(auto i : cnt){
    //    if(i.second == n)
    //        ans++;
    //}

    cout << ans << '\n';
    */

    /*
    18 7 8 12


    */
    /*
    // G
    int n , s , m , l;
    cin >> n >> s >> m >> l;
    int ans = LLONG_MAX;
    for(int i = 0; i <= 20; i++){ // 6
        for(int j = 0; j <= 20; j++){ // 8
            for(int k = 0; k <= 20; k++){ // 12
                int money = i * s + j * m + k * l;
                int eggs = i * 6 + j * 8 + k * 12;
                if(eggs >= n)
                    ans = min(ans , money);
            }
        }
    }
    cout << ans << '\n';
    */
    /*
    // H
    int n;
    cin >> n;
    int L[n + 1];
    L[0] = 2;
    L[1] = 1;
    for(int i = 2; i <= n; i++){
        L[i] = L[i - 1] + L[i - 2];
    }
    cout << L[n] << '\n';
    */
    /*
    // I
    int n , m;
    cin >> n >> m;
    char a[n + 5][m + 5];
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }

    for(int i = 0; i <= n + 1; i++){
        for(int j = 0; j <= m + 1; j++){
            if(!i || !j || i == n + 1 || j == m + 1)
                cout << "#";
            else
                cout << a[i][j];
        }
        cout << '\n';
    }
    */
    /*
    // J
    string a , b;
    cin >> a >> b;
    int n = a.size() , m = b.size();
    int ans = m;
    for(int i = 0; i + m - 1 < n; i++){
        ans = min(ans , dif(a.substr(i , m) , b));
    }
    cout << ans << '\n';
    */
    /*
    // K
    int n , a , b;
    cin >> n >> a >> b;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        // a <= x <= b
        int x = sum(i);
        if(a <= x && x <= b)
            ans += i;
    }
    cout << ans << '\n';
    */
    /*
    // L
    int n , d;
    cin >> n >> d;
    int x[n + 5][d + 5];
    for(int i = 0; i < n; i++){
        for(int k = 0; k < d; k++){
            cin >> x[i][k];
        }
    }
    // i < j
    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            int sum = 0;
            for(int k = 0; k < d; k++){
                sum += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
            }
            int sq = sqrtl(sum);
            if(sq * sq == sum)
                ans++;
        }
    }
    cout << ans << '\n';
    */
}