248_next_min_number.cpp

//248_next_min_number.cpp
// by cydu

#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>

/*
 * 数组里只会出现0到9,给一个数组,一个数target,
 * 找到用数组里的数字组合成的大于target的最小数字,
 * 数组里数字可以任意组合,重复使用。
 * [1,2] 11 -> 12
 * [1] 2222 -> 11111 
 * [1,5,7] 56 -> 57 
 * [1,5] 56 -> 111
 */

using namespace std;
 
string bruteforce(string num, vector<char> dict) {
  int v = atoi(num.c_str());
  set<char> ds = set<char>(dict.begin(), dict.end());
  while (++v) {
    stringstream ss;
    ss << v;
    string vs = ss.str();
    int i;
    for (i = 0; i < vs.length(); ++i) {
      if (ds.find(vs[i]) == ds.end()) {
        break; 
      }
    }
    if (i == vs.length()) {
      return vs;
    }
  }
  return "Error!";
}
 
string find_next(string num, vector<char> dict) {
  if (dict.empty() || dict == vector<char>(1, '0')) {
    throw;
  }
 
  sort(dict.begin(), dict.end());
  string ans = string(num.length(), dict[0]);
  if (string(num.length(), dict.back()) <= num) {
    return string(1, dict[0] != '0' ? dict[0] : dict[1]) + ans;
  }
 
  vector<char>::iterator it;
  int bp = num.length() - 1; // break point
  for (int i = 0; i < num.length(); ++i) {
    it = lower_bound(dict.begin(), dict.end(), num[i]);
    if (it != dict.end()) {
      ans[i] = *it;
      if (*it > num[i]) {
        return ans;
      }
    } else {
      bp = i;
      break;
    }
  }
   
  for (int i = bp; ans <= num && i >= 0; --i) {
    it = upper_bound(dict.begin(), dict.end(), num[i]);
    if (it != dict.end()) {
      ans[i] = *it;
      for (int j = i+1; j < num.length(); ++j) {
        ans[j] = dict[0];
      }
    }
  }
  return ans;
}

void test(string &s, string &d) {
  //cout << "s:" << s << ", d:" << d << endl;
  set<char> dict;
  for (int i = 0; i < d.length(); ++i) {
    dict.insert(d[i]);
  }
  vector<char> vdict = vector<char>(dict.begin(), dict.end());
  string ans = find_next(s, vdict);
  string bans = bruteforce(s, vdict);
  if (bans != ans) {
    char buf[4096];
    snprintf(buf, sizeof(buf), "Error: %s %s, %s != %s\n", 
        s.c_str(), d.c_str(), ans.c_str(), bans.c_str());
    cout << buf;
  } else {
    // cout << s << " " << d << " " << ans << endl;
  }
}
 
int main() {
  srand(NULL);
  int base = 10000;
  for (int i = 1; i < 100; ++i) {
    int ii = rand() % base;
    stringstream si;
    si << ii;
    string s = si.str();
    for (int j = 1; j < 100; ++j) {
      int jj = rand() % base + 1;
      stringstream sj;
      sj << jj;
      string d = sj.str();
      test(s, d);
    }
    string ss[] = {"5", "9", "059", "59", "135", "1345", "3459", "567", "1234567890"};
    for (int k = 0; k < 9; k++) {
        test(s, ss[k]);
    }
  }
  return 0;
}

int main_1() {
  string s, d, v;
  while (cin >> s >> d >> v) {
    vector<char> dict;
    for (int i = 0; i < d.length(); ++i) {
      dict.push_back(d[i]);
    }
    string ans = find_next(s, dict);
    string bans = bruteforce(s, dict);
    if (ans != v || bans != ans) {
      char buf[4096];
      snprintf(buf, sizeof(buf), "Error: %s %s, %s != %s %s\n", 
          s.c_str(), d.c_str(), ans.c_str(), v.c_str(), bans.c_str());
      cout << buf;
    }
  }
  return 0;
 
  for (int i = 1; i < 1200; ++i) {
    stringstream si;
    si << i;
    for (int j = 1; j < 120; ++j) {
      stringstream sj;
      sj << j;
 
      string s = si.str();
      string d = sj.str();
      set<char> dict;
      for (int i = 0; i < d.length(); ++i) {
        dict.insert(d[i]);
      }
      vector<char> vdict = vector<char>(dict.begin(), dict.end());
      string ans = find_next(s, vdict);
      string bans = bruteforce(s, vdict);
      if (bans != ans) {
        char buf[4096];
        snprintf(buf, sizeof(buf), "Error: %s %s, %s != %s\n", 
            s.c_str(), d.c_str(), ans.c_str(), bans.c_str());
        cout << buf;
      } else {
        cout << i << " " << d << " " << ans << endl;
      }
    }
  }
  return 0;
}
 
/*
248_next_min_number.in
 
131 12 211
11 12 12
2222 1 11111
56 157 57
56 15 111
57 157 71
212112 12 212121
2222111 12 2222112
2211222 12 2212111
2213222 12 2221111
222 10 1000
0 1 1
1 1 11
999 9 9999
999 89 8888
889 89 898
889 78 7777
10212 124 11111
130 12 211
*/