POJ.2413 How many Fibs?

1.Problem
http://poj.org/problem?id=2413

2.Idea
Enumerating first 500 fibs numbers.

3.Source

 string add(string a, string b)  
 {  
      if (a == "") return b;  
      if (b == "") return a;  
      if (a.length() < b.length()) swap(a, b);  
      int d = a.length() - b.length();  
      for (int i = 0; i < d; i++) {  
           b = "0" + b;  
      }  
      int car = 0;  
      int n = a.length();  
      for (int i = n - 1; i >= 0; i--) {  
           int tmp = car + a[i] + b[i] - '0' - '0';  
           a[i] = '0' + (tmp % 10);  
           car = tmp / 10;  
      }  
      if (car > 0) return "1" + a;  
      else return a;  
 }  
 bool isNotSmaller(string a, string b) // a <= b -> true  
 {  
      if (a == b) return true;  
      if (a.length() < b.length()) return true;  
      if (a.length() == b.length() && a <= b) return true;  
      return false;  
 }  
 bool isNotGreater(string a, string b) // a >= b -> true  
 {  
      if (a == b) return true;  
      if (a.length() > b.length()) return true;  
      if (a.length() == b.length() && a >= b) return true;  
      return false;  
 }  
 vector<string> fibs;  
 int main()  
 {  
      fibs.push_back("1");  
      fibs.push_back("1");  
      for (int i = 2; i < 500; i++) {  
           string tmp = add(fibs[i - 1], fibs[i - 2]);  
           fibs.push_back(tmp);  
      }  
      while (true) {  
           string a, b;  
           cin >> a >> b;  
           if (a == "0" && b == "0") break;  
           int cnt = 0;  
           for (int i = 1; i < 500; i++) {  
                if (isNotSmaller(a, fibs[i]) && isNotGreater(b, fibs[i])) cnt++;  
           }  
           cout << cnt << endl;  
      }  
      return 0;  
 }  

POJ.1598 Excuses, Excuses!

1.Problem
http://poj.org/problem?id=1598

2.Idea
KMP string matching

3.Source

 int nextarray[1000006];  
 void getnext(string s)  
 {  
      memset(nextarray, 0, sizeof(nextarray));  
      int j = -1, k = 0;  
      nextarray[0] = -1;  
      while (k < s.size())  
      {  
           if (j == -1 || s[j] == s[k])  
                nextarray[++k] = ++j;  
           else  
                j = nextarray[j];  
      }  
 }  
 int kmp(string &a, string &b)  
 {  
      int i = 0, j = 0, ans = 0;  
      while (i < a.size())  
      {  
           if (j == -1 || a[i] == b[j])  
                ++i, ++j;  
           else  
                j = nextarray[j];  
           if (j == b.size())  
                ++ans, j = nextarray[j];  
      }  
      return ans;  
 }  
 int k, e;  
 string kw[100], es[100];  
 int score[100];  
 int main()  
 {  
      int t = 1;  
      while (scanf("%d%d\n", &k, &e) != EOF) {  
           for (int i = 0; i < k; i++) {  
                cin >> kw[i];  
           }  
           for (int i = 0; i < e; i++) {  
                getline(cin, es[i]);  
                transform(es[i].begin(), es[i].end(), es[i].begin(), ::tolower);  
           }  
           memset(score, 0, sizeof score);  
           int mx = -1;  
           for (int i = 0; i < e; i++) {  
                for (int j = 0; j < k; j++) {  
                     getnext(kw[j]);  
                     score[i] += kmp(es[i], kw[j]);  
                }  
                mx = max(mx, score[i]);  
           }  
           cout << "Excuse Set #" << t++ << endl;  
           for (int i = 0; i < e; i++) {  
                if (score[i] == mx) {  
                     cout << es[i] << endl;  
                }  
           }  
           cout << endl;  
      }  
      return 0;  
 }  

POJ.2406 Power Strings

1.Problem
http://poj.org/problem?id=2406

2.Idea
KMP pre-processing

