Muteki.cpp

#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <ctime>
#include <vector>
#include <valarray>
#include <string>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>

using namespace std;
typedef long long ll;

const int D = 54;
int price[D][3];

double dp[D];
bool used[D];
bool bf[D];
int bi[D], bj[D];

double solve(int d) {
    if (d == D) return 1;
    if (used[d]) return dp[d];
    used[d] = true;
    double ma = solve(d+1);
    bf[d] = false;
    for (int i = 0; i < 3; i++) {
        for (int j = d+1; j < D; j++) {
            if (ma < ((double)price[j][i] / price[d][i]) * solve(j+1)) {
                bf[d] = true;
                bi[d] = i;
                bj[d] = j;
                ma = ((double)price[j][i] / price[d][i]) * solve(j+1);
            }
        }
    }
    return dp[d] = ma;
}


int senf[D];
int seni[D], num[D];

int main() {
    int t;
    scanf("%d", &t);
    srand(t);
    price[0][0] = price[0][1] = price[0][2] = 10000;
    for (int i = 1; i < D; i++) {
        for (int j = 0; j < 3; j++) {
            price[i][j] = price[i-1][j] + (rand() % 2001) - 1000;
            price[i][j] = max(price[i][j], 5000);
            price[i][j] = min(price[i][j], 15000);
        }
    }
    solve(1);
    int d = 1;
    int mo = 1000000;
    double sm = 1;
    while (d < D) {
        if (!bf[d]) {
            d = d+1;
            continue;
        }
        int pra = price[d][bi[d]];
        int prb = price[bj[d]][bi[d]];
        sm *= (double)prb / pra;
        int n = mo / price[d][bi[d]];
        mo -= n*pra;
        mo += n*prb;
        senf[d] = 1;
        senf[bj[d]] = 2;
        seni[d] = seni[bj[d]] = bi[d]+1;
        num[d] = num[bj[d]] = n;

        d = bj[d]+1;
    }
    for (int d = 1; d < D; d++) {
        printf("%d: ", d+1);
        if (senf[d] == 0) {
            printf("Rest\n");
        } else if (senf[d] == 1) {
            printf("Buy %d %d (%d)\n", seni[d], num[d], price[d][seni[d]-1]);
        } else {
            printf("Sell %d %d\n", seni[d], num[d]);
        }
    }
    printf("result %d %lf\n", mo, sm);
    return 0;
}