pinboool_dp.cpp

#include<bits/stdc++.h>
#define XX first
#define YY second
#define pb emplace_back
#define eb pb
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define EFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define rep(i,b) FOR(i,0,b)
#define REP rep
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define reps FOR
#define rreps(i,a,b) for (int i=int(b)-1;i>=(a);--i)
#define rrep(i,b) rreps(i,0,b)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
const ll MOD=1e9+7;

#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}

unsigned int rand(unsigned int *state) {
  *state = 214013 * *state + 2531011;
  return (*state >> 16) & 0x7FFF;
}

using Tup = tuple<int, int, int, int>;

// i, rand_state, r, cur_tilt
int dp[4][154][154][154];
Tup trace[4][154][154][154]; 
bool processed[4][154][154][154]; 
int aug[4][154][154][154][3];
int rs[514];
int bump[114];

void Update(int a, int b, int c, int d, int e, int f, int g, int h, int v, int p, int q, int r) {
  assert(!processed[a][b][c][d]);
  if (MN(dp[a][b][c][d], dp[e][f][g][h]+v)) {
    trace[a][b][c][d] = Tup(e,f,g,h);
    aug[a][b][c][d][0] = p;
    aug[a][b][c][d][1] = q;
    aug[a][b][c][d][2] = r;
  }
}

signed main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);

  unsigned int st = 1930;
  rep(i, 514) {
    rs[i] = rand(&st) % 100;
  }

  rep(s, 101) {
    int ns = s+1;
    while (rs[ns] > 0x31) {
      ns += 2;
    }
    bump[s] = ns+1;
    //cout << s << ": " << ns << endl;
  }

  const int INF = MOD;
  fill(dp[0][0][0], dp[4][0][0], INF);

  rep(i, 60) {
    dp[0][i+1][rs[i]][0] = i*10;
  }
  dp[0][1][rs[0]][0] = 0;
  int cnt = 0;
  rep(i, 3) {
    rep(s, 111) {
      rep(r, 111) {
        rep(c, 111) {
          cnt++;
          if (cnt % 1000000 == 0) {
            cout << "cnt=" << cnt << ": " << i << ", " << s << ", " << r << ", " << c << endl;
          }

          processed[i][s][r][c] = 1;
          if (dp[i][s][r][c] == INF) continue;

          // 2
          {
            int v29 = rs[s];
            
            if (v29 > 0 && !(0x23 < r && r <= 0x4a)) {
              Update(i, s+1, r, c,  i, s, r, c, 12,  2, 0, 0);
            }

            if (i == 0 && s == 1 && rs[0] == r && c == 0) cout << "V29: " << v29 << endl;
            reps(v17, v29+1, 100-c) {
              if (r <= 0x31) {
                reps(nr, 10, r) {
                  Update(i, s+1, nr, c+v17,  i, s, r, c, 12,  2, v17, r-nr);
                }
              } else if (r <= 0x64) {
                reps(nr, r, 91) {
                  Update(i, s+1, nr, c+v17,  i, s, r, c, 12,  2, v17, nr-r);
                }
              }
            }
          }

          // 3
          if (r <= 0x23) {
            Update(i, s+1, rs[s], c,  i, s, r, c, 15,  3, 0, 0);
          }

          // 4 
          if (r == 0x23 || (0x40 < r && r <= 0x64)) {
            int ns = bump[s];
            int sz = 10;
            if (i == 0) sz = 530;
            if (i == 1) sz = 15;
            Update(i+1, ns+1, rs[ns], c,  i, s, r, c, sz,  4, 0, 0);
          }
        }
      }
    }
  }
  cout << "done" << endl;

  using Pair = pair<int, Tup>;
  Pair mn(INF, Tup(0, 0, 0, 0));
  rep(s, 101) {
    rep(r, 101) {
      rep(c, 101) {
        MN(mn, Pair(dp[3][s][r][c], Tup(3, s, r, c)));
      }
    }
  }
  cout << "ans: " << mn.XX << endl;

  vector<string> outputs;
  auto args = mn.YY;
  while (1) {
    int a, b, c, d;
    tie(a, b, c, d) = args;
    if (trace[a][b][c][d] == Tup(0, 0, 0, 0)) break;

    args = trace[a][b][c][d];
    int cmd = aug[a][b][c][d][0];
    stringstream ss;
    ss << "cmd=" << cmd;
    if (cmd == 2) ss << ", arg1=0x" << hex << aug[a][b][c][d][1] << ", arg2=0x" << aug[a][b][c][d][2];
    if (cmd == 3) ss << ", arg1=QQQQ\\x00";
    if (cmd == 4) ss << ", arg1=520bytes";
    ss << "\nresulting in state=" << dec << b << ", r=0x" << hex << c << ", cur_tilt=" << dec << d << "\n";
    outputs.eb(ss.str());
  }
  reverse(all(outputs));

  {
    int a, b, c, d;
    tie(a, b, c, d) = args;
    cout << "first:" << dec << b << ", r=0x" << hex << c << ", cur_tilt=" << dec << d << "\n";
  }
  for (auto &output : outputs) {
    cout << output;
  }
}