3.Source

 char s[1000006];  
 int n;  
 int nextarray[1000006];  
 void getnext()  
 {  
      memset(nextarray, 0, sizeof(nextarray));  
      int j = -1, k = 0;  
      nextarray[0] = -1;  
      while (k < n)  
      {  
           if (j == -1 || s[j] == s[k])  
                nextarray[++k] = ++j;  
           else  
                j = nextarray[j];  
      }  
 }  
 int main()  
 {  
      while (scanf("%s", &s) > 0) {  
           n = strlen(s);  
           if (s[0] == '.' && n == 1) break;  
           getnext();  
           if (n % (n - nextarray[n]) == 0)  
                cout << n / (n - nextarray[n]) << endl;  
           else  
                cout << 1 << endl;  
      }  
      return 0;  
 }  

POJ.2752 Seek the Name, Seek the Fame

1.Problem
http://poj.org/problem?id=2752

2.Idea
calculate all prefix&suffix by KMP.

3.Source

 string s;  
 int nextarray[400005];  
 void getnext(string &str)  
 {  
      memset(nextarray, 0, sizeof(nextarray));  
      int j = -1, k = 0;  
      nextarray[0] = -1;  
      while (k < str.size())  
      {  
           if (j == -1 || str[j] == str[k])  
                nextarray[++k] = ++j;  
           else  
                j = nextarray[j];  
      }  
 }  
 void solve()  
 {  
      getnext(s);  
      int cur = s.size();  
      vector<int> ans;  
      while (cur > 0) {  
           ans.push_back(cur);  
           cur = nextarray[cur];  
      }  
      sort(ans.begin(), ans.end());  
      for (int i = 0; i < ans.size(); i++) {  
           cout << ans[i] << " ";  
      }  
      cout << endl;  
 }  
 int main()  
 {  
      while (cin >> s) {  
           solve();  
      }  
      return 0;  
 }  

POJ.1080 Human Gene Functions

1.Problem
http://poj.org/problem?id=1080

2.Idea
DP + string

3.Source

 int mat[5][5] = {  
      5, -1, -2, -1, -3,  
      -1, 5, -3, -2, -4,  
      -2, -3, 5, -2, -2,  
      -1, -2, -2, 5, -1,  
      -3, -4, -2, -1, 0,  
 };  
 int dp[102][102];  
 int main()  
 {  
      int t;  
      cin >> t;  
      map<char, int> dic;  
      dic['A'] = 0; dic['C'] = 1; dic['G'] = 2;  
      dic['T'] = 3; dic['-'] = 4;  
      while (t--) {  
           int l, m;  
           string s, t;  
           cin >> l >> s;  
           cin >> m >> t;  
           memset(dp, 0, sizeof dp);  
           for (int i = 0; i < l; i++) dp[i + 1][0] = dp[i][0] + mat[dic[s[i]]][dic['-']];  
           for (int j = 0; j < m; j++) dp[0][j + 1] = dp[0][j] + mat[dic['-']][dic[t[j]]];  
           for (int i = 0; i < l; i++) {  
                for (int j = 0; j < m; j++) {  
                     dp[i + 1][j + 1] = max(dp[i + 1][j] + mat[dic['-']][dic[t[j]]],  
                                           max(dp[i][j + 1] + mat[dic[s[i]]][dic['-']],  
                                       dp[i][j] + mat[dic[s[i]]][dic[t[j]]]));                           
                }  
           }  
           cout << dp[l][m] << endl;  
      }  
      return 0;  
 }  

POJ.2121 Inglish-Number Translator

1.Problem
http://poj.org/problem?id=2121

2.Idea
Calculate digits for three parts of million, thousand, unit.

3.Source

 string words[] =  
 { "zero", "one", "two", "three",  
 "four", "five", "six", "seven",  
 "eight","nine", "ten", "eleven", "twelve",  
 "thirteen", "fourteen", "fifteen", "sixteen",  
 "seventeen", "eighteen", "nineteen", "twenty",  
 "thirty", "forty", "fifty", "sixty", "seventy",  
 "eighty", "ninety","hundred", "thousand", "million" };  
 int num2str[] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,30,40,50,60,70,80,90,100,1000,1000000 };  
 int main()  
 {  
      map<string, int> mp;  
      for (int i = 0; i < 31; i++) {  
           mp[words[i]] = num2str[i];  
      }  
      string str, line;  
      while (getline(cin, line)) {  
           if (line.length() == 0) break;  
           istringstream input(line);  
           bool neg = 0;  
           ll ans = 0, pre = 0;  
           while (input >> str) {  
                if (str == "negative") neg = 1;  
                else if (str == "hundred") pre *= 100;  
                else if (str == "thousand") {  
                     pre *= 1000;  
                     ans += pre;  
                     pre = 0;  
                }  
                else if (str == "million") {  
                     pre *= 1000000;  
                     ans += pre;  
                     pre = 0;  
                }  
                else {  
                     pre += mp[str];  
                }  
           }  
           ans += pre;  
           if (neg) ans *= -1;  
           cout << ans << endl;  
      }  
      return 0;  
 }  

LeetCode.5180 Constrained Subset Sum

1.Problem
https://leetcode.com/contest/weekly-contest-186/problems/constrained-subset-sum/

2.Idea
DP + maxQueue

3.Source

 class MaxQueue {  
 public:  
      MaxQueue() {}  
      bool empty() { return elements.empty(); }  
      int size() { return elements.size(); }  
      void push(int val) {  
           elements.push(val);  
           while (!maxElements.empty() && val > maxElements.back()) maxElements.pop_back();  
           maxElements.push_back(val);  
      }  
      int pop() {  
           int val = elements.front();  
           elements.pop();  
           if (val == maxElements.front()) maxElements.pop_front();  
           return val;  
      }  
      int peekMax() {  
           return maxElements.front();  
      }  
 private:  
      queue<int> elements;  
      deque<int> maxElements;  
 };  
 class Solution {  
 public:  
      int dp[100005];  
      int constrainedSubsetSum(vector<int>& nums, int k) {  
           int n = nums.size();  
           int ans = -1000000007;  
           MaxQueue mq;  
           memset(dp, 0, sizeof dp);  
           dp[0] = nums[0];  
           mq.push(nums[0]);  
           for (int i = 1; i<n; i++) {  
                dp[i] = max(nums[i], mq.peekMax() + nums[i]);  
                ans = max(ans, dp[i]);  
                mq.push(nums[i]);  
                if (mq.size() > k) mq.pop();  
           }  
           return ans;  
      }  
 };  

POJ. 2192 Zipper

1.Problem
http://poj.org/problem?id=2192

2.Idea
dp[i][j]: true if suffix i+j of C can be made from suffix i of A + suffix j of B, otherwize false.

3.Source

 int t, n, m;  
 string a, b, c;  
 bool dp[202][202];  
 int main()  
 {  
      cin >> t;  
      for (int T = 1; T <= t; T++) {  
           cin >> a >> b >> c;  
           n = a.size();  
           m = b.size();  
           memset(dp, 0, sizeof dp);  
           dp[0][0] = true;  
           for (int i = 0; i <= n; i++) {  
                for (int j = 0; j <= m; j++) {  
                     if (i - 1 >= 0 && a[i - 1] == c[i + j - 1] && dp[i - 1][j]) dp[i][j] = true;  
                     if (j - 1 >= 0 && b[j - 1] == c[i + j - 1] && dp[i][j - 1]) dp[i][j] = true;  
                }  
           }  
           if (dp[n][m]) cout << "Data set " << T << ": yes" << endl;  
           else cout << "Data set " << T << ": no" << endl;  
      }  
      return 0;  
 }  

LeetCode.560 Subarray Sum Equals K

1.Problem
https://leetcode.com/problems/subarray-sum-equals-k/

2.Idea
Using map for every sum of {0..i} and count.

3.Source

 class Solution {  
 public:  
      map<int, int> mp;  
      int sum = 0;  
      int subarraySum(vector<int>& nums, int k) {      
           int ans = 0;  
     mp[0] = 0;  
           for (int i = 0; i < nums.size(); i++) {  
                sum += nums[i];  
                if(sum == k) ans++;  
       mp[sum]++;  
                if (mp.find(sum - k) != mp.end()) {  
                     ans += mp[sum - k];  
                }  
           }  
     if(k == 0) return ans - nums.size();  
           else return ans;  
      }  
 };  

