diff options
| -rw-r--r-- | DP Solver | 156 | ||||
| -rw-r--r-- | dp_solver.cpp | 161 |
2 files changed, 161 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;*/ -} diff --git a/dp_solver.cpp b/dp_solver.cpp new file mode 100644 index 0000000..bbf6f41 --- /dev/null +++ b/dp_solver.cpp @@ -0,0 +1,161 @@ +#include <iostream> +#include <cstring> +#include <cmath> +using namespace std; +typedef long long ll; + +// DP Gimkit Solver +// Developed by SAMCHOOO + +// Initial conditions +ll start = 0, goal = 1e10; +int it = 150; + +// State: Iteration, Upgrade status, Power-up status +ll DP[200][1000][36]; + +// 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); } + +int main() { + memset(DP, -1, sizeof(DP)); + DP[0][0][0] = 0; + for (int i = 0; i < it; i++) { + for (int j = 0; j < 1000; j++) { + int MPQ = j / 100, SB = (j / 10) % 10, M = j % 10; + for (int k = 0; k < 36; k++) { + if (DP[i][j][k] != -1) { + int D = (j / 18) % 2, R = (j / 9) % 2, B1 = (j / 3) % 3, B2 = j % 3; + ll money = DP[i][j][k], inc = round((val[0][MPQ] + val[1][SB]) * val[2][M]); + + // Answer a question + if (money + inc > DP[i + 1][j][k]) { + DP[i + 1][j][k] = money + inc; + // pre[v] = u; + } + + // Answer a question using the mini bonus + if (B1 == 1 && 2 * money + inc > DP[i + 1][j][k + 3]) { + DP[i + 1][j][k + 3] = 2 * money + inc; + // pre[v] = u; + } + + // Answer a question using the mega bonus + if (B2 == 1 && 5 * money + inc > DP[i + 1][j][k + 1]) { + DP[i + 1][j][k + 1] = 5 * money + inc; + // pre[v] = u; + } + + // Answer a question using both the mini bonus and the mega bonus + if (B1 == 1 && B2 == 1 && 10 * money + inc > DP[i + 1][j][k + 4]) { + DP[i + 1][j][k + 4] = 10 * money + inc; + // pre[v] = u; + } + + // Upgrade money per question + if (MPQ < 9 && money - cost[D][0][MPQ + 1] > DP[i][j + 100][k]) { + DP[i][j + 100][k] = money - cost[D][0][MPQ + 1]; + // pre[v] = u; + } + + // Upgrade streak bonus + if (SB < 9 && money - cost[D][1][SB + 1] > DP[i][j + 10][k]) { + DP[i][j + 10][k] = money - cost[D][1][SB + 1]; + // pre[v] = u; + } + + // Upgrade multiplier + if (M < 9 && money - cost[D][2][M + 1] > DP[i][j + 1][k]) { + DP[i][j + 1][k] = money - cost[D][2][M + 1]; + // pre[v] = u; + } + + // Buy the discounter + if (D == 0 && money - calc_pcost(2, money) > DP[i][j][k + 18]) { + DP[i][j][k + 18] = money - calc_pcost(2, money); + // pre[v] = u; + } + + // Buy the rebooter + if (R == 0 && money - calc_pcost(3, money) > DP[i][j][9]) { + DP[i][j][9] = money - calc_pcost(3, money); + // pre[v] = u; + } + + // Buy the mini bonus + if (B1 == 0 && money - calc_pcost(0, money) > DP[i][j][k + 2]) { + DP[i][j][k + 2] = money - calc_pcost(0, money); + // pre[v] = u; + } + + // Buy the mega bonus + if (B2 == 0 && money - calc_pcost(1, money) > DP[i][j][k + 1]) { + DP[i][j][k + 1] = money - calc_pcost(1, money); + // pre[v] = u; + } + } + } + } + } + + // Find and print solution + for (int i = 0; i < it; i++) { + for (int j = 0; j < 1000; j++) { + // int MPQ = j / 100, SB = (j / 10) % 10, M = j % 10; + for (int k = 0; k < 36; k++) { + // int D = (k / 18) % 2, R = (k / 9) % 2, B1 = (k / 3) % 3, B2 = k % 3; + if (DP[i][j][k] > goal) { + cout << i << " " << j << " " << k << endl; + + /*for (state p = u; !(p == s); p = pre[p]) { + cout << p.MPQ << " " << p.SB << " " << p.M << " " << p.D << " " << p.R << " " << p.B1 << " " << p.B2 << endl; + }*/ + return 0; + } + } + } + } + + /*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;*/ +} + |