Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-15

SRM420 div2

23:38

Hard - PrettyPrintingProduct

Permutation(A, B)を表示する問題。出力は、"12345...67891 * 10^3"のようなフォーマットで行う。

とりあえず、string型で乗算を行う関数を実装して、パーミュテーションを計算し、整形して出力するという方法でいってみましたが、やはり大きな数字になるとTLEです。

Editorialをみてみると、正解者が5人でした。難しい問題のようです。詳しい解説は次回見ていきます。

class PrettyPrintingProduct {
public:
  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}

  string plus(string a, string b)
  {
    string ret;

    int i = 0;
    int up = 0;

    while (i < a.size() || i < b.size())
      {
	int ai = (i < a.size()) ? a[a.size() - 1 - i] - '0' : 0;
	int bi = (i < b.size()) ? b[b.size() - 1 - i] - '0' : 0;
	int sum = ai + bi + up;

	ret += sum % 10 + '0';
	up = sum / 10;

	i++;
      }

    if (up)
      ret += '1';

    reverse(ret.begin(), ret.end());
    return ret;
  }

  string mul(string a, string b)
  {
    string ret = "0";
    vector <string> muls;

    for (int i=0; i<b.size(); i++)
      {
	string tmp;
	int cur = b[b.size() - 1 - i] - '0';
	for (int j=0; j<i; j++)
	  tmp += "0";

	int up = 0;
	for (int j=0; j<a.size(); j++)
	  {
	    int n = a[a.size() - 1 - j] - '0';
	    n *= cur;
	    n += up;
	    up = n / 10;
	    tmp += n % 10 + '0';
	  }
	if (up)
	  tmp += up + '0';
	reverse(tmp.begin(), tmp.end());
	muls.push_back(tmp);
      }

    for (int i=0; i<muls.size(); i++)
      ret = plus(ret, muls[i]);

    return ret;
  }

  string prettyPrint(int A, int B)
  {
    string ret;
    string m = "1";

    for (int i=A; i<=B; i++)
      m = mul(m, toStr(i));

    int zeros = 0;
    for (int i=0;; i++)
      if (m[m.size() - 1 - i] == '0')
	zeros++;
      else
	break;

    m.erase(m.end()-zeros, m.end());

    if (m.size() > 10)
      {
	ret += m.substr(0, 5);
	ret += "...";
	ret += m.substr(m.size()-5, 5);
      }
    else
      {
	ret += m;
      }

    ret += " * 10^";
    ret += toStr(zeros);

    return ret;
  }
};