Cod sursa(job #3367600)

Utilizator Emre12Isleam Emre Emre12 Data 8 octombrie 2026 19:30:05
Problema Evaluarea unei expresii Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.47 kb
#include <algorithm>
#include <cstdio>
#include <cstring>

#define MAXA 51
#define MAXT 51
#define MAXX 101
#define INFINIT ((1 << 15) - 1)

short dp[MAXX][MAXT][MAXT][MAXT];
int T1, T2, T3, A1, A2, A3;

static inline short getMin(int x) {
  short min = INFINIT;
  for (int t2 = 0; t2 < T2; t2++)
    for (int t3 = 0; t3 < T3; t3++)
      min = std::min(dp[x][T1][t2][t3], min);
  for (int t1 = 0; t1 < T1; t1++)
    for (int t3 = 0; t3 < T3; t3++)
      min = std::min(dp[x][t1][T2][t3], min);
  for (int t1 = 0; t1 < T1; t1++)
    for (int t2 = 0; t2 < T2; t2++)
      min = std::min(dp[x][t1][t2][T3], min);
  return min;
}

int getSumMin(int minT, int x) {
  short min = INFINIT, s;
  for (int y = x; y < MAXX; y++) {
    for (int t2 = 0; t2 < T2; t2++)
      for (int t3 = 0; t3 < T3; t3++)
        if (dp[y][T1][t2][t3] == minT) {
          s = T1 * A1 + t2 * A2 + t3 * A3;
          min = std::min(min, s);
        }
    for (int t1 = 0; t1 < T1; t1++)
      for (int t3 = 0; t3 < T3; t3++)
        if (dp[y][t1][T2][t3] == minT) {
          s = t1 * A1 + T2 * A2 + t3 * A3;
          min = std::min(min, s);
        }
    for (int t1 = 0; t1 < T1; t1++)
      for (int t2 = 0; t2 < T2; t2++)
        if (dp[y][t1][t2][T3] == minT) {
          s = t1 * A1 + t2 * A2 + T3 * A3;
          min = std::min(min, s);
        }
  }
  return min;
}
int main() {
  FILE *fin, *fout;
  fin = fopen("rell.in", "r");
  fout = fopen("rell.out", "w");

  int q, i, x;
  int n1, n2, n3, nx;
  short min;
  short minvec[MAXX];
  int ultraBoss[MAXX];
  fscanf(fin, "%d%d%d%d%d%d%d", &A1, &A2, &A3, &T1, &T2, &T3, &q);
  memset(dp, 0x3f,
         sizeof(dp[0][0][0][0]) * MAXX * MAXT * MAXT *
             MAXT); // initializez dpu cu infinit
  dp[0][0][0][0] = 0;
  for (int x = 0; x < MAXX; x++) {
    for (int t1 = T1; t1 >= 0; t1--)
      for (int t2 = T2; t2 >= 0; t2--)
        for (int t3 = T3; t3 >= 0; t3--) {
          n1 = t1 - 1 < 0 ? 0 : t1 - 1;
          n2 = t2 - 1 < 0 ? 0 : t2 - 1;
          n3 = t3 - 1 < 0 ? 0 : t3 - 1;
          if (dp[x][n1][n2][n3] > dp[x][t1][t2][t3] + 1) // wait
            dp[x][n1][n2][n3] = dp[x][t1][t2][t3] + 1;
          if (t1 == 0) { // fol abilitatea A1
            nx = x + A1 > MAXX - 1
                     ? MAXX - 1
                     : x + A1; // damage dat daca dau si abilitatea A1
            if (dp[nx][T1][n2][n3] > dp[x][t1][t2][t3] + 1)
              dp[nx][T1][n2][n3] = dp[x][t1][t2][t3] + 1;
          }
          if (t2 == 0) { // fol abilitatea A2
            nx = x + A2 > MAXX - 1
                     ? MAXX - 1
                     : x + A2; // damage dat daca dau si abilitatea A1
            if (dp[nx][n1][T2][n3] > dp[x][t1][t2][t3] + 1)
              dp[nx][n1][T2][n3] = dp[x][t1][t2][t3] + 1;
          }
          if (t3 == 0) { // fol abilitatea A3
            nx = x + A3 > MAXX - 1
                     ? MAXX - 1
                     : x + A3; // damage dat daca dau si abilitatea A1
            if (dp[nx][n1][n2][T3] > dp[x][t1][t2][t3] + 1)
              dp[nx][n1][n2][T3] = dp[x][t1][t2][t3] + 1;
          }
        }
  }
  minvec[MAXX - 1] = getMin(MAXX - 1);
  ultraBoss[MAXX - 1] = getSumMin(minvec[MAXX - 1], MAXX - 1);
  for (i = MAXX - 2; i >= 1;
       i--) { // min vec( vectorul de minimi, pentru ca getmin calculeaza doar
              // timpu cel mai scurt pt exact x damage)
    minvec[i] = std::min(getMin(i), minvec[i + 1]);
  }
  for (i = 0; i < q; i++) {
    fscanf(fin, "%d", &x);
    fprintf(fout, "%d %d\n", minvec[x], getSumMin(minvec[x], x));
  }
}