Участник:Muradyan Armen/AADAGAME

Материал из DISCOPAL
< Участник:Muradyan Armen
Версия от 12:23, 17 декабря 2020; StasFomin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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): Ага, теперь ОК.