Guest User

Untitled

a guest
Nov 21st, 2018
317
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.96 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef long double lf;
  7. typedef pair<int, int> pii;
  8.  
  9. const int MAXN = 1e6+100;
  10. const int INF = 1e9+100;
  11. const int MOD = 1e9+9;
  12.  
  13. lf prob_d[15], dp[(1<<9)+10];
  14. int seen[(1<<9)+10];
  15. vector<int> moves[15];
  16.  
  17. lf to_double(string s) {
  18.   stringstream ss;
  19.   ss << s;
  20.   lf x; ss >> x;
  21.   return x;
  22. }
  23.  
  24. string to_str(int msk) {
  25.   string ans;
  26.   for(int i = 0; i < 9; i++) {
  27.     if(msk >> i & 1) ans.push_back(char(i+1+'0'));
  28.   }
  29.   if(ans.size() == 0) ans.push_back('0');
  30.   return ans;
  31. }
  32.  
  33. lf go(int mask) {
  34.   lf &r = dp[mask];
  35.   if(seen[mask]) return r;
  36.   seen[mask] = 1;
  37.   r = 0;
  38.   for(int d = 2; d <= 12; d++) {
  39.     bool f = 0;
  40.     lf aux = 1e20;
  41.     for(auto &m : moves[d]) {
  42.       if((mask & m) == m) {
  43.         f = 1;
  44.         aux = min(aux, go(mask ^ m));
  45.       }
  46.     }
  47.     if(f) r += prob_d[d] * aux;
  48.     else r += prob_d[d] * to_double(to_str(mask));
  49.   }
  50.   return r;
  51. }
  52.  
  53. lf go2(int mask) {
  54.   lf &r = dp[mask];
  55.   if(seen[mask]) return r;
  56.   seen[mask] = 1;
  57.   r = 0;
  58.   for(int d = 2; d <= 12; d++) {
  59.     bool f = 0;
  60.     lf aux = 0;
  61.     for(auto &m : moves[d]) {
  62.       if((mask & m) == m) {
  63.         f = 1;
  64.         aux = max(aux, go2(mask ^ m));
  65.       }
  66.     }
  67.     if(f) r += prob_d[d] * aux;
  68.     else r += prob_d[d] * to_double(to_str(mask));
  69.   }
  70.   return r;
  71. }
  72.  
  73. int main() {
  74.   ios::sync_with_stdio(0);
  75.   cin.tie(0);
  76.  
  77.   #ifdef LOCAL
  78.     freopen("input.txt", "r", stdin);
  79.   #else
  80.     #define endl '\n'
  81.   #endif // LOCAL
  82.  
  83.   for(int d1 = 1; d1 <= 6; d1++) {
  84.     for(int d2 = 1; d2 <= 6; d2++) {
  85.       prob_d[d1+d2]++;
  86.     }
  87.   }
  88.   for(int i = 2; i <= 12; i++) prob_d[i] /= 36.0;
  89.  
  90.   for(int m = 1; m < (1<<9); m++) {
  91.     int sum = 0;
  92.     for(int i = 0; i < 9; i++)
  93.       if(m >> i & 1)
  94.         sum += i+1;
  95.     if(sum >= 2 && sum <= 12)
  96.       moves[sum].push_back(m);
  97.   }
  98.  
  99.   cout << fixed << setprecision(5);
  100.  
  101.   string state; int d1, d2;
  102.   while(cin >> state >> d1 >> d2) {
  103.     int msk = 0;
  104.     for(int i = 0; i < state.size(); i++) msk |= (1<<(state[i]-'1'));
  105.  
  106.     memset(seen, 0, sizeof seen);
  107.     lf ans = 1e20;
  108.     int id = -1;
  109.     for(int i = 0; i < moves[d1+d2].size(); i++) {
  110.       if((msk & moves[d1+d2][i]) == moves[d1+d2][i]) {
  111.         lf cur = go(msk ^ moves[d1+d2][i]);
  112.         if(ans > cur) {
  113.           ans = cur;
  114.           id = moves[d1+d2][i];
  115.         }
  116.       }
  117.     }
  118.  
  119.     if(id == -1) cout << -1 << " " << to_double(state) << endl;
  120.     else cout << to_str(id) << " " << ans << endl;
  121.  
  122.     memset(seen, 0, sizeof seen);
  123.     ans = -1;
  124.     id = -1;
  125.     for(int i = 0; i < moves[d1+d2].size(); i++) {
  126.       if((msk & moves[d1+d2][i]) == moves[d1+d2][i]) {
  127.         lf cur = go2(msk ^ moves[d1+d2][i]);
  128.         if(ans < cur) {
  129.           ans = cur;
  130.           id = moves[d1+d2][i];
  131.         }
  132.       }
  133.     }
  134.  
  135.     if(id == -1) cout << -1 << " " << to_double(state) << endl;
  136.     else cout << to_str(id) << " " << ans << endl;
  137.   }
  138.  
  139.   return 0;
  140. }
Add Comment
Please, Sign In to add comment