Участник: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 =…»)
 
 
(не показаны 2 промежуточные версии 2 участников)
Строка 5: Строка 5:
 
<code-cpp>
 
<code-cpp>
  
#include <iostream>
+
#include "bits/stdc++.h"
#include <cstring>
+
#include <cmath>
+
 
+
 
using namespace std;
 
using namespace std;
 +
 +
string ori;
 +
int iter;
 +
 +
int dp[10001][101];
 +
 +
bool solve(string s,int i){
 +
if(i==iter){
 +
if(s>ori)return 1;
 +
return 0;
 +
}
 +
int z=stoi(s);
 +
if(dp[z][i]!=-1)return dp[z][i];
 +
bool ans=0;
 +
if(i&1){
 +
ans=1;
 +
}
 +
for(int k=0;k<4;k++){
 +
string tm=s;
 +
if(tm[k]=='9')tm[k]='0';
 +
else tm[k]++;
 +
if(i&1){
 +
ans&=solve(tm,i+1);
 +
}
 +
else {
 +
ans|=solve(tm,i+1);
 +
}
 +
}
 +
return dp[z][i]=ans;
 +
}
 +
 +
int main(){
 +
int t;
 +
string s;
 +
for(scanf("%d",&t);t--;){
 +
memset(dp,-1,sizeof dp);
 +
cin>>s;
 +
ori=s;
 +
scanf("%d",&iter);
 +
if(solve(s,0))printf("Ada\n");
 +
else printf("Vinit\n");
 +
}
 +
 +
</code-cpp>
  
const int MAX = 10005;
 
  
int T;
+
[[Участник:StasFomin|StasFomin]] 00:16, 17 декабря 2020 (MSK): Не проходит по времени. Пробовал несколько раз, разными компиляторами. Скорее всего проблема в алгоритме, не в мелочной оптимизации.
int turns;
+
int digits[4];
+
string number;
+
string dp[101][10][10][10][10];
+
  
string solve(int step, string number) {
+
[[Участник:Muradyan Armen|Muradyan Armen]] 15:02, 17 декабря 2020 (MSK) Проверьте пожалуйста этот вариант, у меня прошел!
    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() {
+
[[File:AADAGAME_2020-12-17_00-15-06_image0.png||800px]]
    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;
+
}
+
  
</code-cpp>
+
[[Участник:StasFomin|StasFomin]] 15:23, 17 декабря 2020 (MSK):  Ага, теперь ОК.

Текущая версия на 12:23, 17 декабря 2020

C++ (gcc 8.3)

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

 
#include "bits/stdc++.h"
using namespace std;
 
string ori;
int iter;
 
int dp[10001][101];
 
bool solve(string s,int i){
	if(i==iter){
		if(s>ori)return 1;
		return 0;
	}
	int z=stoi(s);
	if(dp[z][i]!=-1)return dp[z][i];
	bool ans=0;
	if(i&1){
		ans=1;
	}
	for(int k=0;k<4;k++){
		string tm=s;
		if(tm[k]=='9')tm[k]='0';
			else tm[k]++;
		if(i&1){
			ans&=solve(tm,i+1);
		}
		else {
			ans|=solve(tm,i+1);
		}
	}
	return dp[z][i]=ans;
}
 
int main(){
	int t;
	string s;
	for(scanf("%d",&t);t--;){
		memset(dp,-1,sizeof dp);
		cin>>s;
		ori=s;
		scanf("%d",&iter);
		if(solve(s,0))printf("Ada\n");
		else printf("Vinit\n");
	}
}  


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

Muradyan Armen 15:02, 17 декабря 2020 (MSK) Проверьте пожалуйста этот вариант, у меня прошел!

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

StasFomin 15:23, 17 декабря 2020 (MSK): Ага, теперь ОК.