USACO 3.2 Factorials

Do pre-processing steps to remove the pairs of factor 2 and 5 (which combines together can generate a 0). Then do factorial calculation against preprocessed numbers, and only keep a single digit at each step.
Why not just keep a single digit without pre-processing step? Because even if a digit is not zero, it could become zero after multiplying - so we need make sure kill those factors (2 and 5) first.

int N;
int main() {
  ifstream fin("fact4.in");
  ofstream fout("fact4.out");
  fin >> N;
  vector<int> num(N, 0);
  for (int i = 0; i < N; ++i) {
    num[i] = i + 1;
  }
  int cnt = 0;
  for (auto &i : num) {
    while (i % 5 == 0) {
      i = i / 5;
      ++cnt;
    }
  }
  for (auto &i : num) {
    while (i % 2 == 0) {
      if (cnt == 0) break;
      i = i / 2;
      --cnt;
    }
    if (cnt == 0) break;
  }
  long long r = 1;
  for (int i = 0; i < N; ++i) {
    r = (r * num[i]) % 10;
  }
  cout << r << endl;
  fout << r << endl;
}

2016-10-25

USACO

USACO 3.1 Stamps

Dynamic programming problem. Let dp[i] denotes the minimum number of stamps required to construct a value of i. Then the state transfer function is dp[i] = min(dp[i - val[j]) + 1 for all j between 1 and N, where i >= val[j].

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <string>
#include <map>
#include <unordered_map>
#include <climits>
#include <sstream>

using namespace std;

int K, N;
int main() {
  ifstream fin("stamps.in");
  ofstream fout("stamps.out");
  fin >> K >> N;
  vector<int> val(N, 0);
  for (int i = 0; i < N; ++i) {
    fin >> val[i];
  }
  vector<int> dp(2000001, INT_MAX);
  dp[0] = 0;
  int i = 0;
  while (dp[i] <= K) {
    ++i;
    int cur = INT_MAX;
    for (int j = 0; j < N; ++j) {
      if (val[j] > i) continue;
      cur = std::min(cur, dp[i - val[j]]);
    }
    dp[i] = cur + 1;
  }
  
  fout << i - 1 << endl;
  cout << i - 1 << endl;
}

2016-10-23

USACO

USACO 3.1 Contact

The problem can be reduced to a string search and counting problem. The search space is any possible sub strings with size between A and B inclusive. Use a map to record the frequency of the occurrence of each bit pattern (string). Nothing dramatic, but the output formatting is quite nuisance. 输出坑爹!

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <string>
#include <map>
#include <unordered_map>
#include <climits>
#include <sstream>

using namespace std;

int A, B, N;
int main() {
  ifstream fin("contact.in");
  ofstream fout("contact.out");
  fin >> A >> B >> N;
  string s, t;
  while (fin >> t) {
    s += t;
  }
  cout << s << endl;
  
  map<string, int, std::greater<string>> map;
  const int size = (int)s.size();
  for (int i = 0; i < size; ++i) {
    for (int j = A; j <= B && i + j <= size; ++j) {
      string sub = s.substr(i, j);
      map[sub]++;
    }
  }
  std::vector<pair<int, string>> v;
  unordered_map<int, int> cm; // Key: frequence; Val: frequence count.
  for (auto iter = map.begin(); iter != map.end(); ++iter) {
    v.emplace_back(make_pair(iter->second, iter->first));
    cm[iter->second]++;
  }
  sort(v.begin(), v.end(), [] (const pair<int, string> &a,
                               const pair<int, string> &b) {
    if (a.first > b.first) return true;
    if (a.first < b.first) return false;
    int sa = (int)a.second.size(), sb = (int)b.second.size();
    if (sa < sb) return true;
    if (sa > sb) return false;
    return a.second < b.second;
  });
  
  for (int i = 0, count = 0; count < N && i < v.size();) {
    int cnt = cm[v[i].first];
    fout << v[i].first << endl;
    if (cnt > 1) {
      for (int j = 0; j < cnt; ++j) {
        if ((j + 1) % 6 == 0 || j == cnt - 1) {
          fout << v[i + j].second << endl;
        } else {
          fout << v[i + j].second << " ";
        }
      }
      i += cnt;
    } else {
      fout << v[i].second << endl;
      ++i;
    }
    ++count;
  }
}