ABC122 D - We Like AGC

考えたこと：

1)メモ化再帰

2)包除原理で解く。

-> 2は厳しそう。

-> 重複が滅茶苦茶になりそう。

メモ化再帰で実装する。

どうやって？

dp[i][a][b]：＝i番目まで見ていて、i-2番目はa,i-1番目はbの時の数列の個数。

(ここで、A=0,B=1,C=2,T=3と対応させる。)

これを再帰関数rec(i,a,b)で解く。

ＮＧパターンは

ＡＧＣ、ＡＣＧ、ＧＡＣの３つなので

a=0,b=2のときはi番目はC=2以外の３パターン

(a=0,b=1),(a=2,b=0)のときも同様にする。

しかし・・・

サンプル２が合わない！！

２３３になる！

ここで1時間以上迷走をする・・・

なぜ？

サンプル１で合い、サンプル２で合わない理由。

４文字以上の文字列にのみ存在するＮＧパターンが存在するのでは？

ということに気付く。

上記３つのほかに、AXGC,AGXC　（Ｘ＝A,G,C,T)　の場合にもＮＧとなる。

なので、引数は４つ必要でrec(i,a,b,c)を解くことになる。

実装：

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int N;
int dp[110][5][5][5];

int rec(int n, int a, int b, int c) {
  if (n == N) return 1;
  if (dp[n][a][b][c] > 0) return dp[n][a][b][c];

  int res = 0;
  if (a == 0 && b == 2) {
    for (int i = 0; i < 4; i++) {
      if (i != 1) {
        res += rec(n + 1, b, c, i);
        res %= MOD;
      }
    }
  } else if (b == 2 && c == 0) {
    for (int i = 0; i < 4; i++) {
      if (i != 1) {
        res += rec(n + 1, b, c, i);
        res %= MOD;
      }
    }
  } else if (b == 0 && c == 2) {
    for (int i = 0; i < 4; i++) {
      if (i != 1) {
        res += rec(n + 1, b, c, i);
        res %= MOD;
      }
    }
  } else if (b == 0 && c == 1) {
    for (int i = 0; i < 4; i++) {
      if (i != 2) {
        res += rec(n + 1, b, c, i);
        res %= MOD;
      }
    }
  } else if (a == 0 && c == 2) {
    for (int i = 0; i < 4; i++) {
      if (i != 1) {
        res += rec(n + 1, b, c, i);
        res %= MOD;
      }
    }
  } else {
    for (int i = 0; i < 4; i++) {
      res += rec(n + 1, b, c, i);
      res %= MOD;
    }
  }

  return dp[n][a][b][c] = res;
}

signed main() {
  cin >> N;
  cout << rec(0, 3, 3 ,3) << endl;
  return 0;
}

答えは、NGに関係ない３文字の後ろにＮ文字を付けたとき、条件を満たす文字列は何個か？と考えてrec(0,3,3,3)などと答える。

これは　　ＴＴＴ（条件を満たすＮ文字の文字列）　の個数に等しい。

感想：

悔しいです。

全完したかった。

でもレートが上がったので良しとします。

AtCoder Beginner Contest 120

皆さま、お久しぶりです。

競プロを再開したいと思います。

C - Unification

考えたこと：

（これやったことあるんだけど忘れたので、もう一度解く・・・）

・再帰でいじる。

ー＞ダメ。計算が間に合わない。

・貪欲

ー＞前から順番に消せるなら消していく方法で大丈夫？

ー＞ダメ。計算が間に合わない。

理由：

...1111111110000000...のような並びだと

１周毎に２個しか減らないので最悪計算量Ｏ（Ｎ＾２）になる。

解法：

最終形を考えるとすぐに解けた。

最終的な形。すなわち、もうこれ以上キューブを取り除けない形はどうなっているか？

答え：（0または1のみ）または（全て消えている）形

ex)00000,111111

理由： 

0と1がともに存在すると仮定し、これ以上キューブを取り除けないとする。

この時、0と1が隣り合わせになる部分が少なくとも１つ存在する。

これはキューブがこれ以上取り除けないことに矛盾する。

（証明終了）

よって、取り除けるキューブの個数はmin(0の個数、1の個数）*２となる。

int main() {
  string s;
  cin >> s;
 
  int a = 0, b = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '0')
      a++;
    else
      b++;
  }
 
  cout << 2 * min(a, b) << endl;
  return 0;
}

D - Decayed Bridges

考えたこと：

・「便利さ」を行き来できる点の組の個数と定義する。

・橋が全てある時の、行き来できる点の組の個数は

Ｎコンビネーション２＝Ｎ＊（Ｎ－１）/ 2　（＝allとする）

（以後,calc(x)=x*(x-1)/2とする。）

であるから、「不便さ」＝all　-「便利さ」と表せる。

・「便利さ」＝　Σ calc(連結な点の集合の要素数)

で表せるため、「不便さ」を求めるよりも求めやすそう。

・便利さを求めるうえで、橋を削っていくよりも、無から橋を付け加えていく方が考えやすそう。

・連結な点の集合を管理するにはUnion-Find を使えば良さそう。

ー＞しかし、私のUnion-Findには要素数を返す関数は搭載されていない。

（以前、要素数をrank()にしてもいけると聞いたことがあったので、ちゃんと調べておけばよかったと後悔）

ー＞mapを使って、集合の親に対して集合の要素数を返すように管理すればいいのではないか？

これらのことを踏まえて、解答に移る。

・橋をＮ番目から１番目に向かって「追加」していく。

・点aと点bをつなぐ橋を追加するとき、

１）（点aと連結な集合Ａ）と（点bと連結な集合Ｂ）が連結でないとき

ＡとＢを　unite()　結合して集合Ｃとし、集合の要素数を管理するmapを変更する。

具体的に、

map[Ｃの親]＝map[Aの親]＋map[Bの親]　とする。

（ここでmap[集合の親]＝（集合の要素数）を表すことに注意すること。また、あらかじめmap[１～Ｎ]＝１と初期化しておくこと。）

２）ＡとＢが連結なとき

Ｃ内で橋を追加しただけなので、集合の要素数に変化はない。

これで集合の要素数の管理は順に出来るようになったが、このままではＭ回、全頂点Ｎ個を調べることになってしまい計算量Ｏ（ＭＮ）。間に合わない。

しかし、よくよく考えると橋を追加したときに、便利さに変化があるのは

集合の要素数が変化した部分のみであるから、頂点aと頂点bに関係する部分だけを考えて、１つ前の便利さから変化させればよい。

ここで、便利さをsubとすると、

２）のときsubに変化はない。

１）のときsub += calc(Cの要素数) - (calc(Aの要素数)+calc(Bの要素数))

となる。これは、ＡとＢの２つの集合から、Ｃという１つの集合に変化したときの便利さの差分を足している。

以上から、便利さを求める計算量は　Ｏ（log N)

（mapの使用がネックになっている）

よって全体計算量はO(M log N) <= 5*10^5となり間に合う。

解法：

struct UnionFind {
  vector<int> par;
  vector<int> rank;

  UnionFind(int n = 1) {
    init(n);
  }

  void init(int n = 1) {
    par.resize(n);
    rank.resize(n);
    for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0;
  }

  int root(int x) {
    if (par[x] == x) {
      return x;
    } else {
      int r = root(par[x]);
      return par[x] = r;
    }
  }

  bool same(int x, int y) {
    return root(x) == root(y);
  }

  bool unit(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return false;
    if (rank[x] < rank[y]) swap(x, y);
    if (rank[x] == rank[y]) ++rank[x];
    par[y] = x;
    return true;
  }
};

int N, M;
vector<P> query;
vector<int> ans;
UnionFind uf(101010);
map<int, int> mp;

int calc(int x) {
  return x * (x - 1) / 2;
}

