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

Материал из DISCOPAL
Перейти к: навигация, поиск
 
Строка 58: Строка 58:
  
 
[[File:AADAGAME_2020-12-17_00-15-06_image0.png||800px]]
 
[[File:AADAGAME_2020-12-17_00-15-06_image0.png||800px]]
 +
 +
[[Участник: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): Ага, теперь ОК.