Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define F first
- #define S second
- #define pb push_back
- using namespace std;
- typedef long long ll;
- typedef pair <int, int> pii;
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace __gnu_pbds;
- #define ordered_set tree<pair<ll,int>, null_type,less<pair<ll,int>>, rb_tree_tag,tree_order_statistics_node_update>
- const int INF = 1e8;
- const int mxN = 1e5 + 9;
- const int mxK = 500 + 9;
- const int MOD = 998244353;
- void setIO (string s) {
- freopen ((s + ".in").c_str(), "r", stdin);
- freopen ((s + ".out").c_str(), "w", stdout);
- return;
- }
- int A[15][15];
- double dp[15][15];
- //odd = go left
- //even = go right
- void miniMize (double& x, double y) {
- x = min (x, y);
- return;
- }
- vector <pii> getNext (int x, int y) {
- vector <pii> v;
- for (int i = 0; i < 6; i++) {
- if (x & 1) {
- if (y == 1) {
- x--;
- } else {
- y--;
- }
- } else {
- if (y == 10) {
- x--;
- } else {
- y++;
- }
- }
- if (x >= 1)
- v.pb ({x, y});
- else break;
- }
- return v;
- }
- void solve () {
- for (int i = 1; i <= 10; i++) {
- for (int j = 1; j <= 10; j++) {
- cin >> A[i][j];
- dp[i][j] = INF;
- }
- }
- dp[10][1] = 0;
- double p = 1 / (6.0);
- for (int i = 10; i >= 1; i--) {
- if (i & 1) {
- for (int j = 10; j >= 1; j--) {
- if (i == 1 && j == 1)
- break;
- if (i == 1 && j <= 6) {
- vector <pii> v = getNext (i, j);
- int out = 6 - v.size();
- for (auto [x, y]: v)
- miniMize (dp[x][y], p * (dp[i][j] + 1));
- //p2 = out/6, q = (1 - out/6) = (6 - out)/6
- //dp[s] = val + p2 * dp[s]
- //dp[s] - p2 * dp[s] = val
- //dp[s] x (1 - p2) = val
- //dp[s] = val / q = (val * 6) / 6 - out
- dp[i][j] = (dp[i][j] * 6.0) / (6.0 - out + 0.0);
- continue;
- }
- vector <pii> v = getNext (i, j);
- for (auto [x, y]: v)
- miniMize (dp[x][y], p * (dp[i][j] + 1));
- if (A[i][j] > 0)
- miniMize (dp[i + A[i][j]][j], dp[i][j]);
- }
- } else {
- for (int j = 1; j <= 10; j++) {
- vector <pii> v = getNext (i, j);
- for (auto [x, y]: v)
- miniMize (dp[x][y], p * (dp[i][j] + 1));
- if (A[i][j] > 0)
- miniMize (dp[i + A[i][j]][j], dp[i][j]);
- }
- }
- }
- vector <pii> v = getNext (1, 3);
- for (auto [x, y]: v)
- cout << x << ' ' << y << "\n";
- cout << dp[1][1] << "\n";
- return;
- }
- int main () {
- int t = 1;
- //cin >> t;
- //setIO ("deleg");
- //preCalc ();
- while (t--) {
- //initialize common variables
- //go solve
- solve ();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment