接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

AtCoder Beginner Contest 308（ABC308）

AtCoderBeginnerContest AtCoderBeginnerContest308 ABC ABC308

atcoder.jp

A - New Scheme

問題文の条件を判定する

提出コード

void solve() {
    vector<int> S(8);
    REP(i, 8) cin >> S[i];
    bool ok = true;
    REP(i, 8) if (!(100 <= S[i] and S[i] <= 675)) ok = false;
    REP(i, 8) if (S[i] % 25 != 0) ok = false;
    REP(i, 7) if (S[i] > S[i + 1]) ok = false;
    cout << (ok ? "Yes" : "No") << endl;
}

B - Default Price

mapなどで色に対応する値段を管理する

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<string> C(N), D(M);
    vector<int> P(M + 1);
    REP(i, N) cin >> C[i];
    REP(i, M) cin >> D[i];
    REP(i, M + 1) cin >> P[i];
    map<string, int> mp;
    REP(i, M) mp[D[i]] = P[i + 1];
    ll ans = 0;
    REP(i, N) {
        if (mp.count(C[i])) ans += mp[C[i]];
        else ans += P[0];
    }
    cout << ans << endl;
}

C - Standings

$ \frac{A_i}{A_i+B_i} \lt \frac{A_j} {A_j+B_j} $ の分母を払って $ A_i(A_j+B_j) \lt A_j(A_i+B_i) $ を比較関数にしてソートを行えば良い

提出コード

void solve() {
    int N;
    cin >> N;
    vector<ll> A(N), B(N);
    REP(i, N) cin >> A[i] >> B[i];
    vector<int> idx(N);
    iota(ALL(idx), 0);
    sort(ALL(idx), [&](int i, int j) {
        return A[i] * (A[j] + B[j]) == A[j] * (A[i] + B[i]) ? i < j : A[i] * (A[j] + B[j]) > A[j] * (A[i] + B[i]);
    });
    for (auto i : idx)
        cout << i + 1 << " ";
    cout << endl;
}

D - Snuke Maze

$ dist[i][h][w] := $ マス $ (h, w) $ にいて、その時の距離が $ i \pmod{5} $ であるときの最短距離としてBFSなどでこれを求める

提出コード

void solve() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    string snuke = "snuke";
    REP(i, H) cin >> S[i];
    vector dist(5, vector(H, vector(W, INF)));
    if (S[0][0] != 's') {
        cout << "No" << endl;
        return;
    }
    dist[0][0][0] = 0;
    using T = tuple<int, int, int>;
    queue<T> q;
    q.emplace(0, 0, 0);
    while (!q.empty()) {
        auto [d, h, w] = q.front();
        q.pop();
        REP(dd, 4) {
            int nh = h + dy[dd];
            int nw = w + dx[dd];
            if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
            int nxt_d = (d + 1) % 5;
            if (S[nh][nw] == snuke[nxt_d]) {
                if (dist[nxt_d][nh][nw] != INF) continue;
                q.emplace(nxt_d, nh, nw);
                dist[nxt_d][nh][nw] = dist[d][h][w] + 1;
            }
        }
    }
    bool ok = false;
    REP(i, 5) if (dist[i][H - 1][W - 1] < INF) ok = true;
    cout << (ok ? "Yes" : "No") << endl;
}

E - MEX

$ dp[i][j][k] := i $ 番目まで見て、MEXの $ j $ 文字目まで決めたときに選んだ集合が $ k $ であるときの場合の数としてDPを行う
最後に $ dp[N][3][k] \times MEX(k) $ の総和を求めてそれを出力する

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    string S;
    cin >> S;
    vector dp(N + 1, vector(4, vector(1 << 3, 0LL)));
    dp[0][0][0] = 1;
    string MEX = "MEX";
    REP(i, N) {
        REP(j, 4) {
            REP(k, 1 << 3) {
                dp[i + 1][j][k] += dp[i][j][k];
                if (j < 3 and S[i] == MEX[j]) {
                    dp[i + 1][j + 1][k | (1 << A[i])] += dp[i][j][k];
                }
            }
        }
    }
    ll ans = 0;
    REP(i, 1 << 3) {
        REP(j, 4) {
            if (!(i >> j & 1)) {
                {
                    ans += dp[N][3][i] * (ll)j;
                    break;
                }
            }
        }
    }
    cout << ans << endl;
}

