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;  
      }  
 };