signed main() {
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    query.push_back(P(a, b));
  }

  reverse(ALL(query));

  for (int i = 0; i < N; i++) mp[i] = 1;

  int sub = 0;
  for (int i = 0; i < M; i++) {
    P p = query[i];
    int a = p.first, b = p.second;

    if (!uf.same(a, b)) {
      int x = mp[uf.root(a)], y = mp[uf.root(b)];
      uf.unit(a, b);
      mp[uf.root(a)] = x + y;

      sub += calc(x + y) - calc(x) - calc(y);
      ans.pb(calc(N) - sub);
    } else {
      int x = mp[uf.root(a)];
      uf.unit(a, b);
      mp[uf.root(a)] = x;

      ans.push_back(calc(N) - sub);
    }
  }

  reverse(ALL(ans));

  for (int i = 1; i < M; i++) cout << ans[i] << endl;
  cout << calc(N) << endl;
  return 0;
}

感想：

無事全完できて良かったです。

ＢとＣはもう少し速く解きたかったですね。

AISing Programming Contest 2019 C - Alternating Path

考えたこと：

・メモ化再帰

ー＞重複が取り除けない・・・

ー＞偶奇で場合分けしたりするのだるすぎる・・・

・数え上げていく

ー＞これも微妙・・・

・組み合わせの計算に持ち込む。

ー＞どうやって？

左端上の点を固定して考えようとしていましたが、これが間違いでした・・・

実験をしていくと・・・

・考えればいいのは、白黒が交互に並ぶ部分だけ。（この部分を連結な部分と呼ぶことにする。）

・連結部の白の個数と黒の個数がわかれば、スタート点とゴール点の個数が決まる。

・任意のスタート点からゴール点へ移動することができる。（理由：連結）

これらを踏まえて、連結部分のもとめる点の組の個数は、

黒点の数　＊　白点の数　に等しい。

また、各点において訪れたかどうかの判定をbool vis[]などで記録しておけば、各点を訪れる回数は高々一回。

ゆえに　計算量はＯ（Ｈ＊Ｗ）

実装：

#include <bits/stdc++.h>
using namespace std;
#define int long long

int H, W;
string s[410];
bool vis[410][410];

int dx[] = {-1, 0 ,0 ,1};
int dy[] = {0, -1, 1, 0};

int x = 0, y = 0;

void rec(int h, int w) {
  if (vis[h][w] == true) return;
  vis[h][w] = true;
  for (int i = 0; i < 4; i++) {
    int ny = h + dy[i], nx = w + dx[i];
    if (ny >= H || ny < 0 || nx >= W || nx < 0 || vis[ny][nx] || s[ny][nx] == s[h][w]) continue;
    rec(ny, nx);
  }

  if (s[h][w] == '.') {
    x++;
  } else {
    y++;
  }
  return;
}

signed main() {
  cin >> H >> W;
  for (int i = 0; i < H; i++) {
    cin >> s[i];
  }

  int ans = 0;
  for (int h = 0; h < H; h++) {
    for (int j = 0; j < W; j++) {
      rec(h, j);
      ans += x * y;
      x = 0;
      y = 0;
    }
  }

  cout << ans << endl;
  return 0;
}

xが黒点の個数、yが白点の個数で、グローバル変数で持たせた。

（お行儀が悪い。）

連結部分ごとに考えるので、x=y=0を忘れないよう注意。

CADDi 2018 for Beginners

A:12/22

解法：

各桁毎にチェックしていく。

整数Ｎの１桁目はＮ％１０に等しい。

２桁目は（Ｎ／１０）％１０に等しい。以下同様

whileで実装する。

（わからない場合は確かめてみると良い）

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
  int n;
  cin >> n;

  int cont = 0;
  while (n > 0) {
    int tmp = n % 10;
    if (tmp == 2) cont++;
    n /= 10;
  }

  cout << cont << endl;
  return 0;
}

B:AtCoder Alloy

解法：

ある金属板(縦a横b)から縦Ｈ横Ｗの板を取り出せる条件は、

a>=H && b>=W　に他ならない。

この条件をみたすとき、回数を１増やせばよい。

#include <bits/stdc++.h>
using namespace std;
#define int long long

int N, H, W;

signed main() {
  cin >> N >> H >> W;

  int cont = 0;
  for (int i = 0; i < N; i++) {
    int a, b;
    cin >> a >> b;

    if (a >= H && b >= W) cont++;
  }

  cout << cont << endl;
  return 0;
}

C:Product and GCD

考えたこと：

・まずPを素因数分解しないと話が始まらない。