F - Vouchers

買う値段を最小化したいので、$ D_i $ の大きい順に使っていくことを考える
このとき、 $ L_i $ を満たすギリギリのものを選びたいのでmultisetなどで集合を管理し、lower_boundでその値を求める

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> P(N), L(M), D(M);
    REP(i, N) cin >> P[i];
    REP(i, M) cin >> L[i];
    REP(i, M) cin >> D[i];
    sort(ALL(P));
    reverse(ALL(P));
    multiset<int> mst;
    priority_queue<pair<int, int>> pq;
    REP(i, N) mst.insert(P[i]);
    REP(i, M) pq.emplace(D[i], L[i]);
    ll ans = 0;
    while (!pq.empty()) {
        auto [d, l] = pq.top();
        pq.pop();
        auto it = mst.lower_bound(l);
        if (it == mst.end()) continue;
        ans += *it - d;
        mst.erase(it);
    }
    for (auto x : mst)
        ans += x;
    cout << ans << endl;
}

AtCoder Beginner Contest 306（ABC306）

AtCoderBeginnerContest AtCoderBeginnerContest306 ABC ABC306

atcoder.jp

A - Echo

$ S_i $ を2個ずつ出力する

提出コード

void solve() {
    int N;
    string S;
    cin >> N >> S;
    REP(i, N) cout << S[i] << S[i];
    cout << endl;
}

B - Base 2

問題文の通りに計算するだけだが、long long ではオーバーフローするので多倍長整数や unsigned long long を使う

提出コード

void solve() {
    unsigned ll ans = 0;
    REP(i, 64) {
        int a;
        cin >> a;
        if (a) ans += 1uLL << i;
    }
    cout << ans << endl;
}

C - Centers

$ A $ の2番目の要素でソートを行う

提出コード

void solve() {
    int N;
    cin >> N;
    vector<vector<int>> A(N);
    REP(i, 3 * N) {
        int a;
        cin >> a;
        --a;
        A[a].push_back(i);
    }
    vector<int> idx(N);
    iota(ALL(idx), 0);
    sort(ALL(idx), [&](int a, int b) { return A[a][1] < A[b][1]; });
    REP(i, N) cout << idx[i] + 1 << " \n"[i == N - 1];
}

D - Poisonous Full-Course

$ dp[i][j] := i $ 番目までの料理まで選択したときに、高橋くんの状態が $ j $ （お腹を壊しているかどうか）のときに得られた美味しさの和の最大としてDPを行う

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> X(N), Y(N);
    REP(i, N) cin >> X[i] >> Y[i];
    vector dp(2, -LINF);
    dp[0] = 0;
    REP(i, N) {
        vector ndp(2, -LINF);
        chmax(ndp[0], dp[0]);
        chmax(ndp[1], dp[1]);
        if (X[i] == 0) {
            chmax(ndp[0], dp[0] + Y[i]);
            chmax(ndp[0], dp[1] + Y[i]);
        }
        else {
            chmax(ndp[1], dp[0] + Y[i]);
        }
        swap(dp, ndp);
    }
    cout << max(dp[0], dp[1]) << endl;
}

E - Best Performances

BITでk-th elementの取得と、区間和を求めることで解くことができる
降順に $ k $ 番目の値は昇順に $ N - K $ 番目の値になるのでこの値を取得し、それ以降の区間和を求めればいい

提出コード

void solve() {
    int N, K, Q;
    cin >> N >> K >> Q;
    Compress<int> cmp;
    vector<int> A(N);
    vector<int> X(Q), Y(Q);
    REP(i, Q) {
        cin >> X[i] >> Y[i];
        cmp.add(Y[i]);
        --X[i];
    }
    cmp.add(0);
    cmp.add(2 * INF);
    cmp.build();
    int sz = cmp.size();
    BIT<ll> bit(sz), bit_sum(sz);
    bit.add(0, N);
    ll ans = 0;

    REP(i, Q) {
        int pre = A[X[i]];
        bit.add(cmp.get(pre), -1);
        bit_sum.add(cmp.get(pre), -pre);
        bit.add(cmp.get(Y[i]), 1);
        bit_sum.add(cmp.get(Y[i]), Y[i]);

        int k = bit.kth_element(N - K - 1) - 1;
        ll ans = 0;
        ans += bit_sum.sum(k + 1, sz);
        ans += max(0LL, (K - bit.sum(k + 1, sz))) * cmp[k];
        cout << ans << endl;
        A[X[i]] = Y[i];
    }
}

