Update dp_solver.cpp

Still in development so expect bugs, also formatted output should be done soon

1 files changed, 106 insertions, 130 deletions

diff --git a/dp_solver.cpp b/dp_solver.cpp
index 129c7b9..cb4e21f 100644
--- a/dp_solver.cpp
+++ b/dp_solver.cpp
@@ -9,17 +9,31 @@ typedef long long ll;
 
 // Initial conditions
 ll start = 0, goal = 1e10;
-int it = 150;
+int max_it = 150; // Number of iterations to solve
+// int MPQ = 0, SB = 0, M = 0; // Initial upgrade status
+// int D, R, B1, B2; // Initial power-up status
 
 // State: Iteration, Upgrade status, Power-up status
-ll DP[200][1000][36], pre[7200000];
+ll DP[7200000], pre[7200000];
 
-// Upgrade values and costs
+// Return DP array element from state
+ll& get_DP(int it, int MPQ, int SB, int M, int D, int R, int B1, int B2) {
+    return DP[36000 * it + 3600 * MPQ + 360 * SB + 36 *M + 18 * D + 9 * R + 3 * B1 + B2];
+}
+
+// Return pre array element from state
+ll& get_pre(int it, int MPQ, int SB, int M, int D, int R, int B1, int B2) {
+    return pre[36000 * it + 3600 * MPQ + 360 * SB + 36 *M + 18 * D + 9 * R + 3 * B1 + B2];
+}
+
+// Upgrade values
 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 }
 };
+
+// Upgrade costs
 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 },
@@ -30,143 +44,105 @@ ll cost[2][3][10] = {
 };
 
 // Power-up costs