LeetCode.1419 Minimum Number of Frogs Croaking

1.Problem
https://leetcode.com/problems/minimum-number-of-frogs-croaking/

2.Idea
Counting chars while making sure order and number are correct.

3.Souce

 bool cmp(string a, string b)  
 {  
      return std::stoi(a) < std::stoi(b);  
 }  
 class Solution {  
 public:  
      vector<vector<string>> displayTable(vector<vector<string>>& orders) {  
           int N = orders.size();  
           map< pair<string, string>, int> ords;  
           vector<string> tables, items;  
           for (int i = 0; i < N; i++) {  
                string table = orders[i][1];  
                string item = orders[i][2];  
                ords[make_pair(table, item)]++;  
                tables.push_back(table);  
                items.push_back(item);  
           }  
           sort(tables.begin(), tables.end(), cmp);  
           std::vector<string>::iterator it;  
           it = std::unique(tables.begin(), tables.end());   
           tables.resize(std::distance(tables.begin(), it));  
           sort(items.begin(), items.end());  
           it = std::unique(items.begin(), items.end());  
           items.resize(std::distance(items.begin(), it));  
           int n = tables.size() + 1, m = items.size() + 1;  
           vector<vector<string>> ans(1);  
           ans[0].push_back("Table");  
           for (int i = 0; i < items.size(); i++) {  
                ans[0].push_back(items[i]);  
           }  
           for (int i = 0; i < tables.size(); i++) {  
                vector<string> tmp(m);  
                tmp[0] = tables[i];  
                ans.push_back(tmp);  
           }  
           for (int i = 1; i < n; i++) {  
                for (int j = 1; j < m; j++) {  
                     if (ords.find(make_pair(ans[i][0], ans[0][j])) == ords.end()) {  
                          ans[i][j] = "0";  
                     }  
                     else {  
                          ans[i][j] = std::to_string(ords[make_pair(ans[i][0], ans[0][j])]);  
                     }  
                }  
           }  
           return ans;  
      }  
 };  

POJ.3461 Oulipo

1.Problem
http://poj.org/problem?id=3461

2.Idea
KMP method for string matching

3.Source

 const int maxw = 10000 + 10;   
 const int maxt = 1000000 + 10;   
 //KMP Method  
 int match(char w[], char s[], int next[])  
 {   
      int cnt = 0;  
      int slen = strlen(s);  
      int wlen = strlen(w);  
      int p = 0, cur = 0;  
      while (cur < slen) {   
           if (s[cur] == w[p]) {   
                ++cur;  
                ++p;  
           }  
           else if (p >= 0) {   
                p = next[p];  
           }  
           else {  
                ++cur;  
                p = 0;  
           }  
           if (p == wlen) {   
                ++cnt;  
                p = next[p];  
           }  
      }  
      return cnt;  
 }  
 int main(void)  
 {  
      int loop;  
      scanf("%d", &loop);  
      while (loop--) {  
           char w[maxw], t[maxt];  
           scanf("%s%s", w, t);   
           int suffix[maxw]; // prefix function for word w  
           suffix[0] = -1;  
           suffix[1] = 0;  
           int p = 0;  
           for (int cur = 2; cur <= strlen(w); cur++) {  
                while (p >= 0 && w[p] != w[cur - 1])  
                     p = suffix[p];  
                suffix[cur] = ++p;  
           }  
           printf("%d\n", match(w, t, suffix));   
      }  
      return 0;  
 }  

Codeforces. 1336B Xenia and Colorful Gems

1.Problem
https://codeforces.com/contest/1336/problem/B

2.Idea
Assuming x <= y <=z.
Enumerating middle value, and find smallest and biggest value by binary_search.