F - Merge Sets

各$ A _ i $ を昇順に並べ替える操作を予め行っておく
$ A _ {i , j } $ が $ A, B $ の集合の中で答えに寄与する分は、$ A $ の中で 自分より小さいものの個数と、$ B $ の中で自分より小さいものの個数になる
前者は $ j (N - i) $ として求めることができ、後者はBITなどで求めることができる
よって後者を実際に求め最後に前者の値を足した総和が答え

提出コード

void solve() {
    ll N, M;
    cin >> N >> M;
    vector<vector<int>> A(N, vector<int>(M, 0));
    Compress<int> cmp;
    REP(i, N) {
        REP(j, M) {
            cin >> A[i][j];
            cmp.add(A[i][j]);
        }
        sort(ALL(A[i]));
    }
    cmp.build();
    int sz = cmp.size();
    ll ans = 0;
    BIT<int> bit(sz);
    REP(i, N) REP(j, M) bit.add(cmp.get(A[i][j]), 1);
    REP(i, N) {
        REP(j, M) bit.add(cmp.get(A[i][j]), -1);
        REP(j, M) {
            ans += (j + 1) * (N - i - 1);
            ans += bit.sum(0, cmp.get(A[i][j]));
        }
    }
    cout << ans << endl;
}

接着剤の「CODINGAME SPRING CHALLENGE 2023」 参加記

CodinGame SPRING CHALLENGE 2023 ゲームAI

はじめに

CodinGameのコンテスト（CODINGAME SPRING CHALLENGE 2023)に参加しました
結果は世界82/5290位（Legend）、日本20/309位でした
🐜さん観察日記

ルール

例のごとくツカモさんの要約記事です（ありがとうございます）
tsukammo.hatenablog.com

やったこと

概要

方針：最初にある程度卵を集めて🐜を増やす、その後は距離順に最小シュタイナー木っぽくリソースマスをビーコンで繋いでいく
ルールベース + ダイクストラでの経路決め

BEACON

ビーコンの強さは1で固定
ダイクストラで求めた経路を復元し、経路上のマスにBEACONを設置

ダイクストラ

