2016-12-04

POJ 2121 Inglish-Number Translator

POJ 文字列処理

問題

アルファベット表記された数字を英数字に変換して表示せよ。

やりかた

数字をthousand未満、thousandの桁、millionの桁に分けて各桁を英数字に直して、桁の数字をかけて足し合わせた。

以下ソース。

int main(int argc, char **argv){
  map<string, int> p;
  p["negative"] = -1; p["zero"] = 0; p["one"] = 1; p["two"] = 2;
  p["three"] = 3; p["four"] = 4; p["five"] = 5; p["six"] = 6;
  p["seven"] = 7; p["eight"] = 8; p["nine"] = 9; p["ten"] = 10;
  p["eleven"] = 11; p["twelve"] = 12; p["thirteen"] = 13; p["fourteen"] = 14;
  p["fifteen"] = 15; p["sixteen"] = 16; p["seventeen"] = 17; p["eighteen"] = 18; 
  p["nineteen"] = 19; 
  p["twenty"] = 20; p["thirty"] = 30; p["forty"] = 40; p["fifty"] = 50; 
  p["sixty"] = 60; p["seventy"] = 70; p["eighty"] = 80; p["ninety"] = 90; 
  p["hundred"] = 100; p["thousand"] = 1000; p["million"] = 1000000;


  char c[400];
  while(gets(c)){
    string s(c);
    if(s.empty()) break;
    stringstream ss(s);
    vector<string> v;
    while(ss >> s) v.push_back(s);
    reverse(ALL(v));
    
    //桁ごとに入力を割り振る
    vector<string> num[4];
    int digit = 0;
    for(int i = 0; i < v.size(); i++){
      if(v[i] == "hundred"		&& digit < 1) digit = 1;
      else if(v[i] == "thousand"	&& digit < 2) digit = 2;
      else if(v[i] == "million"		&& digit < 3) digit = 3;
      else num[digit].push_back(v[i]);
    }

    //各桁について数字を計算
    int ans = 0;
    int sign = 1;
    for(int i = 0; i < 4; i++){
      int base = 1, val = 0;
      for(int j = 0; j < num[i].size(); j++){
	if(p[num[i][j]] == -1) sign = -1;
	else if(p[num[i][j]] < 100){
	  val += base * p[num[i][j]];
	}else{
	  base = p[num[i][j]];
	}
      }
      if(i == 0) ans += val;      
      if(i == 1) ans += 100 * val;
      if(i == 2) ans += 1000 * val;
      if(i == 3) ans += 1000000 * val;
    }
    cout << sign * ans << endl;
  }
  return 0;
}

2016-12-02

POJ 1265 Area

POJ 幾何

問題

ロボットが2次元座標上で原点から出発して左回りに動いて再び原点に戻ってくる。動作は格子点から格子点への直線運動の繰り返しで行われ、毎回の移動量dx, dyが入力として与えられる。この一周の動作で囲われた領域の内部にある格子点の総数、動作した直線上の格子点の総数、領域の面積を求めよ。なおロボットは過去に自分が通過した線を交差したり、接触するような動作はしない。

やりかた

ある直線動作（線分）の上にある格子点数はgcd(dx, dy)+1で求まる。なので一連の動作全体では $\sum_i gcd(dx_i, dy_i)$ となる。
領域は多角形になるので多角形の面積は頂点の座標（位置ベクトル）が分かれば $\frac{1}{2}|\sum_i (x_iy_{i+1} - x_{i+1}y_i)|$ で求まる。（ただしi=M-1のときi+1は0にする）
辺上の格子点数と領域の面積がわかれば、領域内の格子点数についてはピックの定理からすぐ求まる。

以下ソース。

int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}
int main(int argc, char **argv){
  int N;
  scanf("%d", &N);
  for(int t = 1; t <= N; t++){
    int x[101], y[101];
    int M;
    scanf("%d", &M);
    for(int i = 0; i < M; i++) scanf("%d %d", &x[i], &y[i]);

    int E = 0;
    double A = 0.0;
    for(int i = 0; i < M; i++) E += gcd(abs(x[i]), abs(y[i]));
    for(int i = 1; i < M; i++) x[i] += x[i - 1], y[i] += y[i - 1];//方向ベクトルから位置ベクトルに変換
    for(int i = 0; i < M; i++)
      A += 0.5 * (x[i] * y[(i + 1) % M] - y[i] * x[(i + 1) % M]);
    A = fabs(A);
    printf("Scenario #%d:\n", t);
    printf("%d %d %.1f\n\n", (int)(A + 1 - 0.5 * E), E, A);
  }
  return 0;
}

