ferinの競プロ帳

競プロについてのメモ

CODE FESTIVAL 2016 Grand Final A - 1D Matching

問題ページ
A - 1D Matching

考えたこと

とりあえずNが小さいパターンを実験してみる。PCと電源をつなぐのをPCから電源への有向辺で表すとする。

下の図でオレンジ色のつなぎ方は最短なつなげ方ではない。最短なつなげ方にならないパターンを他にも試してみると、有向辺の向きが逆の辺が交差していると最短なつなげ方にならないことがわかる。交差しているところがあったらつなげる先を交換すればより短いつなげ方となることからもわかる。位置だけからもっとも短いつなげ方がわかるので重要なのは順番だけで座標の位置は気にしなくてよいことがわかる。
さらにいろいろ試していると交差がだめなことから、うまく区間を区切っていくと区間内のPCと電源しかつなげないことがわかる。つまり、区間ごとに独立に計算できる。PCが来たら+1、電源が来たら-1として累積和を取って0になった時点で区間を区切るとうまい区切り方になる。
この区間ごとに有向辺の向きはかならず一定になるのでこれをうまく使って何通りあるのか数える。次のように並んでいるときについて考える。今見ている場所まででつなげ方が何通りあるか、まだつなげていない電源が何個あるのかを保持しておくと下の表のように数えられる。更新は * 今見ているのが電源なら残りの電源数にその分プラス * 今見ているのがPCならC(残りの電源数, PC数) * (PC数)!を通り数に加える でできる。

電源,電源,電源,PC,PC,電源,PC,電源,PC,PC  
              電 PC 電 PC 電 PC
連続してる数  3  2  1  1  1  2
      何通り  1  6  6  12 12 24
残りの電源数  3  1  2  1  2  0

MODを取ることやオーバーフローに気をつけつつ実装すると通った。
もうちょっと素早く考察できるようになりたい。

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

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

int a[100010], b[100010], f[200010];

ll combi(ll N_, ll C_) {
    const int NUM_=400001;
    static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
    if (fact[0]==0) {
        inv[1]=fact[0]=factr[0]=1;
        for (int i=2;i<=NUM_;++i) inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
        for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%MOD, factr[i]=factr[i-1]*inv[i]%MOD;
    }
    if(C_<0 || C_>N_) return 0;
    return factr[C_]*fact[N_]%MOD*factr[N_-C_]%MOD;
}

signed main(void)
{
  int n;
    cin >> n;
    vector<PII> v;
    REP(i, n) cin >> a[i], v.PB({a[i], 0});
    REP(i, n) cin >> b[i], v.PB({b[i], 1});
    sort(ALL(v));

    f[0] = 1;
    FOR(i, 1, 2*n+1) (f[i] = f[i-1] * i) %= MOD;

    VI v2;
    int cnt = 1;
    FOR(i, 1, v.size()) {
        if(v[i].second == v[i-1].second) cnt++;
        else {
            v2.PB(cnt);
            cnt = 1;
        }
    }
    v2.PB(cnt);

    bool turn = true;
    int ret = 1; cnt = 0;
    for(int i: v2) {
        if(turn) {
            cnt += i;
        } else {
            if(cnt >= i) {
                // C(cnt, i) * i!
                (ret *= combi(cnt, i) * f[i] % MOD) %= MOD;
                cnt -= i;
            } else {
                (ret *= f[cnt]) %= MOD;
                cnt = i-cnt;
                turn = !turn;
            }
        }
        turn = !turn;
    }
    cout << ret % MOD << endl;

    return 0;
}

競プロはじめて1年が経った

技術的なことは書けないのでポエムを書きます。ferinという名前で競プロをやっていてAtcodercodeforcesで青の下の方、topcoderで緑の人です。

2016年11月

ミーハーなので流行りのディープラーニングに手を出してみる。どうやらPythonという言語がメジャーらしいのでPythonの勉強が必要になった。Pythonの勉強がてら競プロをはじめた。気づいたら競プロにハマっていて11月で60ACしていた。

Twitterを見ていたらコンテスト情報を見つけたのではじめてのコンテストAGC 007に参加した。終了5分前にBを通すことができ2完できてめちゃくちゃうれしかった。次の週にABC 048に出たら500点が発想よりだったおかげで解けて気づいたら25位でうれしかった。今思うと最初のコンテスト2回で大成功したのが競プロにハマった原因な気がする。

蟻本を買った。必要な知識は大体載っているし実装に困ったら写経できるようになって捗った。

12月

モチベが高かったのでひたすらにABCを解いていた。

SRMに初参加した。med落として灰スタートかなーと思ったら緑スタートで意外と優しかった。

2017年1月

ABC埋めを終わらせた。ほとんど解説を読んでいた気がするけどよく使うテクを一通り勉強できてよかった。日本語のわかりやすい解説は貴重。

エクセルでAC記録を取りはじめた。AC数駆動で精進していたのでAC数グラフとか作れたのが割とモチベになってよかった。

2,3月

春休みで暇人だったのでひたすら競プロをする人になっていた。yukicoderの☆2とかARC-A,BとかcodeforcesのバーチャルコンテストとかAOJICPCとかを埋めた結果2ヶ月で385ACしていた。

AtCoderで水色になれた。

4月

ICPCに参加している人がいるサークルが弊学にもあるらしいことを知って見に行ったりしていた。

AOJICPCを解いてた。150,200あたりの実装が重い系に苦労したり250のDP楽しいって言ってたりしたら20000ptになった。

5,6月

大学がはじまったらあんまり競プロができなくなってしまった。水色でレートがなかなか上がらなくなってきて厳しさを感じていた。ICPCの模擬国内でも3完で2時間近く座っていることになり冷えていた

埋めはAOJICPCの国内予選の問題を中心にやっていた。

7月

水色天井でレートが止まっていて一生ABC-Dが解けないという気持ちになっていた。

ICPCの国内予選があった。自分より強い後輩とチームで出たらBをバグらせ続ける戦犯をして国内突破できなくて申し訳ない気持ちになった。先輩チームが5位になっていてとても強かった。

8月

夏休みがはじまったのでひたすら競プロをする日々がはじまった。セグ木のライブラリをつくったりHackerrankのgametheory埋めをしたりJOI埋めをしたりSRMのd1E埋めをしたりしていた。

SRMではdiv2☀をしてレートが4桁を切って冷えた。
codeforcesでようやく青になれてうれしかった。
AtCoderで1561->1594->1597みたいなレート遷移をしていて早く青になりたいという気持ちしかなかった。

9月

一番多く問題を解いているAtCoderでようやく青くなれてめちゃくちゃうれしかった。

埋めはJOIの7とかSRMのd1Eを解いていた。
この時期にマラソンをはじめた。Chokudai Contestの過去問に2~3日かけて取り組んだり、topcoder education MMをやったりしていた。やってもやってもスコアが上がらないのにダメージを受けつつ焼きなましとかビームサーチの実装を覚えた。

JAG合宿に参加した。3時間セット+ボドゲ、5時間セット+こどふぇす予選、5時間セットと非常に濃い3日間でTLが現実に再現されていたのが面白かった。 ferin-tech.hatenablog.com

10,11月

毎週末のAtCoderくらいしか出ていなくてレートも停滞気味。

RCO勉強会に参加した。こどふぇすの裏で行われていた勉強会で交流をした。RCOの紹介を見てるととても楽しそうだった。無料の勉強会で🍣と🍖がでてきてRCO様々といった感じ。

12月

だめだろうなーと思ってたら予選ABの早解きが功を奏したらしくCODE THANKS FESTIVALにいけることになった。(登録情報を間違えてたけどリクルートさんにメールしたら対応してもらえた。ありがとうございます。) ferin-tech.hatenablog.com

AOJICPCの350~450あたりを主に埋めてた。

まとめ

基本的に飽きっぽい人間で1年も競プロモチベが高いまま維持されていたのはかなり奇跡的だと思っています。プログラムは好きだけど何か作りたいかと言われるとそういうわけでもなかったので競プロそのものが向いていたことだったり、Twitterの競プロコミュニティが好きで楽しかったりするおかげでここまで続けてこれたのかなと思います。競プロerのみなさんTwitterをやりましょう。

来年は黄色くなってICPCのアジアや各種オンサイトに行けるようにがんばっていきたい。

AOJ 2152 Restrictive Filesystem

問題ページ
Restrictive Filesystem | Aizu Online Judge

考えたこと

  • 10^9の配列確保して1つずつ記録していくのはメモリ的にも計算量的にも不可能なので座圧は必須そう
  • dp[i] = (j, k) (位置iからjまでkが記録されている)としてunordered_mapを使ってメモリを節約することを考える
  • 書き込みと削除と参照について場合分けするとそれぞれのクエリにO(N)で対応できそうでO(N^2)なら通る気持ちになったので実装をする
  • TLEが出てつらい気持ちになりながら†submitデバッグ†をするとバグがわかったので直すと通った

やらかしたバグ
* 必要な更新処理をわすれてた * dp[idx]をみないといけないのにdp[i]を見ていた
* 書き込みで値を更新するときにすでに値が入ってるときは書き込んじゃいけないのに書き込んだ

解法

  • 書き込み
    • dp[idx].second == -1 (何も記録されていない)
      • dp[idx].first まで書き込めば終わる
        必要な分の書き込みする
        dpの値の更新
      • 終わらない
        dp[idx].first まで目一杯書き込む
        idx = dp[idx].first
    • dp[idx].second != -1
      idx = dp[idx].first
  • 削除
    dpを全部なめて dp[idx].second が入力された値だったら -1 に変更
  • 参照
    (参照するindex) >= dp[idx].first になるまで idx = dp[idx].first + 1で更新
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif

unordered_map<int, PII> dp;
signed main(void)
{
  while(true) {
    int n;
    cin >> n;
    if(!n) break;

    dp.clear();
    dp[0] = {INF, -1};

    REP(i, n) {
      char c;
      cin >> c;
      int l, r;
      if(c == 'W') {
        cin >> l >> r;
        int idx = 0, cnt = r;
        while(true) {
          if(dp[idx].second == -1) {
            if(idx + cnt - 1 <= dp[idx].first) {
              if(dp.find(idx+cnt) == dp.end()) dp[idx+cnt] = {dp[idx].first, -1};
              dp[idx] = {idx+cnt-1, l};
              break;
            } else {
              dp[idx].second = l;
              cnt -= dp[idx].first - idx + 1;
            }
          }
          idx = dp[idx].first + 1;
        }
      } else if(c == 'D') {
        cin >> l;
        for(auto& j: dp) if(j.second.second == l) j.second.second = -1;
      } else if(c == 'R') {
        cin >> l;
        int idx = 0;
        while(true) {
          if(dp[idx].first >= l) {
            cout << dp[idx].second << endl;
            break;
          }
          idx = dp[idx].first + 1;
        }
      }
    }
    cout << endl;
  }

  return 0;
}

AtCoder Regular Contest 087 E - Prefix-free Game

問題ページ
E - Prefix-free Game

考えたこと

  • ゲームと言われたのでサンプルについてWin-Loseの探索木を書いてみるがよくわからない
  • 01文字列なのでtrie木を書いてみると葉を通らないような位置に頂点を追加する問題に言い換えられることがわかった
  • 木上のゲームでgrundy数っぽい感じがしたのでdeforestation を思い出すと同じgrundy数の定義でいける気持ちになったので書く
  • trieを書いたことがなかったので手間取っていると終了10分前になっている。サンプルを試すと落ちた。
  • trieをバグらせているのかとか色々確認してたらコンテスト終わった
    ----解説を見た----
  • trie書いてgrundy数まではあってたけどgrundy数の求め方が間違っていた
  • 冷静に考えると操作が別物だし何で同じgrundy数の求め方だと思ってしまったのか謎

学び

  • bitのTrie木(完全二分木)のライブラリをつくった
  • 解説放送を見たらgrundy数の問題は考えてどうにかなるものではないのでとにかく実験しろと言っていたので今度からそうする
  • それっぽい法則を見つけた気分になったときに合ってるか確かめずに実装に入っちゃうのを直す
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define PB push_back

/*
完全二分木
v[now].lch = v.size(); v.PB(node(v[now].d+1)); now = v[now].lch;  // 左に追加
v[now].rch = v.size(); v.PB(node(v[now].d+1)); now = v[now].rch;  // 右に追加
*/
struct node {
  int d, lch, rch;
  node() {lch=rch=d=-1;}
  node(int d):d(d){lch=rch=-1;}
};
vector<node> v;

int n, l, ans;
string s[100010];

signed main(void)
{
  cin >> n >> l;
  REP(i, n) cin >> s[i];

  v.PB(node(0));
  REP(i, n) {
    int now = 0;
    REP(j, s[i].size()) {
      if(s[i][j] == '0') {
        if(v[now].lch != -1) now = v[now].lch;
        else {
          v[now].lch = v.size();
          v.PB(node(v[now].d+1));
          now = v[now].lch;
        }
      } else {
        if(v[now].rch != -1) now = v[now].rch;
        else {
          v[now].rch = v.size();
          v.PB(node(v[now].d+1));
          now = v[now].rch;
        }
      }
    }
  }

  int ret = 0;
  for(auto i: v) {
    if(i.lch == -1 && i.rch == -1) continue;
    if(i.lch == -1 || i.rch == -1) ret ^= (l-i.d)&(i.d-l);
  }

  if(ret) cout << "Alice" << endl;
  else cout << "Bob" << endl;

  return 0;
}

