aboutsummaryrefslogtreecommitdiff
path: root/DP Solver
diff options
context:
space:
mode:
Diffstat (limited to 'DP Solver')
-rw-r--r--DP Solver156
1 files changed, 0 insertions, 156 deletions
diff --git a/DP Solver b/DP Solver
deleted file mode 100644
index c961518..0000000
--- a/DP Solver
+++ /dev/null
@@ -1,156 +0,0 @@
-#include <iostream>
-#include <cmath>
-using namespace std;
-typedef long long ll;
-
-// DP Gimkit Solver
-// Developed by SAMCHOOO
-
-// Initial conditions
-ll start = 0, goal = 1e10; // Money status
-int MPQ = 0, SB = 0, M = 0; // Upgrade status
-int D = 0, R = 0, B1 = 0, B2 = 0; // Power-up status
-
-// DP state: Iteration, upgrade status, power-up status
-ll DP[200][1000][9][4] = { 0 };
-
-// Reconstruct paths
-int pre[7200000];
-int path_hash(int it, int i, int j, int k) {
- return 36000 * it + 36 * i + 4 * j + k;
-}
-
-// Upgrade values and costs
-double val[3][10] = {
- { 1, 5, 50, 100, 500, 2000, 5000, 10000, 250000, 1000000 },
- { 2, 20, 100, 200, 1000, 4000, 10000, 50000, 1000000, 5000000 },
- { 1, 1.5, 2, 3, 5, 8, 12, 18, 30, 100 }
-};
-ll cost[2][3][10] = {
- { { 0, 10, 100, 1000, 10000, 75000, 300000, 1000000, 10000000, 100000000},
- { 0, 15, 150, 1500, 15000, 115000, 450000, 1500000, 15000000, 200000000 },
- { 0, 50, 300, 2000, 12000, 85000, 700000, 6500000, 65000000, 1000000000 } },
- { { 0, 8, 75, 750, 7500, 56250, 225000, 750000, 7500000, 75000000 },
- { 0, 12, 113, 1125, 11250, 86250, 337500, 1125000, 11250000, 150000000 },
- { 0, 38, 225, 1500, 9000, 63750, 525000, 4875000, 48750000, 750000000 } }
-};
-
-// Power-up costs
-int pcost[4] = { 20, 50, 250, 1000 };
-double pcentcost[4] = { 0.03, 0.06, 0.16, 0.30 };
-ll calc_pcost(int i, ll money) { return 5 * ceil((double)(pcentcost[i] * money + pcost[i]) / 5); }
-
-// Utility function for printing the optimal solution
-/*string format_int(int x) {
- string ret = to_string(x);
- int pos = ret.length() - 3;
- while (pos > 0) {
- ret.insert(pos, ",");
- pos -= 3;
- }
- return ret;
-}*/
-
-int main() {
- int s = path_hash(0, 100 * MPQ + 10 * SB + M, 2 * D + R, 3 * B1 + B2);
- DP[0][100 * MPQ + 10 * SB + M][2 * D + R][3 * B1 + B2] = start;
- for (int it = 0; it < 200; it++) {
- for (int i = 0; i < 1000; i++) {
- MPQ = i / 100, SB = (i / 10) % 10, M = i % 10;
- for (int j = 0; j < 4; j++) {
- D = j / 2, R = j % 2;
- for (int k = 0; k < 9; k++) {
- B1 = k / 3, B2 = k % 3;
- ll money = DP[it][i][j][k];
- ll inc = round((val[0][MPQ] + val[1][SB]) * val[2][M]);
-
- if (money + inc > DP[it + 1][i][j][k]) {
- DP[it + 1][i][j][k] = money + inc;
- pre[path_hash(it + 1, i, j, k)] = path_hash(it, i, j, k);
- }
- if (B1 == 1 && 2 * money + inc > DP[it + 1][i][j][k + 3]) {
- DP[it + 1][i][j][k + 3] = 2 * money + inc;
- pre[path_hash(it + 1, i, j, k + 3)] = path_hash(it, i, j, k);
- }
- if (B2 == 1 && 5 * money + inc > DP[it + 1][i][j][k + 1]) {
- DP[it + 1][i][j][k + 1] = 5 * money + inc;
- pre[path_hash(it + 1, i, j, k + 1)] = path_hash(it, i, j, k);
- }
- if (B1 == 1 && B2 == 1 && 10 * money + inc > DP[it + 1][i][j][k + 4]) {
- DP[it + 1][i][j][k + 4] = 10 * money + inc;
- pre[path_hash(it + 1, i, j, k + 4)] = path_hash(it, i, j, k);
- }
-
- if (MPQ < 9 && money - cost[D][0][MPQ + 1] > DP[it][i + 100][j][k]) {
- DP[it][i + 100][j][k] = money - cost[D][0][MPQ + 1];
- pre[path_hash(it, i + 100, j, k)] = path_hash(it, i, j, k);
- }
- if (SB < 9 && money - cost[D][1][SB + 1] > DP[it][i + 10][j][k]) {
- DP[it][i + 10][j][k] = money - cost[D][1][SB + 1];
- pre[path_hash(it, i + 10, j, k)] = path_hash(it, i, j, k);
- }
- if (MPQ < 9 && money - cost[D][2][M + 1] > DP[it][i + 1][j][k]) {
- DP[it][i + 1][j][k] = money - cost[D][2][M + 1];
- pre[path_hash(it, i + 1, j, k)] = path_hash(it, i, j, k);
- }
-
- if (B1 == 0 && money - calc_pcost(0, money) > DP[it][i][j][k + 3]) {
- DP[it][i][j][k + 3] = money - calc_pcost(0, money);
- pre[path_hash(it, i, j, k + 3)] = path_hash(it, i, j, k);
- }
- if (B2 == 0 && money - calc_pcost(1, money) > DP[it][i][j][k + 1]) {
- DP[it][i][j][k + 1] = money - calc_pcost(1, money);
- pre[path_hash(it, i, j, k + 1)] = path_hash(it, i, j, k);
- }
-
- if (D == 0 && money - calc_pcost(2, money) > DP[it][i][j + 2][k]) {
- DP[it][i][j + 2][k] = money - calc_pcost(2, money);
- pre[path_hash(it, i, j + 2, k)] = path_hash(it, i, j, k);
- }
- if (R == 0 && money - calc_pcost(3, money) > DP[it][i][1][0]) {
- DP[it][i][1][0] = money - calc_pcost(3, money);
- pre[path_hash(it, i, 0, 1)] = path_hash(it, i, j, k);
- }
- }
- }
- }
- }
-
- // Find and print solution
- for (int it = 0; it < 200; it++) {
- for (int i = 0; i < 1000; i++) {
- for (int j = 0; j < 9; j++) {
- for (int k = 0; k < 4; k++) {
- if (DP[it][i][j][k] > goal) {
- for (int p = path_hash(it, i, j, k); p != s; p = pre[p]) cout << p << endl;
- }
- }
- }
- }
- }
-
- /*vector<int> output;
- for (int i = 999; i != 0; i = pre[i]) output.push_back(i);
- output.push_back(0);
- reverse(output.begin(), output.end());
-
- for (int i = 1; i < output.size(); i++) {
- if (output[i] / 100 != output[i - 1] / 100) {
- cout << left << setw(25) << ("Upgrade MPQ to L" + format_int(output[i] / 100 + 1));
- cout << left << setw(25) << (" Cost: " + format_int(cost[output[i] / 100][0]));
- // cout << left << setw(25) << (" Remainder: " + format_int(rem[output[i]]));
- }
- else if ((output[i] / 10) % 10 != (output[i - 1] / 10) % 10) {
- cout << left << setw(25) << ("Upgrade SB to L" + format_int((output[i] / 10) % 10 + 1));
- cout << left << setw(25) << (" Cost: " + format_int(cost[(output[i] / 10) % 10][1]));
- // cout << left << setw(25) << (" Remainder: " + format_int(rem[output[i]]));
- }
- else {
- cout << left << setw(25) << ("Upgrade M to L" + format_int(output[i] % 10 + 1));
- cout << left << setw(25) << (" Cost: " + format_int(cost[output[i] % 10][2]));
- // cout << left << setw(25) << (" Remainder: " + format_int(rem[output[i]]));
- }
- cout << " Number of questions: " << DP[output[i]] - DP[output[i - 1]] << endl;
- }
- cout << "Total questions: " << DP[999] + 2 << endl;*/
-}