3.Source

 int nr, ng, nb;  
 ll ans = 1LL << 60;  
 ll calc(ll x, ll y, ll z)  
 {  
      return (x - y)*(x - y) + (y - z)*(y - z) + (x - z)*(x - z);  
 }  
 void solve(vector<int> a, vector<int> b, vector<int> c) {  
      for (auto x : a) {  
           auto y = lower_bound(b.begin(), b.end(), x);  
           auto z = upper_bound(c.begin(), c.end(), x);  
           if (y == b.end() || z == c.begin()) { continue; }  
           z--;   
           ans = min(ans, calc(x, *y, *z));  
      }  
 }  
 int main()  
 {  
      int t; cin >> t;  
      while (t--) {  
           ans = 1LL << 62;  
           cin >> nr >> ng >> nb;  
           vector<int> r(nr), g(ng), b(nb);  
           for (int i = 0; i < nr; i++) {  
                cin >> r[i];  
           }  
           for (int i = 0; i < ng; i++) {  
                cin >> g[i];  
           }  
           for (int i = 0; i < nb; i++) {  
                cin >> b[i];  
           }  
           sort(r.begin(), r.end());  
           sort(g.begin(), g.end());  
           sort(b.begin(), b.end());  
           solve(r, g, b);  
           solve(r, b, g);  
           solve(g, r, b);  
           solve(g, b, r);  
           solve(b, g, r);  
           solve(b, r, g);  
           cout << ans << endl;  
      }  
      return 0;  
 }  

LeetCode.678 Valid Parenthesis String

1.Problem
https://leetcode.com/problems/valid-parenthesis-string/

2.Idea
Greedy approach. Evaluating possible lower and upper bound value of open parenthesis number.

3.Source

 class Solution {  
 public:  
   bool checkValidString(string s) {  
     int lo = 0, hi = 0;  
     for (int i = 0; i < s.size(); i++) {  
       lo += s[i] == '(' ? 1 : -1;  
       hi += s[i] != ')' ? 1 : -1;  
       if (hi < 0) break;  
       lo = std::max(lo, 0);  
     }  
     return lo == 0;  
   }  
 };  

POJ.3080 Blue Jeans

1.Problem
http://poj.org/problem?id=3080

2.Idea
Brute Force + KMP

3.Source

 int nextarray[65];  
 string str[15];  
 void getnext(string &str)  
 {  
      memset(nextarray, 0, sizeof(nextarray));  
      int j = -1, k = 0;  
      nextarray[0] = -1;  
      while (k < str.size())  
      {  
           if (j == -1 || str[j] == str[k])  
                nextarray[++k] = ++j;  
           else  
                j = nextarray[j];  
      }  
 }  
 bool kmp(string &a, string &b)  
 {  
      int i = 0, j = 0, ans = 0;  
      while (i < a.size())  
      {  
           if (j == -1 || a[i] == b[j])  
                ++i, ++j;  
           else  
                j = nextarray[j];  
           if (j == b.size())  
                ++ans, j = nextarray[j];  
      }  
      if (ans)  
           return true;  
      return false;  
 }  
 int main()  
 {  
      string s;  
      ios::sync_with_stdio(0);  
      int n;  
      cin >> n;  
      for (int i = 0; i < n; ++i)  
      {  
           int m;  
           cin >> m;  
           for (int j = 0; j < m; ++j)  
                cin >> str[j];  
           string ans = "";  
           for (int j = 0; j < str[0].size(); ++j)  
                for (int k = 1; k + j <= str[0].size(); ++k)  
                {  
                     s = str[0].substr(j, k);  
                     getnext(s);  
                     bool flag = 0;  
                     for (int l = 1; l < m; ++l)  
                          //cout << kmp(str[l], s) << " " << str[l] << " " << s << endl;  
                          if (!kmp(str[l], s))  
                               flag = 1;  
                     //cout << flag << endl;  
                     if (!flag)  
                     {  
                          if (ans.size() < s.size())  
                               ans = s;  
                          else if (ans.size() == s.size() && ans > s)  
                               ans = s;  
                          //cout << ans << endl;  
                     }  
                }  
           if (ans.size() < 3)  
                cout << "no significant commonalities" << endl;  
           else  
                cout << ans << endl;  
      }  
      return 0;  
 }  

CodeForces. 1337C Linova and Kingdom

1.Problem
https://codeforces.com/contest/1337/problem/C

2.Idea
Sort by {Depth - Child Number}, and pick k vertices.

