Advertisement
Guest User

Untitled

a guest
Apr 30th, 2016
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4. #define nfor(i, n) for (int i = int(n) - 1; i >= 0; i--)
  5. #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
  6. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  7. #define all(a) (a).begin(), (a).end()
  8. #define sz(a) int((a).size())
  9. #define pb(a) push_back(a)
  10. #define mp(x, y) make_pair((x), (y))
  11. #define x first
  12. #define y second
  13.  
  14. using namespace std;
  15.  
  16. typedef long long li;
  17. typedef long double ld;
  18. typedef pair<int, int> pti;
  19.  
  20. template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
  21. template<typename X> inline X sqr(const X& a) { return a * a; }
  22.  
  23. template<typename A, typename B> inline ostream& operator<< (ostream& out, const pair<A, B>& p) { return out << "(" << p.x << ", " << p.y << ")"; }
  24. template<typename T> inline ostream& operator<< (ostream& out, const vector<T>& a) { out << "["; forn(i, sz(a)) { if (i) out << ','; out << ' ' << a[i]; } return out << " ]"; }
  25. template<typename T> inline ostream& operator<< (ostream& out, const set<T>& a) { return out << vector<T>(all(a)); }
  26. template<typename X, typename Y> inline ostream& operator<< (ostream& out, const map<X, Y>& a) { return out << vector<pair<X, Y>>(all(a)); }
  27. template<typename T> inline ostream& operator<< (ostream& out, pair<T*, int> a) { return out << vector<T>(a.x, a.x + a.y); }
  28.  
  29. inline ld gett() { return ld(clock()) / CLOCKS_PER_SEC; }
  30.  
  31. const int INF = int(1e9);
  32. const li INF64 = li(1e18);
  33. const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
  34.  
  35. #ifdef SU1
  36. #define LOG
  37. #endif
  38.  
  39. string a, b;
  40.  
  41. bool read() {
  42.     return !!(cin >> a >> b);
  43. }
  44.  
  45. bool better(pair<string, string> a, pair<string, string> b) {
  46.     if (b.x.empty()) return true;
  47.     auto toInt = [](string s) {
  48.         stringstream ss;
  49.         ss << s;
  50.         li x;
  51.         ss >> x;
  52.         return x;
  53.     };
  54.     li ax = toInt(a.x), ay = toInt(a.y);
  55.     li bx = toInt(b.x), by = toInt(b.y);
  56.     if (abs(ax - ay) != abs(bx - by)) return abs(ax - ay) < abs(bx - by);
  57.     if (ax != bx) return ax < bx;
  58.     return ay < by;
  59. }
  60.  
  61. //#define CHECK
  62.  
  63. pair<string, string> solve(int test) {
  64.     printf("Case #%d: ", test + 1);
  65.  
  66.     pair<string, string> ans("", "");
  67.     forn(len, sz(a) + 1)
  68.     for (char da = '0'; da <= '9'; da++)
  69.     for (char db = '0'; db <= '9'; db++) {
  70.         string a(::a), b(::b);
  71.  
  72.         bool can = true;
  73.         forn(v, len) {
  74.             if (a[v] == '?' && b[v] == '?') a[v] = b[v] = '0';
  75.             else if (a[v] == '?') a[v] = b[v];
  76.             else if (b[v] == '?') b[v] = a[v];
  77.             else if (a[v] != b[v]) can = false;
  78.         }
  79.  
  80.         if (len < sz(a)) {
  81.             if (a[len] != '?' && a[len] != da) can = false;
  82.             else a[len] = da;
  83.             if (b[len] != '?' && b[len] != db) can = false;
  84.             else b[len] = db;
  85.             if (da == db) can = false;
  86.         }
  87.  
  88.         if (!can) continue;
  89.  
  90.         fore(i, len, sz(a)) {
  91.             if (a[i] == '?') a[i] = a[len] < b[len] ? '9' : '0';
  92.             if (b[i] == '?') b[i] = b[len] < a[len] ? '9' : '0';
  93.         }
  94.  
  95.         if (better(mp(a, b), ans))
  96.             ans = mp(a, b);
  97.     }
  98.  
  99.     return ans;
  100. }
  101.  
  102. bool match(string s, string p) {
  103.     assert(sz(s) == sz(p));
  104.     forn(i, sz(s))
  105.         if (p[i] != '?' && s[i] != p[i])
  106.             return false;
  107.     return true;
  108. }
  109.  
  110. pair<string, string> naive() {
  111.     auto toString = [](int x) {
  112.         stringstream ss;
  113.         ss << x;
  114.         return ss.str();
  115.     };
  116.     pair<string, string> ans("", "");
  117.     //cerr << "ans=" << ans << endl;
  118.     forn(i, 1000) {
  119.         string x = toString(i);
  120.         while (sz(x) < sz(a)) x = "0" + x;
  121.         if (sz(x) > sz(a) || !match(x, a)) continue;
  122.         forn(j, 1000) {
  123.             //i = 19, j = 23;
  124.             string x = toString(i);
  125.             string y = toString(j);
  126.             while (sz(x) < sz(a)) x = "0" + x;
  127.             while (sz(y) < sz(b)) y = "0" + y;
  128.             if (sz(x) > sz(a) || sz(y) > sz(b)) continue;
  129.             /*cerr << "x=" << x << " y=" << y << endl;
  130.             cerr << "match(x, a)=" << match(x, a) << " match(y, b)=" << match(y, b) << endl;
  131.             exit(0);*/
  132.             if (match(x, a) && match(y, b))
  133.                 if (better(mp(x, y), ans))
  134.                     ans = mp(x, y);
  135.         }
  136.     }
  137.     assert(isdigit(ans.x[0]));
  138.     return ans;
  139. }
  140.  
  141. int main() {
  142. #ifdef SU1
  143.     assert(freopen("input.txt", "rt", stdin));
  144.     assert(freopen("output.txt", "wt", stdout));
  145. #endif
  146.    
  147.     cout << setprecision(10) << fixed;
  148.     cerr << setprecision(5) << fixed;
  149.  
  150.     int tc;
  151.     cin >> tc;
  152.     forn(tt, tc) {
  153.         assert(read());
  154.         ld stime = gett();
  155.  
  156.         string a = ::a, b = ::b;
  157.         auto ans1 = solve(tt);
  158.         cout << ans1.x << ' ' << ans1.y << endl;
  159.  
  160. #ifdef CHECK
  161.         ::a = a, ::b = b;
  162.         auto ans2 = naive();
  163.  
  164.         if (ans1 != ans2) {
  165.             cerr << "exp: " << ans2 << " rec: " << ans1 << endl;
  166.             cerr << a << ' ' << b << endl;
  167.             exit(0);
  168.         }
  169. #endif
  170.  
  171.         cerr << "TEST #" << tt + 1 << endl;
  172.         cerr << "Time: " << gett() - stime << endl;
  173.         //break;
  174.     }
  175.    
  176.     return 0;
  177. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement