Fshl0

Untitled

Mar 23rd, 2022
1,094
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.60 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define pb push_back
  5.  
  6. using namespace std;
  7. typedef long long ll;
  8. typedef pair <int, int> pii;
  9.  
  10. #include <ext/pb_ds/assoc_container.hpp>
  11. #include <ext/pb_ds/tree_policy.hpp>
  12. using namespace __gnu_pbds;
  13.  
  14. #define ordered_set tree<pair<ll,int>, null_type,less<pair<ll,int>>, rb_tree_tag,tree_order_statistics_node_update>
  15.  
  16. const int INF = 1e8;
  17. const int mxN = 1e5 + 9;
  18. const int mxK = 500 + 9;
  19. const int MOD = 998244353;
  20.  
  21. void setIO (string s) {
  22.     freopen ((s + ".in").c_str(), "r", stdin);
  23.     freopen ((s + ".out").c_str(), "w", stdout);
  24.    
  25.     return;
  26. }
  27.  
  28. int A[15][15];
  29. double dp[15][15];
  30. //odd = go left
  31. //even = go right
  32.  
  33.  
  34. void miniMize (double& x, double y) {
  35.     x = min (x, y);
  36.    
  37.     return;
  38. }
  39.  
  40. vector <pii> getNext (int x, int y) {
  41.     vector <pii> v;
  42.     for (int i = 0; i < 6; i++) {
  43.         if (x & 1) {
  44.             if (y == 1) {
  45.                 x--;
  46.             } else {
  47.                 y--;
  48.             }
  49.         } else {
  50.             if (y == 10) {
  51.                 x--;
  52.             } else {
  53.                 y++;
  54.             }
  55.         }
  56.        
  57.         if (x >= 1)
  58.             v.pb ({x, y});
  59.         else break;
  60.     }
  61.    
  62.     return v;
  63. }
  64.  
  65. void solve () {
  66.     for (int i = 1; i <= 10; i++) {
  67.         for (int j = 1; j <= 10; j++) {
  68.             cin >> A[i][j];
  69.             dp[i][j] = INF;
  70.         }
  71.     }
  72.    
  73.     dp[10][1] = 0;
  74.     double p = 1 / (6.0);
  75.    
  76.     for (int i = 10; i >= 1; i--) {
  77.         if (i & 1) {
  78.             for (int j = 10; j >= 1; j--) {
  79.                 if (i == 1 && j == 1)
  80.                     break;
  81.                                
  82.                 if (i == 1 && j <= 6) {
  83.                     vector <pii> v = getNext (i, j);
  84.                     int out = 6 - v.size();
  85.                    
  86.                     for (auto [x, y]: v)
  87.                         miniMize (dp[x][y], p * (dp[i][j] + 1));
  88.                    
  89.                     //p2 = out/6, q = (1 - out/6) = (6 - out)/6
  90.                     //dp[s] = val + p2 * dp[s]
  91.                     //dp[s] - p2 * dp[s] = val
  92.                     //dp[s] x (1 - p2) = val
  93.                     //dp[s] = val / q = (val * 6) / 6 - out
  94.                    
  95.                     dp[i][j] = (dp[i][j] * 6.0) / (6.0 - out + 0.0);
  96.                     continue;
  97.                 }
  98.                
  99.                 vector <pii> v = getNext (i, j);
  100.                 for (auto [x, y]: v)
  101.                     miniMize (dp[x][y], p * (dp[i][j] + 1));
  102.                
  103.                 if (A[i][j] > 0)
  104.                     miniMize (dp[i + A[i][j]][j], dp[i][j]);
  105.             }
  106.            
  107.         } else {
  108.             for (int j = 1; j <= 10; j++) {
  109.                 vector <pii> v = getNext (i, j);
  110.                 for (auto [x, y]: v)
  111.                     miniMize (dp[x][y], p * (dp[i][j] + 1));
  112.                
  113.                 if (A[i][j] > 0)
  114.                     miniMize (dp[i + A[i][j]][j], dp[i][j]);
  115.             }
  116.         }
  117.     }
  118.    
  119.     vector <pii> v = getNext (1, 3);
  120.     for (auto [x, y]: v)
  121.         cout << x << ' ' << y << "\n";
  122.    
  123.     cout << dp[1][1] << "\n";
  124.     return;
  125. }
  126.  
  127. int main () {
  128.     int t = 1;
  129.     //cin >> t;
  130.    
  131.     //setIO ("deleg");
  132.     //preCalc ();
  133.     while (t--) {
  134.         //initialize common variables
  135.        
  136.        
  137.         //go solve
  138.         solve ();
  139.     }
  140.        
  141.     return 0;
  142. }
  143.  
Advertisement
Add Comment
Please, Sign In to add comment