AOJ 2536 Median Tree

問題ページ
Median Tree | Aizu Online Judge

考えたこと

  • コストが小さい辺をなるべく使っていきたい
  • 最小全域木を思い浮かべるけどコストが1の辺を使わずに2と3の辺を繋いだほうがいい場合があるのではみたいな気持ちになって捨てる(は?)
  • 謎の貪欲を投げたけど落ちるので人生終了
    ----解説を読む----
    MSTでよかったらしい

冷静になって考えると頂点2つをコスト1の辺でつなぐのと頂点3つをコスト2,3の辺でつなぐのを比較してるのが謎な気がした。貪欲で、
* ある状態での評価式
* 評価式で最善なものを選び続けたら最適解になる
を考えるときに、評価式で比較するもの(今回は小さいコストの辺の本数)以外を一致させないと変なのではという気がした。冷静に考えると対照実験でそれはそう。頂点数を固定したときにコストが小さい辺を増やそうとすると自然にMSTの発想が生える気持ちになった。

学び

MST Sと任意の全域木 Tについて、(Sのn番目のコスト) <= (Tのn番目のコスト)
証明で交換可能な辺の考え方何回か見たことある気がするので覚えておく
状態の比較をするときは比較するもの以外を一致させる

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

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

class UnionFind {
public:
  const static int MAX_N = 100010;
  int par[MAX_N];
  int rank[MAX_N];
  int s[MAX_N];
  bool used[MAX_N];
  UnionFind() { init(); }
  UnionFind(int n) { init(n); }
  void init() { for(int i=0; i<MAX_N; ++i) par[i] = i, rank[i] = 0, s[i] = 1; }
  void init(int n) { for(int i=0; i<n; ++i) par[i] = i, rank[i] = 0, s[i] = 1; }
  int find(int x) {
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(rank[x] < rank[y]) {
      par[x] = y; s[y] = s[x] + s[y];
    } else {
      par[y] = x; s[x] = s[x] + s[y];
      if( rank[x] == rank[y] ) rank[x]++;
    }
  }
  int size(int x) { return s[find(x)];}
  bool same(int x, int y) { return find(x) == find(y);}
  int group(int n) {
    REP(i, n) used[find(i)] = true;
    int ret = 0;
    REP(i, n) if(used[i]) ret++;
    return ret;
  }
};
UnionFind uf;

VI a[10010];
signed main(void)
{
  while(true) {
    int n, m;
    cin >> n >> m;
    if(!n) break;
    REP(i, m) {
      int x, y, z;
      cin >> x >> y >> z;
      x--, y--;
      a[i] = {z, x, y};
    }
    sort(a, a+m);
    if(n == 2) {
      cout << a[0][0] << endl;
      continue;
    }

    uf.init(n);
    VI v;
    REP(i, m) {
      if(!uf.same(a[i][1], a[i][2])) {
        v.PB(a[i][0]);
        uf.unite(a[i][1], a[i][2]);
      }
    }
    sort(ALL(v));
    cout << v[n/2-1] << endl;
  }

  return 0;
}

AOJ 1602 ICPC計算機

問題ページ
ICPC Calculator | Aizu Online Judge

解法

+か*が来たらその演算子で計算する範囲の数式を全部計算して返すような関数をつくってその関数を再帰的に呼び出していくことで計算する。ある演算子で計算する対象はその演算子より高さが1段高いものなのでそれより低いものが来たらその演算子の範囲は終了したと判定できる。n=1だと演算子が一つもないのに要注意。

再帰降下型の構文解析みたいな気持ちで考えたら実装どうやるかなんとなく決めれたけど細かい実装でindexバグらせたり<と<=間違えたりしていた。境界で混乱するときはちゃんと考えてから実装に移るべき。

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

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

string s[100];
pair<int, char> p[100];
int n;
int add(int&, int);
int mul(int&, int);

int add(int& idx, int par) {
  int ret = 0;
  while(idx < n) {
    if(p[idx].first <= par) {
      break;
    } else if(p[idx].second == '+') {
      idx++;
      ret += add(idx, p[idx-1].first);
    } else if(p[idx].second == '*') {
      idx++;
      ret += mul(idx, p[idx-1].first);
    } else {
      ret += p[idx].second - '0';
      idx++;
    }
  }
  return ret;
}