ー＞ライブラリを貼る。

（持っていない場合はどんどん増やしていくと良いと思います。）

・P<=10^12といえども、素因数分解をして出てくる素因数の個数は高々４０個

ー＞理由：１０＾１２＜２＾４０

・前から順に公約数を取りながら回せばいいのだけれど、a[n]の全探索は無理そう。

解法：

求める最大個約数を「最大公約数」と呼ぶ。（厳密には最大の最大公約数なのだけれども）

・a[0~n-1]の最大公約数の素因数にXが含まれるための条件はなにか？

それは、Pが素因数Xをｎ個持っていること！

Pの素因数になりうる候補は、１から√Pまで。

なので、前から全探索をして、素因数の個数がｎ個以上であれば最大公約数はXを素因数にもつ！

といいたいところなのだけれども！

注意すべき点が二つある！

一つ目：Pの素因数の候補にPも含まれるということ！

（この場合はN=１の場合だけ見てあげればいい）

二つ目：素因数の個数がｎ＊ｋ個（ｋは１以上の整数）ある場合、最大公約数の素因数もXをｋ個含めてあげられるということ。すなわち最大公約数はX＾ｋを素因数にもつ。

#include <bits/stdc++.h>
using namespace std;
#define int long long

int N, p;

//Ｏ(√n)
//素因数分解
map<int, int> prime_factor(int n) {
  map<int, int> res; // map[i]:=ｎを素因数分解したときiは何乗か。
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) {
        res[i]++;
        n /= i;
      }
    }
  }
  if (n != 1)
    res[n] = 1;
  return res;
}

signed main() {
  cin >> N >> p;
  if (N == 1) {
    cout << p << endl;
    return 0;
  }

  map<int, int> mp = prime_factor(p);

  int ans = 1;
  for (int i = 2; i * i <= p; i++) {
    if (mp[i] / N > 0) ans *= pow(i, mp[i] / N);
  }

  cout << ans << endl;
  retu

D:Harlequin

・本番では嘘解法で通した。（下に載せています）

・実験をして規則をみるタイプの問題でした。

問題のキモとしては、

・すべてのa[i]が偶数の時。

ー＞どのように食べても、奇数個のリンゴが１つ以上出来る。

・１つ以上、奇数のa[i]があるとき。

ー＞奇数のa[i]をすべて１つずつ食べるようにすれば、相手に渡せるリンゴの個数a[i]は全て偶数となる。

なので、初めの状態で少なくとも１つ奇数のa[i]があるとき、先手は常に、後手に「すべてのリンゴの個数a[i]を偶数にした状態」で手番を渡せます。

リンゴの個数は毎ターン単調減少するので、いつかこのゲームは終わります。

ゲーム終了の合図はa[i]が全て０になることですが、これは全て偶数の状態です。

以上から、少なくとも１つ奇数があるとき、先手は全偶数状態を押し付け続けることができるので先手が勝ちます。

逆にすべて偶数の時は、先手は後手に奇数が少なくとも１つある状態で手番を渡してしまうので、同様に考えると（この瞬間からゲームが始まったと考えると）後手が勝ちます。

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
  int N;
  cin >> N;

  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    if (a % 2 == 1) {
      cout << "first" << endl;
      return 0;
    }
  }

  cout << "second" << endl;
  return 0;
}

 すみません！！！！！

ここから下のDの解法は嘘解法です！

このブログはここで終わりになります！！

嘘解法を見たい方のみどうぞ！

D:Harlequin

初めに思ったこと：

・grundy数を使う。

・アドホックな解法がある。

・規則性が存在する。

・前からDPしていく。（前の結果が使える。）

ー＞これはなさそう、a<=10^9,n<=10^5　デカすぎる。

解法：

用いたのはgrundy数を使う方法。

a[i]はsortしておく。（二部探索を使うので）（というか、できるのならばしておいて損はない）

・縦からa[i]の列を縦に並べる。xはリンゴ

　　1234567

a[0]  x

a[1]  xxx

a[2]  xxxxxx

a[3]  xxxxxxx

....

このとき、縦には取れるだけとれるので、縦の石の列をNimの石の山と見た。