2016-12-01

POJ 2537 Tight words

POJ DP 確率

問題

[0...k](0<= k <= 9)の文字を使って長さnの文字列を作る。隣り合った文字の差がすべて1以下であるとき、その文字列をtightという。全文字列中のうちのtightな文字列の割合を百分率で求めよ。

やりかた

DP。
dp[i][j]:=（長さiの文字列で最後の文字がjであるようなtightな文字列が発生する割合（百分率））とする。dpでtightな文字列の総パターン数を求めて(k+1)^nで割ることもできるが、C++では多倍長整数を使わないとできないのでここでは割合のまま計算した。

以下ソース。

double dp[101][10];
int main(int argc, char **argv){
  int k, n;
  while(scanf("%d %d", &k, &n) != EOF){
    FILL(dp, 0);
    for(int i = 0; i < 10; i++) dp[1][i] = 100;
    for(int i = 1; i < n; i++){
      for(int j = 0; j <= k; j++){
	if(j - 1 >= 0) dp[i + 1][j] += dp[i][j - 1] / (k + 1);
	if(j + 1 <= k) dp[i + 1][j] += dp[i][j + 1] / (k + 1);
	dp[i + 1][j] += dp[i][j] / (k + 1);
      }
    }
    double ans = 0;
    for(int i = 0; i <= k; i++) ans += dp[n][i];
    printf("%.5f\n", ans / (k + 1));
  }
  return 0;
}

2016-11-27

POJ 2954 Triangle

POJ 整数問題

問題

3つの格子点の座標が与えられる。この格子点からなる三角形の内部にある格子点数を求めよ。ただし、辺上の格子点は数えない。また、与えられる三角形の面積は必ず0より大きい。

やりかた

ピックの定理を使った。

（ピックの定理）
頂点がすべて格子点上にあるような多角形の面積Sは、多角形内部（辺上を除く）にある格子点数をa、辺上にある格子点数をbとした時、以下の式で求められる。
$S = a + \frac{1}{2}b - 1$

以下ソース。

int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); }

int main(int argc, char **argv){
  int x1, y1, x2, y2, x3, y3;
  while(cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3){
    if(x1 == 0 && y1 == 0 && x2 == 0 && y2 == 0 && x3 == 0 & y3 == 0) break;
    //辺上の格子点数
    int b = gcd(abs(x1 - x2), abs(y1 - y2)) + gcd(abs(x2 - x3), abs(y2 - y3)) + gcd(abs(x3 - x1), abs(y3 - y1));
    int S2 = abs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1));
    cout << (S2 + 2 - b) / 2 << endl;
  }
  return 0;
}

2016-11-16

POJ 2295 A DP Problem

POJ 文字列処理

問題

'x'を変数とする1次方程式が文字列形式で与えられる。この方程式をxについて解き、解を床関数にかけたものを出力せよ。ただし解が不定の場合は"IDENTITY"を、不能の場合は"IMPOSSIBLE"を出力せよ。なお入力文字列は空白を含まない。

やりかた

単にやるだけで、方程式を左辺と右辺に分け、左辺のxの係数と定数、右辺のxの係数と定数をそれぞれ求めて、最終的に解を求めた。

以下ソース。

void strReplace(string &str, const string &from, const string &to){
  string::size_type pos = 0;
  while((pos = str.find(from, pos)) != string::npos){
    str.replace(pos, from.length(), to);
    pos += to.length();
  }
}

int s2i(string s){
  stringstream ss(s);
  int x; ss >> x; return x;
}

void proc(string s, int &coef, int &cons){
  stringstream ss(s);
  string tmp;
  while(ss >> tmp){
    if(tmp[tmp.size() - 1] == 'x'){
      if(tmp == "x") coef += 1;
      else if(tmp == "-x") coef += -1;
      else coef += s2i(tmp.substr(0, tmp.size() - 1));
    }
    else cons += s2i(tmp);
  }
  return;
}