int mul(int &idx, int par) {
  int ret = 1;
  while(idx < n) {
    if(p[idx].first <= par) {
      break;
    } else if(p[idx].second == '+') {
      idx++;
      ret *= add(idx, p[idx-1].first);
    } else if(p[idx].second == '*') {
      idx++;
      ret *= mul(idx, p[idx-1].first);
    } else {
      ret *= p[idx].second - '0';
      idx++;
    }
  }
  return ret;
}

signed main(void)
{
  while(true) {
    cin >> n;
    if(!n) break;
    REP(i, n) cin >> s[i];

    REP(i, n) p[i].first = 0;
    REP(i, n) {
      REP(j, s[i].size()) {
        if(s[i][j] == '.') p[i].first++;
        else p[i].second = s[i][j];
      }
    }
    if(n == 1) {
      cout << p[0].second << endl;
      continue;
    }

    int ret;
    if(p[0].second == '+') {
      int st = 1;
      ret = add(st, 0);
    } else {
      int st = 1;
      ret = mul(st, 0);
    }

    cout << ret << endl;
  }

  return 0;
}

AOJ 2255 6/2(1+2)

問題ページ
6/2(1+2) | Aizu Online Judge

解法

構文解析をする。取りうる数字が一意には定まらないので候補全部をsetで持っておき、next_permutationで全通りを試す。括弧ごとに演算子と数字を全部列挙したあと、演算子の取りうる順番を全通り試してその括弧が取りうる数字を求める。

O(n^2n!)でテストケース厳しいとだめそうだけど通ったからセーフ(は?)

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

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

string s;

typedef string::const_iterator State;

set<int> factor(State& begin);
set<int> digit(State& begin);

set<int> expr(State& begin) {
  vector<char> op;
  vector<set<int>> num;
  while(begin != s.end() && *begin != ')') {
    if(*begin == '+') {
      op.PB('+'); begin++;
    } else if(*begin == '-') {
      op.PB('-'); begin++;
    } else if(*begin == '*') {
      op.PB('*'); begin++;
    } else if(*begin == '/') {
      op.PB('/'); begin++;
    } else if(*begin == '(') {
      num.PB(factor(begin));
    } else {
      num.PB(digit(begin));
    }
  }

  set<int> ret;
  VI per(op.size());
  REP(i, op.size()) per[i] = i;
  do {
    VI p(per);
    for(int i=per.size()-1; i>=0; --i) {
      int tmp = 0;
      REP(j, i) {
        if(p[j] < p[i]) tmp++;
      }
      p[i] -= tmp;
    }
    vector<set<int>> num2(num);
    REP(i, per.size()) {
      // p[i] と p[i]+1についての演算をする
      if(op[per[i]] == '+') {
        set<int> tmp;
        for(int j: num2[p[i]]) for(int k: num2[p[i]+1]) {
          tmp.insert(j+k);
        }
        num2[p[i]] = tmp;
        num2.erase(num2.begin()+p[i]+1);
      } else if(op[per[i]] == '-') {
        set<int> tmp;
        for(int j: num2[p[i]]) for(int k: num2[p[i]+1]) {
          tmp.insert(j-k);
        }
        num2[p[i]] = tmp;
        num2.erase(num2.begin()+p[i]+1);
      } else if(op[per[i]] == '*') {
        set<int> tmp;
        for(int j: num2[p[i]]) for(int k: num2[p[i]+1]) {
          tmp.insert(j*k);
        }
        num2[p[i]] = tmp;
        num2.erase(num2.begin()+p[i]+1);
      } else if(op[per[i]] == '/') {
        set<int> tmp;
        for(int j: num2[p[i]]) for(int k: num2[p[i]+1]) {
          if(k == 0) continue;
          tmp.insert(j/k);
        }
        num2[p[i]] = tmp;
        num2.erase(num2.begin()+p[i]+1);
      }
    }
    for(int i: num2[0]) ret.insert(i);
  } while(next_permutation(ALL(per)));
  return ret;
}

set<int> factor(State& begin) {
  begin++;
  set<int> ret = expr(begin);
  begin++;
  return ret;
}

set<int> digit(State& begin) {
  int ret = 0;
  while(isdigit(*begin)) {
    ret *= 10;
    ret += *begin - '0';
    begin++;
  }
  return {ret};
}

signed main(void)
{
  while(true) {
    cin >> s;
    if(s == "#") break;
    State begin = s.begin();
    set<int> ret = expr(begin);
    cout << ret.size() << endl;
  }

  return 0;
}