Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef long double lf;
- typedef pair<int, int> pii;
- const int MAXN = 1e6+100;
- const int INF = 1e9+100;
- const int MOD = 1e9+9;
- lf prob_d[15], dp[(1<<9)+10];
- int seen[(1<<9)+10];
- vector<int> moves[15];
- lf to_double(string s) {
- stringstream ss;
- ss << s;
- lf x; ss >> x;
- return x;
- }
- string to_str(int msk) {
- string ans;
- for(int i = 0; i < 9; i++) {
- if(msk >> i & 1) ans.push_back(char(i+1+'0'));
- }
- if(ans.size() == 0) ans.push_back('0');
- return ans;
- }
- lf go(int mask) {
- lf &r = dp[mask];
- if(seen[mask]) return r;
- seen[mask] = 1;
- r = 0;
- for(int d = 2; d <= 12; d++) {
- bool f = 0;
- lf aux = 1e20;
- for(auto &m : moves[d]) {
- if((mask & m) == m) {
- f = 1;
- aux = min(aux, go(mask ^ m));
- }
- }
- if(f) r += prob_d[d] * aux;
- else r += prob_d[d] * to_double(to_str(mask));
- }
- return r;
- }
- lf go2(int mask) {
- lf &r = dp[mask];
- if(seen[mask]) return r;
- seen[mask] = 1;
- r = 0;
- for(int d = 2; d <= 12; d++) {
- bool f = 0;
- lf aux = 0;
- for(auto &m : moves[d]) {
- if((mask & m) == m) {
- f = 1;
- aux = max(aux, go2(mask ^ m));
- }
- }
- if(f) r += prob_d[d] * aux;
- else r += prob_d[d] * to_double(to_str(mask));
- }
- return r;
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- #else
- #define endl '\n'
- #endif // LOCAL
- for(int d1 = 1; d1 <= 6; d1++) {
- for(int d2 = 1; d2 <= 6; d2++) {
- prob_d[d1+d2]++;
- }
- }
- for(int i = 2; i <= 12; i++) prob_d[i] /= 36.0;
- for(int m = 1; m < (1<<9); m++) {
- int sum = 0;
- for(int i = 0; i < 9; i++)
- if(m >> i & 1)
- sum += i+1;
- if(sum >= 2 && sum <= 12)
- moves[sum].push_back(m);
- }
- cout << fixed << setprecision(5);
- string state; int d1, d2;
- while(cin >> state >> d1 >> d2) {
- int msk = 0;
- for(int i = 0; i < state.size(); i++) msk |= (1<<(state[i]-'1'));
- memset(seen, 0, sizeof seen);
- lf ans = 1e20;
- int id = -1;
- for(int i = 0; i < moves[d1+d2].size(); i++) {
- if((msk & moves[d1+d2][i]) == moves[d1+d2][i]) {
- lf cur = go(msk ^ moves[d1+d2][i]);
- if(ans > cur) {
- ans = cur;
- id = moves[d1+d2][i];
- }
- }
- }
- if(id == -1) cout << -1 << " " << to_double(state) << endl;
- else cout << to_str(id) << " " << ans << endl;
- memset(seen, 0, sizeof seen);
- ans = -1;
- id = -1;
- for(int i = 0; i < moves[d1+d2].size(); i++) {
- if((msk & moves[d1+d2][i]) == moves[d1+d2][i]) {
- lf cur = go2(msk ^ moves[d1+d2][i]);
- if(ans < cur) {
- ans = cur;
- id = moves[d1+d2][i];
- }
- }
- }
- if(id == -1) cout << -1 << " " << to_double(state) << endl;
- else cout << to_str(id) << " " << ans << endl;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment