Участник:Muradyan Armen/AADAGAME — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «C++ (gcc 8.3) https://www.spoj.com/problems/ADAGAME/ <code-cpp> #include <iostream> #include <cstring> #include <cmath> using namespace std; const int MAX =…»)
 
Строка 76: Строка 76:
  
 
</code-cpp>
 
</code-cpp>
 +
 +
 +
[[Участник:StasFomin|StasFomin]] 00:16, 17 декабря 2020 (MSK): Не проходит по времени. Пробовал несколько раз, разными компиляторами. Скорее всего проблема в алгоритме, не в мелочной оптимизации.
 +
 +
[[File:AADAGAME_2020-12-17_00-15-06_image0.png||800px]]

Версия 21:16, 16 декабря 2020

C++ (gcc 8.3)

https://www.spoj.com/problems/ADAGAME/

 
#include <iostream>
#include <cstring>
#include <cmath>
 
using namespace std;
 
const int MAX = 10005;
 
int T;
int turns;
int digits[4];
string number;
string dp[101][10][10][10][10];
 
string solve(int step, string number) {
    if (step > turns) {
        return number;
    }
    for (int i = 0; i < 4; i ++) {
        digits[i] = number[i] - '0';
    }
    string &result = dp[step][digits[0]][digits[1]][digits[2]][digits[3]];
    if (result != "-1") {
        return result;
    }
    if (step & 1) {
        result = "0000";
    }
    else {
        result = "9999";
    }
    for (int i = 0; i < 4; i ++) {
        string to = number;
        to[i] = (to[i] - '0' + 1) % 10 + '0';
        if (step & 1) {
            result = max(result, solve(step + 1, to));
        }
        else {
            result = min(result, solve(step + 1, to));
        }
    }
    return result;
}
 
int main() {
    cin >> T;
    while (T --) {
        for (int i = 1; i < 101; i ++) {
            for (int j = 0; j < 10; j ++) {
                for (int k = 0; k < 10; k ++) {
                    for (int q = 0; q < 10; q ++) {
                        for (int l = 0; l < 10; l ++) {
                            dp[i][j][k][q][l] = "-1";
                        }
                    }
                }
            }
        }
        cin >> number >> turns;
        if (solve(1, number) > number) {
            cout << "Ada" << endl;
        }
        else {
            cout << "Vinit" << endl;
        }
    }
 
    return 0;
}
 


StasFomin 00:16, 17 декабря 2020 (MSK): Не проходит по времени. Пробовал несколько раз, разными компиляторами. Скорее всего проблема в алгоритме, не в мелочной оптимизации.

AADAGAME 2020-12-17 00-15-06 image0.png