3.Source

 int n, k;  
 vector<int> adj[N];  
 int dist[N];  
 bool visited[N];  
 int child[N];  
 bool col[N];  
 int dist2[N];  
 struct City {  
      int num, child, dist;  
      bool operator < (const City &a)const {  
           return dist - child < a.dist - a.child;  
      }  
 } Cities[N];  
 void getChild(int k)  
 {  
      //cout << k << endl;  
      visited[k] = true;  
      for (int i = 0; i < adj[k].size(); i++) {  
           int u = adj[k][i];  
           if (visited[u] == 0) {  
                getChild(u);  
                child[k] += (1 + child[u]);  
           }  
      }  
 }  
 void colorCities()  
 {  
      for (int i = 0; i < n; i++) {  
           Cities[i].num = i;  
           Cities[i].child = child[i];  
           Cities[i].dist = dist[i];  
      }  
      sort(Cities, Cities + n);  
      for (int i = 0; i < n - k; i++) {  
           int t = Cities[i].num;  
           col[t] = true;  
      }  
 }  
 int main()  
 {  
      cin >> n >> k;  
      for (int i = 0; i < n - 1; i++) {  
           int u, v;  
           cin >> u >> v;  
           u--; v--;  
           adj[u].push_back(v);  
           adj[v].push_back(u);  
      }  
      // get dist  
      memset(visited, 0, sizeof visited);  
      queue<P> q;  
      q.push(P(0, 0));  
      while (!q.empty()) {  
           int v = q.front().first;  
           int d = q.front().second;  
           q.pop();  
           visited[v] = 1;  
           dist[v] = d;  
           for (int i = 0; i < adj[v].size(); i++) {  
                int u = adj[v][i];  
                if (visited[u] == 0 && dist[u] == 0) {  
                     q.push(P(u, d + 1));  
                }  
           }  
      }  
      //get child  
      memset(visited, 0, sizeof visited);  
      getChild(0);  
      //color  
      colorCities();  
      //count  
      memset(visited, 0, sizeof visited);  
      queue<P> q1;  
      q1.push(P(0, 0));  
      while (!q1.empty()) {  
           int v = q1.front().first;  
           int d = q1.front().second;  
           q1.pop();  
           visited[v] = 1;  
           dist2[v] = d;  
           if (col[v]) d++;  
           for (int i = 0; i < adj[v].size(); i++) {  
                int u = adj[v][i];  
                if (visited[u] == 0) {  
                     q1.push(P(u, d));  
                }  
           }  
      }  
      int ans = 0;  
      for (int i = 0; i < n; i++) {  
           if (col[i] == 0) ans += dist2[i];  
      }  
      cout << ans << endl;  
      return 0;  
 }  

CodeForces. 1339D Edge Weight Assignment

1.Problem.
https://codeforces.com/contest/1339/problem/D

2.Idea
Here

3.Source

 vector<int> adj[N];  
 int d[N];  
 set<int> st;  
 // calc dist from root  
 void dfs(int v, int p)  
 {  
      for (auto& x : adj[v]) {  
           if (x == p) continue;  
           d[x] = d[v] + 1;  
           dfs(x, v);  
      }  
 }  
 int main()  
 {  
      int n;  
      cin >> n;  
      for (int i = 1; i < n; i++) {  
           int v, u;  
           cin >> v >> u;  
           adj[u].push_back(v);  
           adj[v].push_back(u);  
      }  
      int root = 0;  
      for (int i = 1; i <= n; i++) {  
           if (adj[i].size() == 1) {  
                root = i;  
                break;  
           }  
      }  
      dfs(root, 0);  
      int mn = 1, mx = n - 1;  
      for (int i = 1; i <= n; i++) {  
           if (adj[i].size() == 1) {  
                if (d[i] % 2 != 0) {  
                     mn = 3;  
                }  
                st.insert(adj[i][0]);  
                --mx;  
           }  
      }  
      mx += st.size();  
      cout << mn << " " << mx << endl;  
      return 0;  
 }  

POJ.2080 Calendar

1.Problem
http://poj.org/problem?id=2080

2.Idea
Simulate exact date month year