int main(int argc, char **argv){
  int t; cin >> t;
  while(t--){
    string s;
    cin >> s;
    strReplace(s, "=", " ");
    stringstream ss(s);

    //式を左辺と右辺にわける
    string l, r;
    ss >> l >> r; 

    //項ごとに空白を入れて分けておく
    strReplace(l, "-", " -");
    strReplace(l, "+", " ");
    strReplace(r, "-", " -");
    strReplace(r, "+", " ");

    int lcoef = 0, lcons = 0, rcoef = 0, rcons = 0;
    proc(l, lcoef, lcons);
    proc(r, rcoef, rcons);

    if(lcoef == rcoef)
      cout << (lcons == rcons ? "IDENTITY" : "IMPOSSIBLE") << endl;
    else
      cout << (int)floor((rcons - lcons) * 1.0 / (lcoef - rcoef)) << endl;
  }
  return 0;
}

xを含む項の係数を求めるとき、xと-xが例外的な表記になるので注意。といっても何も難しくないけど。

2016-11-14

POJ 2005 Blackjack

POJ

問題

トランプがnセット（1セットあたりジョーカーなしの52枚）与えられ、このカードデッキを使ってブラックジャックを行う。
この中からディーラーが1枚、あなたが2枚をランダムにピックアップし、場にお互いが見えるように置く。ディーラーがランダムにもう1枚引いたときにあなたが勝つ確率を求めよ。

やりかた

自分の得点はすぐ計算できる。その際にAを11として加算しても21より大きくならないならそうする。
ディーラーの得点は最初に引いたディーラーのカードがAか否かで場合分け。場合分けした上で各場合についてディーラーが引いた場合に負けとなるカードの総枚数（自分の勝ちパターン数）を計算し、ディーラーが引きうるカードの総数n * 52 - 3（全パターン数）で割れば割合となる。

以下ソース。

int p(char c){
  if(c == 'A') return 1;
  else if(isdigit(c)) return (int)(c - '0');
  else return 10;
}
int num(char c){
  if(c == 'A') return 1;
  if(c == 'K') return 13;
  if(c == 'Q') return 12;
  if(c == 'J') return 11;
  if(c == 'T') return 10;
  return (int)(c - '0');
}
int main(int argc, char **argv){
  int card[14];
  int n;
  while(cin >> n, n){
    if(n == 0) break;
    for(int i = 1; i <= 13; i++) card[i] = 4 * n;

    int dealer = 0, me = 0;
    char a, b, c;
    cin >> a >> b >> c;
    card[num(a)]--;
    card[num(b)]--;
    card[num(c)]--;
    
    me = p(b) + p(c);
    if(b == 'A' || c == 'A') me = (me + 10 <= 21) ? me + 10 : me;

    int chance = 0;
    if(a == 'A'){//ディーラーは最初にAを引いた
      for(int i = 1; i <= 13; i++){
	if(i == 1){//ディーラーは2枚目にAを引くケース
	  dealer = 12;
	  if(dealer < me && me <= 21) chance += card[i];
	}else{//ディーラーは2枚目にA以外をを引くケース
	  dealer = min(10, i) + 11;
	  if(dealer > 21) dealer -= 10;
	  if(dealer < me && me <= 21) chance += card[i];
	}
      }
      printf("%.3f\%\n\n", chance * 100.0 / (n * 52 - 3));
    }else{//ディーラーは最初にAではないカードを引いた
      for(int i = 1; i <= 13; i++){
	dealer = p(a);
	if(i == 1){//ディーラーは2枚目にAを引くケース
	  dealer += 11;
	  if(dealer > 21) dealer -= 10;
	  if(dealer < me && me <= 21) chance += card[i];
	}else{//ディーラーは2枚目にA以外を引くケース
	  dealer += min(i, 10);
	  if((dealer > 21 && me <= 21) || (dealer < me && me <= 21))
	    chance += card[i];
	}
      }
      printf("%.3f\%\n\n", chance * 100.0 / (n * 52 - 3));      
    }
  }
  return 0;
}

場合分けはもう少し削れるはず。

2016-11-13

POJ 2418 Hardwood Species

POJ

問題

木の名前がいくつか入力される。各木の種類について、それが入力された総数のうち何%を占めているか木の名前のアルファベット順にパーセンテージで出力せよ。

やりかた

mapに木の名前と出現数を入れて総数で割って、、、というだけ。入力はgetsを使えば余裕で通る。

以下ソース。

int main(int argc, char **argv){
  char tree[256];
  map<string, int> p;
  int num = 0;
  while(gets(tree)){
    p[string(tree)]++;
    num++;
  }
  map<string, int>::iterator it = p.begin();
  for(; it != p.end(); it++)
    printf("%s %.4f\n", (it->first).c_str(), it->second * 100.0 / num);
  return 0;
}

atetubouさんによればgetlineでも通ったそうです。
PKU 2418 Hardwood Species - 日記