自分のベースとすでに設置したビーコンを始点としてダイクストラをする
(そのマスの蟻の総数 + 1）の逆数をコストとして最も近いリソースマスを貪欲に選ぶ
お気持ちとしては蟻が全くいない方向にビーコンを置くと移動に時間がかかるのですでに蟻がいる近くのリソースマスを狙うようにしたいため
選ぶリソースマスの総数は以下のルールベースで選択
現在の盤面に存在する卵のマスの個数を $ EggCells $、クリスタルのマスの個数を $ CrystalCells $ とする

  1. 取得した🐜の卵の総数が初期配置の🐜の卵の総数の15%未満の場合、最大 $ \lfloor \frac{EggCells}{2} \rfloor + 1 $ まで卵のマスを選択する
  2. 取得した🐜の卵の総数が初期配置の🐜の卵の総数の30%未満の場合、最大 $ \lfloor \frac{EggCells + CrystalCells}{2} \rfloor + 1 $ までマスを選択する、ただし卵のマスがある場合は卵のマスを優先して選び、残りをクリスタルのマスを選ぶ
  3. それ以外の場合、残っているマスの中から距離順に貪欲に選ぶ

マスを選ぶ際に相手始点でもダイクストラで各マスへの距離を求めておき、マス $ i $ の距離が $ OpponentDist[i] + 1 < MeDist[i] $ の場合は選択しない
境界付近のマスを除いて相手の方が近いマスは基本的には狙わないほうが良く、自分が取るべき個数（初期リソースマスの半分）+ 1個（中心に配置されているような自分と相手が争うマス）を取ることができれば勝てるため

やりたかったこと

・nターン後のスコア最大化（探索）
・ビーコンを上手く置いて🐜を賢く動かす（諦めた）

知見

焼きなまし（山登り）でビーコンの配置を最適化

感想

🐜の挙動を上手く動かすのが難しくてコンテスト期間中ずっと考えていたけど結局しっくりくる方法が思いつかず諦めた
シミュレートも書いたけど重すぎて結局使わなかったんだけどいい感じにシミュレートする方法あるのかな、気になる
とにかく何もわからなかったのでレジェンド行けて満足

おまけ（ブロンズ到達RTA）

やったこと

リソースのあるマスを全部LINEコマンドで選ぶ（サンプルコード+数行）

AtCoder Beginner Contest 301（ABC301）

AtCoderBeginnerContest AtCoderBeginnerContest301 ABC ABC301

atcoder.jp

A - Overall Winner

T と A の個数を数える
個数が同じ場合、最後に数えたものが負け

提出コード

void solve() {
    int N;
    string S;
    cin >> N >> S;
    bool f = false;
    int a = 0, t = 0;
    REP(i, N) {
        if (S[i] == 'T') {
            t++;
            f = true;
        }
        else {
            a++;
            f = false;
        }
    }
    if (a > t) cout << "A" << endl;
    else if (a < t) cout << "T" << endl;
    else {
        if (f) cout << "A" << endl;
        else cout << "T" << endl;
    }
}

B - Fill the Gaps

問題文の条件のとおりに出力をする

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    cout << A[0] << " ";
    REP(i, 1, N) {
        if (abs(A[i] - A[i - 1]) == 1) cout << A[i] << " ";
        else if (A[i] > A[i - 1]) {
            REP(j, A[i - 1] + 1, A[i] + 1) cout << j << " ";
        }
        else if (A[i] < A[i - 1]) {
            for (int j = A[i - 1] - 1; j >= A[i]; j--)
                cout << j << " ";
        }
    }
    cout << endl;
}

C - AtCoder Cards

各文字ごとに文字数を数え、SとTで文字数が同じかどうかを比較していく
このとき @はa, t, c, o, d, e, rに置き換えられるので足りない分は置き換えてしまっていい
SとTで文字数を同じにできない文字がある場合はNo、それ以外はYesとなる

提出コード

void solve() {
    string S, T;
    cin >> S >> T;
    vector<int> s(27), t(27);
    for (char c : S) {
        if (c == '@') s[26]++;
        else s[c - 'a']++;
    }
    for (char c : T) {
        if (c == '@') t[26]++;
        else t[c - 'a']++;
    }
    set<char> st = {'a', 't', 'c', 'o', 'd', 'e', 'r'};
    REP(i, 26) {
        if (s[i] == t[i]) continue;
        else if (!st.count(char(i + 'a'))) {
            cout << "No" << endl;
            return;
        }
        else if (s[i] > t[i]) {
            if (s[i] - t[i] > t[26]) {
                cout << "No" << endl;
                return;
            }
            else {
                t[26] -= s[i] - t[i];
            }
        }
        else if (s[i] < t[i]) {
            if (t[i] - s[i] > s[26]) {
                cout << "No" << endl;
                return;
            }
            else {
                s[26] -= t[i] - s[i];
            }
        }
    }
    cout << "Yes" << endl;
}

D - Bitmask

? を 0とした場合の2進数整数を予め求めておく
その後、上位bitから順に見ていき?を1としたときの2進数整数が $ N $ 以下の場合、そのbitは1としてしまって良い

提出コード

void solve() {
    string S;
    ll N;
    cin >> S >> N;
    ll cur = 0;
    reverse(ALL(S));
    REP(i, S.size()) if (S[i] == '1') cur += 1LL << i;
    if (cur > N) {
        cout << -1 << endl;
        return;
    }
    for (int i = (int)S.size() - 1; i >= 0; i--)
        if (S[i] == '?' and cur + (1LL << i) <= N) cur += 1LL << i;
    cout << cur << endl;
}

E - Pac-Takahashi

