fork(1) download
copy 
  1. # include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long 			ll;
  6. typedef pair<int,int>		ii;
  7. typedef pair<ll,ll>			LL;
  8. typedef vector<ii>			vii;
  9. typedef vector<LL>			vLL;
  10.  
  11. # define FAST				ios_base::sync_with_stdio(false);cin.tie(0);
  12.  
  13. # define mp(x,y)			make_pair(x,y)
  14. # define F					first
  15. # define S					second
  16. # define sii(p)				sd(p.F),sd(p.S)
  17. # define sLL(p)				sll(p.F),sll(p.S)
  18. # define stl(x)				x.begin(),x.end()
  19. # define stlr(x)			x.rbegin(),x.rend()
  20.  
  21. # define rep(i,a,b)			for(auto i = a; i < b; ++i)
  22. # define rrep(i,a,b) 		for(auto i = a; i > b ;--i)
  23. # define repstr(str,i) 		for(auto i = 0 ; str[i] ;++i)
  24. # define repstl(stl,l) 		for(auto l : stl) 
  25.  
  26. # define gets(str)			scanf("%s",str)
  27. # define gc()				getchar()
  28. # define pc(c)				putchar(c)
  29. # define nline				pc('\n')
  30. # define pd(x)				printf("%d",x)
  31. # define pll(x)				printf("%lld",x)
  32. void sd(int &n){
  33.  
  34. 	n = 0;
  35. 	int sign = +1;
  36. 	char ch;
  37.  
  38. 	while(isspace(ch = gc()));
  39.  
  40. 	if(isdigit(ch))
  41. 		n = ch - '0';
  42. 	else
  43. 		sign = ch == '+' ? +1 : -1;
  44.  
  45. 	while(isdigit(ch = gc()))
  46. 		n = (n << 3) + (n << 1) + ch - '0';
  47.  
  48. 	n *= sign;
  49. }
  50.  
  51. # define pMAT(mat,r,c)	rep(i,0,r){\
  52. 							rep(j,0,c)\
  53. 								pd(mat[i][j]),pc(' ');\
  54. 							nline;\
  55. 						}
  56.  
  57. # define TC				int tc;sd(tc);while(tc--)
  58.  
  59. // ACTUAL CODE-------------------------------------------------------
  60. /* 
  61. 	IDEA
  62.  
  63. 	bool DP[MOVES[NUMS];
  64.  
  65. 	DP[i][j] => ith move and jth number, contains the answer to question
  66. 	what will happen to the one whose move is this ?
  67. 	Will he win? or lose?
  68. 	1 - win
  69. 	0 - loose
  70.  
  71. 	1. TRANS[num] = { , , , };
  72. 	TRANS contains the possible list of numbers 
  73. 	which can be obtained if a move is made at that number.
  74.  
  75. 	2. If the total no. of moves are odd, ADA will play move no. 1,3,5,...
  76. 	Else ADA will play move no. 2,4,6,..
  77.  
  78. 	3. For the first move,
  79. 		DP[1][num]
  80. 		if it's ADA's move (i.e. total no. of moves are ODD),
  81. 		for this entry to be true, there must exist atleast one transition leading to 
  82. 		a number which is greater than current number num.
  83.  
  84. 		if it's VINIT's move (i.e. total no. of moves are even)
  85. 		for this entry to be true, there must be atleast one transition to a number
  86. 		which is smaller than current number num.
  87.  
  88. 	4. for 2nd move onwards, 
  89. 		every player will keep their entry true, if there is atleast one
  90. 		transition that leads to loose for the opponent.
  91.  
  92. */
  93.  
  94.  
  95. # define NUM 10000
  96. int TRANS[NUM+1][4];
  97.  
  98. // Fill transition entries, for every number
  99. void fillTrans(void){
  100.  
  101. 	rep(i,0,NUM){
  102.  
  103. 		int ptr = 0;
  104. 		char digit[4];
  105. 		int num = i;
  106.  
  107. 		rrep(i,3,-1){
  108. 			digit[3-i] = num%10;
  109. 			num /= 10;
  110. 		}
  111. 		num = i;
  112.  
  113. 		rep(i,0,4){
  114. 			char ch = digit[i];
  115. 			(digit[i] += 1) %= 10;
  116.  
  117. 		int n = digit[3];
  118. 			rrep(i,2,-1)
  119. 				 n = (n*10)+digit[i];
  120.  
  121. 			TRANS[num][ptr++] = n;
  122. 			digit[i] = ch;
  123. 		}
  124. 	}
  125. }	
  126.  
  127. void printTrans(int num){
  128. 	cout << num << endl;
  129. 	cout<<TRANS[num][0]<<" "<<TRANS[num][1]<<" "<<TRANS[num][2]<<" "<<TRANS[num][3]<<endl;
  130. }
  131.  
  132. # define MOVES 100
  133.  
  134. bool DP[MOVES+1][NUM];
  135.  
  136. int main(void){
  137.  
  138. 	fillTrans();
  139.  
  140. 	TC{
  141.  
  142. 		int num,moves;
  143.  
  144. 		sd(num);
  145. 		sd(moves);
  146.  
  147. 		// initialize
  148. 		rep(i,0,moves+1)
  149. 			rep(j,0,NUM)
  150. 				DP[i][j] = 0;
  151.  
  152. 		// base case
  153. 		rep(i,num+1,NUM)
  154. 			DP[0][i] = true;
  155.  
  156. 		// for first move
  157. 		// ADA
  158. 		if(moves&1)
  159. 			rep(j,0,NUM){
  160. 				rep(i,0,4)
  161. 					DP[1][j] |= (TRANS[j][i] > j);
  162. 			}
  163. 		// VINIT	
  164. 		else
  165. 			rep(j,0,NUM){
  166. 				rep(i,0,4)
  167. 					DP[1][j] |= (TRANS[j][i] < j);
  168. 			}
  169.  
  170. 		// for all further moves, there must be
  171. 		// at least one transisiton, where
  172. 		// the opponent will loose !!
  173. 		rep(i,2,moves+1)
  174. 			rep(j,0,NUM){
  175. 				rep(k,0,4)
  176. 					DP[i][j] |= !DP[i-1][TRANS[j][k]];
  177. 			}
  178. 		puts(DP[moves][num]?"ADA":"VINIT");
  179. 		nline;		
  180. 	}	
  181.  
  182. 	return 0;
  183. }
  184.  
  185. /*
  186. 	Correct Output : 
  187.  
  188. 	Ada
  189. 	Ada
  190. 	Vinit
  191. 	Ada
  192. 	Vinit
  193. 	Ada
  194. 	Vinit
  195. 	Vinit
  196. 	Ada
  197. 	Vinit	
  198.  
  199. */	
  200.  
Success #stdin #stdout 0.02s 16384KB
comments (?)
stdin
copy 
10
1232 34
2323 43
9898 65
6532 3
3245 0
2342 23
7863 99
2423 100
3242 49
8999 99
stdout
copy 
ADA

ADA

ADA

ADA

VINIT

ADA

ADA

ADA

ADA

ADA
https://ideone.com/7vAGAJ
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!