SRM 405 div2 (practice)

Easy – FallingFactorialPower

For implementing quickly, consider conditions (k 0), and calculate the answer respectively using the for loop.

class FallingFactorialPower {
public:
  double compute(int n, int k) {
    double ret = 1;

    if (k < 0)
      for (int i=1; i<=abs(k); i++)
        ret /= (double)(n + i);
    else if (k > 0)
      for (int i=0; i<k; i++)
        ret *= (double)(n - i);

    return ret;
  }
};

Medium – RelativePath

Took a quick string processing-like approach. First of all, divide the two strings by “/” and store into two vectors. Check the vectors simultaneously to find an index that the first time two element of vectors are differ. Then append “../” to reach such index, and also append paths behind from such index.

class RelativePath {
public:
  vector <string> split(const string _s, const string del) {
    vector <string> ret;
    string s = _s;

    while (!s.empty())
      {
        size_t pos = s.find(del);
        string sub = "";
        sub = s.substr(0, pos);
        ret.push_back(sub);
        if (pos != string::npos)
          pos += del.size();
        s.erase(0, pos);
      }

    return ret;
  }

  string makeRelative(string path, string currentDir) {
    string ret;

    vector <string> p = split(path, "/");
    vector <string> c = split(currentDir, "/");

    int i = 0, n = min(p.size(), c.size());
    for (i=0; i<n; i++)
      if (p[i] != c[i]) break;

    for (int j=0; j<c.size() - i; j++)
      ret += "../";
    for (int j=i; j<p.size(); j++)
      ret += p[j] + "/";

    ret.erase(ret.end()-1);

    return ret;
  }
};