S, G, o のみに注目すると頂点数は高々20となり巡回セールスマン問題のようにbit DPで求めることができる
そのため、各頂点間の距離を予めBFSなどで求めておくことで以下のDPで答えを求めることができる
$ dp[i][j] := $ 最後に訪れた頂点が $ i $ で、訪れた頂点集合が $ j $ としたときの移動回数の最小
求めたい答えは、最後にGを訪れたときに移動回数が $ T $ 以下であるときの頂点集合に含まれる oの数の最大であるので条件を満たすもののうち、頂点集合に含まれる oの数の最大を求めればいい

提出コード

void solve() {
    int H, W, T;
    cin >> H >> W >> T;
    vector<string> s(H);
    REP(i, H) cin >> s[i];
    vector<pair<int, int>> snack;
    int sh, sw, gh, gw;
    REP(i, H) REP(j, W) {
        if (s[i][j] == 'S') sh = i, sw = j;
        else if (s[i][j] == 'G') gh = i, gw = j;
    }
    snack.emplace_back(sh, sw);
    snack.emplace_back(gh, gw);
    REP(i, H) REP(j, W) {
        if (s[i][j] == 'o') snack.emplace_back(i, j);
    }
    int n = snack.size();
    vector<vector<int>> dist(n, vector<int>(n, INF));
    REP(i, n) {
        auto [h, w] = snack[i];
        vector<vector<int>> d(H, vector<int>(W, INF));
        d[h][w] = 0;
        queue<pair<int, int>> q;
        q.emplace(h, w);
        while (!q.empty()) {
            auto [cur_h, cur_w] = q.front();
            q.pop();
            REP(dir, 4) {
                int nh = cur_h + dx[dir];
                int nw = cur_w + dy[dir];
                if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
                if (s[nh][nw] == '#') continue;
                if (d[nh][nw] < INF) continue;
                d[nh][nw] = d[cur_h][cur_w] + 1;
                q.emplace(nh, nw);
            }
        }
        REP(j, n) dist[i][j] = d[snack[j].first][snack[j].second];
    }
    vector dp(n, vector<int>(1 << n, INF));
    dp[0][0] = 0;
    dp[0][1] = 0;  // s = 0, g=1
    REP(i, 1, (1 << n) + 1) {
        REP(j, n) if (i >> j & 1) {
            REP(k, n) {
                int cost = dp[j][i ^ (1 << j)] + dist[j][k];
                chmin(dp[k][i], cost);
            }
        }
    }
    int ma = -1;
    REP(i, 1 << n) if ((i & 1) and (i >> 1 & 1) and dp[1][i] <= T) { chmax(ma, __builtin_popcount(i ^ 1 ^ 2)); }
    cout << ma << endl;
}

AtCoder Beginner Contest 298（ABC298）

AtCoderBeginnerContest AtCoderBeginnerContest298 ABC ABC298

atcoder.jp

A - Job Interview

o があるかどうかとxがあるかどうかをそれぞれ確認する

提出コード

void solve() {
    int N;
    string S;
    cin >> N >> S;
    bool ok1 = false;
    bool ok2 = true;
    REP(i, N) {
        if (S[i] == 'o') ok1 |= true;
        if (S[i] == 'x') ok2 = false;
    }
    cout << (ok1 and ok2 ? "Yes" : "No") << endl;
}

B - Coloring Matrix

4回回転させれば元に戻るので全探索する

提出コード

void solve() {
    int N;
    cin >> N;
    vector<vector<int>> A(N, vector<int>(N));
    auto B = A;
    REP(i, N) REP(j, N) cin >> A[i][j];
    REP(i, N) REP(j, N) cin >> B[i][j];
    REP(_, 4) {
        bool ok = true;
        REP(i, N) REP(j, N) {
            if (A[i][j] == 1 and B[i][j] == 0) ok = false;
        }
        if (ok) {
            cout << "Yes" << endl;
            return;
        }
        auto a = A;
        REP(i, N) REP(j, N) { A[i][j] = a[N - j - 1][i]; }
    }
    cout << "No" << endl;
}

C - Cards Query Problem

箱は重複を許すmultiset、数は重複なしのsetで管理する

提出コード