3.Source

 const char wstr[][20] = { "Saturday","Sunday","Monday","Tuesday","Wednesday","Thursday","Friday" };  
 int days_of_year(int year)  
 {  
      if (year % 100 == 0) {  
           return year % 400 == 0 ? 366 : 365;  
      }  
      return year % 4 == 0 ? 366 : 365;  
 }  
 int days_of_month(int month, int year)  
 {  
      if (month == 2)  
           return days_of_year(year) == 366 ? 29 : 28;  
      int d;  
      switch (month)  
      {  
           case 1: case 3: case 5: case 7: case 8: case 10: case 12:   
                d = 31; break;  
           default:  
                d = 30;  
                break;  
      }  
      return d;  
 }  
 int main()  
 {  
      int n;  
      cin >> n;  
      while (n >= 0) {  
           int year, month, day, week;  
           week = n % 7;  
           year = 2000;  
           month = 1;  
           day = 1;  
           while (n) {  
                if (n >= days_of_year(year)) {  
                     n -= days_of_year(year);  
                     year++;  
                }  
                else if(n >= days_of_month(month, year)) {  
                     n -= days_of_month(month, year);  
                     month++;  
                }  
                else {  
                     day += n;  
                     n = 0;  
                }  
           }  
           cout << year << '-' << (month < 10 ? "0" : "") << month << "-" << (day < 10 ? "0" : "") << day << " " << wstr[week] << endl;  
           cin >> n;  
      }  
      return 0;  
 }  

Codeforces.1334C Circle of Monsters

1.Problem
https://codeforces.com/contest/1334/problem/C

2.Idea
Only start point takes a[i] shoots, and other places a[i] - b[i-1]. Check every places as start point.

3.Source

 int n, t;  
 ll a[300005], b[300005], ac[300005];  
 void solve()  
 {  
      ll sum = 0;  
      for (int i = 0; i < n; i++) {  
           ac[i] = max(0ll, a[i] - b[(i + n - 1) % n]);  
           sum += ac[i];  
      }  
      ll ans = 1ll << 60;  
      for (int i = 0; i < n; i++) {  
           ans = min(ans, sum - ac[i] + a[i]);  
      }  
      //cout << ans << endl;  
      printf("%lld\n", ans);  
 }  
 int main()  
 {  
      scanf("%d", &t);  
      while (t--) {  
           scanf("%d", &n);  
           for (int i = 0; i < n; i++) {  
                scanf("%lld%lld", &a[i], &b[i]);  
           }  
           solve();  
      }  
      return 0;  
 }  

CodeForces. 1333C Eugene and an array

1.Problem
https://codeforces.com/problemset/problem/1333/C

2.Idea
Keep tracking right most sum zero segment. 