-int pcost[4] = { 250, 1000, 20, 50 };
-double pcentcost[4] = { 0.16, 0.30, 0.03, 0.06 };
-ll calc_pcost(int i, ll money) { return 5 * ceil((double)(pcentcost[i] * money + pcost[i]) / 5); }
+int base[4] = { 250, 1000, 20, 50 };
+double pcent[4] = { 0.16, 0.30, 0.03, 0.06 };
+ll pcost(int i, ll x) { return 5 * ceil((double)(pcent[i] * x + base[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 = (k / 18) % 2, R = (k / 9) % 2, B1 = (k / 3) % 3, B2 = k % 3;
-                    ll money = DP[i][j][k], inc = round((val[0][MPQ] + (i != 0 ? val[1][SB] : 0)) * val[2][M]);
-                    
-                    // Answer a question
-                    if (money + inc > DP[i + 1][j][k]) {
-                        DP[i + 1][j][k] = money + inc;
-                        pre[36000 * (i + 1) + 36 * j + k] = 36000 * i + 36 * j + k;
-                    }
-                    
-                    // Answer a question using the mini bonus
-                    if (B1 == 1 && money + 2 * inc > DP[i + 1][j][k + 3]) {
-                        DP[i + 1][j][k + 3] = money + 2 * inc;
-                        pre[36000 * (i + 1) + 36 * j + k + 3] = 36000 * i + 36 * j + k;
-                    }
-                    
-                    // Answer a question using the mega bonus
-                    if (B2 == 1 && money + 5 * inc > DP[i + 1][j][k + 1]) {
-                        DP[i + 1][j][k + 1] = money + 5 * inc;
-                        pre[36000 * (i + 1) + 36 * j + k + 1] = 36000 * i + 36 * j + k;
-                    }
-                    
-                    // Answer a question using both the mini bonus and the mega bonus
-                    if (B1 == 1 && B2 == 1 && money + 10 * inc > DP[i + 1][j][k + 4]) {
-                        DP[i + 1][j][k + 4] = money + 10 * inc;
-                        pre[36000 * (i + 1) + 36 * j + k + 4] = 36000 * i + 36 * j + k;
-                    }
-                    
-                    // Upgrade money per question
-                    int l = MPQ;
-                    while (++l < 10 && money >= cost[D][0][l]) {
-                        if (money - cost[D][0][l] > DP[i][j + 100 * (l - MPQ)][k]) {
-                            DP[i][j + 100 * (l - MPQ)][k] = money - cost[D][0][l];
-                            pre[36000 * i + 36 * (j + 100 * (l - MPQ)) + k] = 36000 * i + 36 * j + k;
-                        }
-                    }
-                    
-                    // Upgrade streak bonus
-                    l = SB;
-                    while (++l < 10 && money >= cost[D][1][l]) {
-                        if (money - cost[D][1][l] > DP[i][j + 10 * (l - SB)][k]) {
-                            DP[i][j + 10 * (l - SB)][k] = money - cost[D][1][l];
-                            pre[36000 * i + 36 * (j + 10 * (l - SB)) + k] = 36000 * i + 36 * j + k;
-                        }
-                    }
-                    
-                    // Upgrade multiplier
-                    l = M;
-                    while (++l < 10 && money >= cost[D][2][l]) {
-                        if (money - cost[D][2][l] > DP[i][j + l - M][k]) {
-                            DP[i][j + l - M][k] = money - cost[D][2][l];
-                            pre[36000 * i + 36 * (j + l - M) + k] = 36000 * i + 36 * j + k;
-                        }
-                    }
-                    
-                    // Buy the discounter
-                    if (D == 0 && money >= calc_pcost(0, money) && money - calc_pcost(0, money) > DP[i][j][k + 18]) {
-                        DP[i][j][k + 18] = money - calc_pcost(0, money);
-                        pre[36000 * i + 36 * j + k + 18] = 36000 * i + 36 * j + k;
-                    }
-                    
-                    // Buy the rebooter
-                    if (R == 0 && money >= calc_pcost(1, money) && money - calc_pcost(1, money) > DP[i][j][9]) {
-                        DP[i][j][9] = money - calc_pcost(1, money);
-                        pre[36000 * i + 36 * j + 9] = 36000 * i + 36 * j + k;
-                    }
-                    
-                    // Buy the mini bonus
-                    if (B1 == 0 && money >= calc_pcost(2, money) && money - calc_pcost(2, money) > DP[i][j][k + 2]) {
-                        DP[i][j][k + 2] = money - calc_pcost(2, money);
-                        pre[36000 * i + 36 * j + k + 2] = 36000 * i + 36 * j + k;
-                    }
-                    
-                    // Buy the mega bonus
-                    if (B2 == 0 && money >= calc_pcost(3, money) && money - calc_pcost(3, money) > DP[i][j][k + 1]) {
-                        DP[i][j][k + 1] = money - calc_pcost(3, money);
-                        pre[36000 * i + 36 * j + k + 1] = 36000 * i + 36 * j + k;
-                    }
+    
+    get_DP(0, 0, 0, 0, 0, 0, 0, 0) = start;
+    for (int i = 0; i < 36000 * max_it; i++) {
+        if (DP[i] != -1) {
+            int it = i / 36000;
+            int MPQ = (i / 3600) % 10, SB = (i / 360) % 10, M = (i / 36) % 10;
+            int D = (i / 18) % 2, R = (i / 9) % 2, B1 = (i / 3) % 3, B2 = i % 3;
+            ll inc = round((val[0][MPQ] + (i != 0 ? val[1][SB] : 0)) * val[2][M]);
+            
+            // Answer a question
+            if (DP[i] + inc > DP[i + 36000]) {
+                DP[i + 36000] = DP[i] + inc;
+                pre[i + 36000] = i;
+            }
+            
+            // Answer a question using the mini bonus
+            if (B1 == 1 && DP[i] + 2 * inc > DP[i + 36003]) {
+                DP[i + 36003] = DP[i] + 2 * inc;
+                pre[i + 36003] = i;
+            }
+            
+            // Answer a question using the mega bonus
+            if (B2 == 1 && DP[i] + 5 * inc > DP[i + 36001]) {
+                DP[i + 36001] = DP[i] + 5 * inc;
+                pre[i + 36001] = i;
+            }
+            
+            // Answer a question using both the mini bonus and the mega bonus
+            if (B1 == 1 && B2 == 1 && DP[i] + 10 * inc > DP[i + 36004]) {
+                DP[i + 36004] = DP[i] + 10 * inc;
+                pre[i + 36004] = i;
+            }
+            
+            // Upgrade money per question
+            for (int j = MPQ + 1; j < 10 && DP[i] >= cost[D][0][j]; j++) {
+                if (DP[i] - cost[D][0][j] > DP[i + 3600 * (j - MPQ)]) {
+                    DP[i + 3600 * (j - MPQ)] = DP[i] - cost[D][0][j];
+                    pre[i + 3600 * (j - MPQ)] = i;
                 }
             }
-        }
-    }
-    
-    // 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) {
-                    for (int p = 36000 * i + 36 * j + k; p != 0; p = pre[p]) {
-                        int a = p / 36000, b = (p / 36) % 1000, c = p % 36;
-                        cout << DP[a][b][c] << " " << a << " " << b << " " << c << 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;
+            
+            // Upgrade streak bonus
+            for (int j = SB + 1; j < 10 && DP[i] >= cost[D][1][j]; j++) {
+                if (DP[i] - cost[D][1][j] > DP[i + 360 * (j - SB)]) {
+                    DP[i + 360 * (j - SB)] = DP[i] - cost[D][1][j];
+                    pre[i + 360 * (j - SB)] = i;
+                }
+            }
+            
+            // Upgrade streak bonus
+            for (int j = M + 1; j < 10 && DP[i] >= cost[D][2][j]; j++) {
+                if (DP[i] - cost[D][2][j] > DP[i + 36 * (j - M)]) {
+                    DP[i + 36 * (j - M)] = DP[i] - cost[D][2][j];
+                    pre[i + 36 * (j - M)] = i;
                 }
             }
+            
+            // Buy the discounter
+            if (D == 0 && DP[i] - pcost(0, DP[i]) > DP[i + 18]) {
+                DP[i + 18] = DP[i] - pcost(0, DP[i]);
+                pre[i + 18] = i;
+            }
+            
+            // Buy the rebooter
+            if (R == 0 && DP[i] - pcost(1, DP[i]) > DP[i - i % 36 + 9]) {
+                DP[i - i % 36 + 9] = DP[i] - pcost(1, DP[i]);
+                pre[i - i % 36 + 9] = i;
+            }
+            
+            // Buy the mini bonus
+            if (B1 == 0 && DP[i] - pcost(2, DP[i]) > DP[i + 2]) {
+                DP[i + 2] = DP[i] - pcost(2, DP[i]);
+                pre[i + 2] = i;
+            }
+            
+            // Buy the mega bonus
+            if (B2 == 0 && DP[i] - pcost(3, DP[i]) > DP[i + 1]) {
+                DP[i + 1] = DP[i] - pcost(3, DP[i]);
+                pre[i + 1] = i;
+            }
         }
     }
     
-    /*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]]));
+    for (int i = 0; i < 36000 * max_it; i++) {
+        if (DP[i] >= goal) {
+            for (int j = i; j != 0; j = pre[j]) {
+                int it = j / 36000;
+                int MPQ = (j / 3600) % 10, SB = (j / 360) % 10, M = (j / 36) % 10;
+                int D = (j / 18) % 2, R = (j / 9) % 2, B1 = (j / 3) % 3, B2 = j % 3;
+                cout << DP[j] << " " << it << " " << MPQ << " " << SB << " " << M << " " << D << " " << R << " " << B1 << " " << B2 << endl;
+            }
+            return 0;
         }
-        cout << " Number of questions: " << DP[output[i]] - DP[output[i - 1]] << endl;    
     }
-    cout << "Total questions: " << DP[999] + 2 << endl;*/
 }