void solve() {
    int N, Q;
    cin >> N >> Q;
    vector<multiset<int>> hako(202020);
    vector<set<int>> number(202020);
    while (Q--) {
        int q;
        cin >> q;
        if (q == 1) {
            int i, j;
            cin >> i >> j;
            hako[j].emplace(i);
            number[i].emplace(j);
        }
        else if (q == 2) {
            int i;
            cin >> i;
            for (auto x : hako[i]) {
                cout << x << " ";
            }
            cout << endl;
        }
        else {
            int i;
            cin >> i;
            for (auto x : number[i]) {
                cout << x << " ";
            }
            cout << endl;
        }
    }
}

D - Writing a Numeral

先頭の要素取得と削除が可能なdequeで管理しながら追加、削除で差分計算をしていく
よく考えるとqueueでも良かった

提出コード

void solve() {
    int Q;
    cin >> Q;
    mint sum = 1;
    deque<int> dq;
    dq.push_front(1);
    while (Q--) {
        int q;
        cin >> q;
        if (q == 1) {
            int x;
            cin >> x;
            dq.push_back(x);
            sum = sum * 10 + x;
        }
        else if (q == 2) {
            int d = dq.size();
            int x = dq.front();
            dq.pop_front();
            sum = sum - modpow(mint(10), d - 1) * x;
        }
        else cout << sum << endl;
    }
}

E - Unfair Sugoroku

青木くんと高橋くんそれぞれ独立に考えていいので、以下のDPを求める
$ dp[i][j] := i $ 回目に地点 $ x $ にいる確率
高橋くんが $ i $ 回目に勝つ確率は、高橋くんが$ i $ 回目に地点 $ N $ にいる確率と青木くんが $ i - 1 $ 回目に地点 $ N $ 以外にいる確率との積になるのでその総和を求めればいい

提出コード

void solve() {
    int N, A, B, P, Q;
    cin >> N >> A >> B >> P >> Q;
    vector<vector<mint>> aoki(N + 1, vector<mint>(N + 1, 0));
    aoki[0][B] = 1;
    REP(k, N) {
        REP(i, N) REP(j, 1, Q + 1) {
            int to = (i + j > N ? N : i + j);
            aoki[k + 1][to] += aoki[k][i] / Q;
        }
    }
    vector<vector<mint>> takahashi(N + 1, vector<mint>(N + 1, 0));
    takahashi[0][A] = 1;
    REP(k, N) {
        REP(i, N) REP(j, 1, P + 1) {
            int to = (i + j > N ? N : i + j);
            takahashi[k + 1][to] += takahashi[k][i] / P;
        }
    }
    mint ans = 0;
    REP(i, 1, N + 1) {
        if (takahashi[i][N] == 0) continue;
        mint p = 0;
        REP(j, N) p += aoki[i - 1][j];
        ans += p * takahashi[i][N];
    }
    cout << ans << endl;
}

F - Rook Score

座圧をして平面走査を行う
$ r $ 行目の総和をセグメント木で管理し、その最大値を求める
$ w $ 列目の総和をそれぞれ求めながら重複する$ r $行目の差分計算を行い最大値を更新していく

提出コード

void solve() {
    int N;
    cin >> N;
    Compress<ll> cmp_h;
    vector<ll> h(N), w(N), x(N);
    REP(i, N) {
        cin >> h[i] >> w[i] >> x[i];
        cmp_h.add(h[i]);
    }
    cmp_h.build();
    int sz = cmp_h.size() + 1;
    map<ll, vector<LP>> mpw;
    vector<ll> h_val(sz + 1);
    REP(i, N) {
        mpw[w[i]].emplace_back(cmp_h.get(h[i]), x[i]);
        h_val[cmp_h.get(h[i])] += x[i];
    }
    ll ans = 0;
    segtree<ll, op, e> seg(h_val);
    for (auto [k, v] : mpw) {
        ll sum = 0;
        for (auto [h_idx, x] : v) {
            seg.set(h_idx, seg.get(h_idx) - x);
            sum += x;
        }
        chmax(ans, sum + seg.all_prod());
        for (auto [h_idx, x] : v) {
            seg.set(h_idx, seg.get(h_idx) + x);
        }
    }
    cout << ans << endl;
}