3.Source

 int n;  
 map<ll, int> mp;  
 ll ans, sum;  
 int x, q;  
 int main()  
 {  
      cin >> n;  
      q = -1;  
      mp[0] = 0;  
      for (int i = 1; i <= n; i++)  
      {  
           cin >> x;  
           sum += x;  
           if (mp.count(sum)) {  
                q = max(q, mp[sum]);  
           }  
           ans += (i - q - 1);  
           mp[sum] = i;  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ.1019 Number Sequence

1.Problem
http://poj.org/problem?id=1019

2.Idea
Enumeration

3.Source

 #define MAX_N 35000  
 ll a[MAX_N];  
 ll b[MAX_N];  
 int n;  
 int getDigNum(int k)  
 {  
      if (k < 1) return 0;  
      int ans = 0;  
      while (k) {  
           ans++;  
           k /= 10;  
      }  
      return ans;  
 }  
 void solve()  
 {  
      if (n == 1) {  
           cout << 1 << endl;  
           return;  
      }  
      if (n == 2) {  
           cout << 1 << endl;  
           return;  
      }if (n == 3) {  
           cout << 2 << endl;  
           return;  
      }  
      int i1 = 1, i2 = 1;  
      //get group  
      while (b[i1] <= n) i1++;  
      i1--;  
      if (b[i1] == n) {  
           cout << i1 % 10 << endl;  
           return;  
      }  
      else {  
           n = n - b[i1];  
      }  
      //get number  
      while (a[i2] <= n) i2++;  
      i2--;  
      if (a[i2] == n) {  
           cout << i2 % 10 << endl;  
           return;  
      }  
      else {  
           n = n - a[i2];  
      }  
      //get digit  
      int h = i2 + 1;  
      n = getDigNum(h) - n;  
      h = h / (int)pow(10.0, n);  
      cout << h % 10 << endl;  
 }  
 int main()  
 {       
      for (int i = 1; i < MAX_N; i++) {  
           a[i] = a[i - 1] + getDigNum(i);  
           b[i] = b[i - 1] + a[i];  
      }  
      int t = 0;  
      cin >> t;  
      while (t--) {  
           cin >> n;  
           solve();  
      }  
      return 0;  
 }  

LeetCode 122. Best Time to Buy and Sell Stock II

1.Problem
https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/528/week-1/3287/

2.Idea
Just keep adding positive diffs.

3.Source

 class Solution {  
 public:  
      int maxProfit(vector<int>& prices) {  
           int ans = 0;  
           for (int i = 1; i < prices.size(); i++) {  
                if (prices[i - 1] < prices[i]) {  
                     ans += (prices[i]- prices[i - 1]);  
                }  
           }  
           return ans;  
      }  
 };  

POJ.1338 Ugly Numbers

1.Problem
http://poj.org/problem?id=1338

2.Idea
Using 3 variables

3.Source

 ll ans[1502];  
 int main()  
 {  
      ans[1] = 1;  
      int u2 = 1, u3 = 1, u5 = 1;  
      for (int i = 2; i <= 1500; i++) {  
           int value2 = ans[u2] * 2;  
           int value3 = ans[u3] * 3;  
           int value5 = ans[u5] * 5;  
           ans[i] = min(min(value2, value3), value5);  
           if (ans[i] == value2) u2++;  
           if (ans[i] == value3) u3++;  
           if (ans[i] == value5) u5++;  
      }  
      int n;  
      while ((cin >> n), n)  
      {  
           cout << ans[n] << endl;  
      }  
      return 0;  
 }  

POJ.3006 Dirichlet's Theorem on Arithmetic Progressions

1.Problem
http://poj.org/problem?id=3006

2.Idea
Sieve of Eratosthenes

3.Source

 bool isPrime[1000006];  
 vector<int> Primes;  
 int a, d, n;  
 //Sieve of Eratosthenes  
 void prep()  
 {  
      for (int i = 2; i < 1000006; i++) {  
           if (isPrime[i]==0) {  
                Primes.push_back(i);  
                for (int j = i * 2; j < 1000006; j += i) {  
                     isPrime[j] = 1;  
                }  
           }  
      }  
 }  
 int main()  
 {  
      prep();  
      while (scanf("%d%d%d", &a, &d, &n) > 0) {  
           if (a + d + n == 0) break;  
           int cnt = 0;  
           for (int i = 0; i < Primes.size(); i++) {  
                if (Primes[i] >= a && (Primes[i] - a) % d == 0) {  
                     cnt++;  
                     if (cnt == n) {  
                          cout << Primes[i] << endl;  
                          break;  
                     }  
                }  
           }  
      }  
      return 0;  
 }  

POJ.2739 Sum of Consecutive Prime Numbers

1.Problem
http://poj.org/problem?id=2739

2.Idea
Enumerating primes

3.Source

 const int maxp = 2000;  
 int n = 10000;  
 int prime[maxp], total = 0;  
 bool isPrime(int k)  
 {  
      for (int i = 0; i < total; i++) {  
           if (k % prime[i] == 0) return false;  
      }  
      return true;  
 }  
 int main()  
 {  
      for (int i = 2; i <= n; i++) {  
           if (isPrime(i)) prime[total++] = i;  
      }  
      prime[total] = n + 1;  
      int m;  
      cin >> m;  
      while (m) {  
           int ans = 0;  
           for (int i = 0; m >= prime[i]; i++) {  
                int cnt = 0;  
                for (int j = i; j < total && cnt < m; j++) {  
                     cnt += prime[j];  
                }  
                if (cnt == m) ans++;  
           }  
           cout << ans << endl;  
           cin >> m;  
      }  
      return 0;  
 }