具体的には、

・(i=0から順番に）リンゴがa[i]個以上ある縦の列の個数を求める。これをcont[i]とする。

ー＞これはlower_boundで求まる。O（N lon N)

次にgrundy数を求めていく。

a[i]の大きさによってまとめて計算していく。

具体的にはset<int>stにa[i]を挿入していき、すでに挿入されていればcontinueする。

・i=0のとき

リンゴの数がa[0]以上となる列の個数はcont[0]個である、このような列がa[0]個横に並ぶので、for(int i=0;i<a[0];i++)grundy^=cont[0];とすればよいのだが、これだと明らかに間に合わない。

xor演算においてx^x^x=xとなる性質を用いると、a[i]が奇数ならばgrundy^=cont[0]とし、偶数ならばcont[0]同士で打ち消しあうので、何もしなくてよい。

よって、

if(a[i]%2)grundy^=cont[0];

・i>0のとき

上と同様に考えるが、もしもa[i]と同じ値がa[j](i>j)に存在すればcontinue

ー＞何故なら、このような場合の処理は（a[i]個横にならんでいるので・・・）のくだりでまとめてされているから。

・continueされなかった場合。

i=0のときと同じように考えるが、注意すべき点は、cont[i]以上となる列が横に並ぶ個数

はa[i]ではなく、a[i]-a[i-1]個であるということ。その他の点は同じ。

よって、if((a[i]-a[i-1])%2)grundy^=cont[i];

これで値は求まった。

最後にgrundy=0ならばsecont

grundy!=0ならばfirstをする。

#include <bits/stdc++.h>
using namespace std;
#define int long long

#define EXIST(s, e) ((s).find(e) != (s).end())

int N;
int a[101010], cont[101010];
set<int> st;

signed main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }
  sort(a, a + N);

  for (int i = 0; i < N; i++) {
    cont[i] = (N - (int)(lower_bound(a, a + N, a[i]) - a));
  }

  int grundy = 0;
  for (int i = 0; i < N; i++) {
    if (st.find(a[i]) != st.end()) continue;

    if (i > 0) {
      if ((a[i] - a[i - 1]) % 2) grundy ^= cont[i];
    }
    if (i == 0) {
      if (a[i] % 2) grundy ^= cont[0];
    }

    st.insert(a[i]);
  }

  if (grundy != 0) {
    cout << "first" << endl;
  } else {
    cout << "second" << endl;
  }

  return 0;
}

感想：

C問題を１WA（コーナーケースを見落とした）

D問題を５WAした。（かなしい）

でも全完は全完！次も頑張ります！

AGC029 A - Irreversible operation

初めに思いついたこと：

・前からシミュレーション

->何往復もするのでかなりの計算量になる。（Ｎ＜＝１０＾５）

・反転数っぽい。

ー＞ＢＩＴか？

ー＞ダメ。ＡＧＣ－ＡでＢＩＴが出るわけない。（ぐっと我慢する）

（もっと楽な方法があるはず）

実験を進めていくと・・・

・どんな状態がきても、最終的な状態は

WW......WBB........B

みたいな感じになる。

こうでない場合、WBW or BWB　が存在するので最終状態にはなり得ない。

・なので、Ｗを左端に寄せていくことを考える。

ー＞Wどうしの相対的な位置を変えるのは無駄なので、一番左のＷから、左に詰めていく。

実装：

numは次にＷを詰める場所を表す。

#include <bits/stdc++.h>
using namespace std;

signed main() {
  string s;
  cin >> s;

  int sum = 0, num = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'W') {
      sum += i - num;
      num++;
    }
  }
  cout << sum << endl;
  return 0;
}

感想：

１０分かかった。５分で解きたかった。

全体としては１完でした。

実力不足です。精進します。

ABC115 D - Christmas

初めに思いついたこと：

・Ｎ＜＝５０と小さい。

・漸化式を用いて、ＮバーガーのＰとＢの総数と、ＮバーガーのＰの総数は表せる。

（前者をnum[N],後者をf[N]と表す。）

・後ろから数え上げればいいな。

ー＞シミュレーションか？

ー＞シミュレーションは厳しそう。

理由：後ろから見ていっても、構造が単純ではなさそうだから。

～～さらによく問題を読んでみると～～

・（レベル）Ｎバーガーをひとつの塊とみると、ＮバーガーはＮ－１バーガーで表せて、これが全てのＮについて言える。

なので・・・

・全てのＮバーガーについて、後ろからＸの位置までのＰの個数の求め方はＮ－１バーガーに含まれるＰの個数の情報で表せる。

これは再帰関数で表せそう！

具体的には：

nバーガーの後ろからpos番目までのＰの総数を、rec(n,pos)と表す。

このとき

(0)pos==０のとき0個

　n==０のとき、０バーガーより１個

(1)pos>=num[n-1]*2+2のとき

ｎバーガーを　B （[n-1]バーガー） P （[n-1]バーガー）  Bと表すと（以後、[n-1]とす)

posの位置は[n-1]を完全に二つとも含む。

また、左の[n-1]よりも左にはＢしかないので、ここから左にはＰは存在しない

よってrec(n,pos)=f[n-1]*2+1と表される。

(１は真ん中のＰ）

(2)pos>=num[n-1]+2のとき

[n-1]は一つだけ完全に含まれ、左の[n-1]は途中までふくまれる。

ここで、左の[n-1]がどれだけ含まれているか、すなわち後ろから何番目まで含まれているかをpos2と表すと、左の[n-1]の中のpos2までのＰの個数は

rec(n-1,pos2)と表される。（定義より）

よって、rec(n,pos)=rec(n-1,pos2)+f[n-1]+1と表される。

(ただし、pos2=pos-(num[n-1]+2))

(3) 上記以外のとき

右の[n-1]が中途半端に含まれ、真ん中のＰは含まれないため

右のバーガーがpos3まで含まれているとすると

rec(n,pos)=rec(n-1,pos3)と表される。

（ただし、pos3=pos-1)(右のＢを除いただけ）

以上をもとに再帰関数を組めばよい。

求める答えはrec(N,X)

#include <bits/stdc++.h>
using namespace std;
#define int long long

int N, X;
int f[100], num[100];

int rec(int n, int pos) {
  if (pos == 0) return 0;
  if (n == 0) return 1;

  if (pos >= 2 * num[n - 1] + 2) {
    return f[n];
  } else if (pos >= num[n - 1] + 2) {
    int tmp = pos - (num[n - 1] + 2);
    int res = f[n - 1] + 1 + rec(n - 1, tmp);
    return res;
  } else {
    int tmp = pos - 1;
    return rec(n - 1, tmp);
  }
}

signed main() {
  cin >> N >> X;

  f[0] = num[0] = 1;
  for (int i = 0; i < 50; i++) {
    f[i + 1] = 2 * f[i] + 1;
    num[i + 1] = 2 * num[i] + 3;
  }

  cout << rec(N, X) << endl;
  return 0;
}

反省：

今回はＤを２ＷＡしてしまいました・・・

一つは範囲外参照。

もう一つはn==0のときの再帰の処理（重要）です。

どちらも本質ではないので悔しいです。

ですが、全完できたのは成長かなと思います！

頑張ります！

ABC115 C - Christmas Eve

初めに思いついたこと：

・最小値だから二分探索では？？？（条件反射）

ー＞問題をよく見ると、そんな必要はない。

・Ｎ＝１０＾５だからsortして考えて良いな。

ー＞sortしたら尺取り法の要領で求まるのでは？

ー＞Ｋが決まっているから尺を取る必要もない。

ー＞左端を決めれば右端も自動的に決まる。

結果：

sortをして、右端に対して全探索をする。

計算量はsortがボトルネックになってＯ（N log N)

実装：

#include <bits/stdc++.h>
using namespace std;
#define int long long

int N, K;
int h[101010];

signed main() {
  cin >> N >> K;
  for (int i = 0; i < N; i++) cin >> h[i];

  sort(h, h + N);

  int ans = INF;
  for (int i = 0; i + K - 1 < N; i++) {
    int tmp = abs(h[i + K - 1] - h[i]);
    chmin(ans, tmp);
  }

  cout << ans << endl;
  return 0;
}