fork(6) download
copy 
  1. //Finding Sprague-Grundy number for each subset of the array and finding the answer
  2. #include<stdio.h>
  3. #include<algorithm>
  4. using namespace std;
  5. int grundy[1<<16];
  6. void init()
  7. {
  8. 	for(int i=0;i<(1<<16);i++)
  9. 		grundy[i]=-1;
  10. 	grundy[0]=0;			//Zero element also P position
  11. 	for(int i=0;i<16;i++)
  12. 		grundy[1<<i]=0;		//Single elements means P position
  13. }
  14. int isSorted(int arr[],int size,int position)
  15. {
  16. 	int l=-999;		//As no element will be lesser than this
  17. 	for(int i=size-1;i>=0;i--)
  18. 	{
  19. 		if(position & (1<<i))
  20. 		{
  21. 			if(arr[i]>l)
  22. 				l=arr[i];
  23. 			else
  24. 				return 0;
  25. 		}
  26. 	}
  27. 	return 1;
  28. }
  29. int solve(int arr[],int size,int position)
  30. {
  31. 	if(grundy[position]!=-1)
  32. 		return grundy[position];
  33. 	if(isSorted(arr,size,position))
  34. 	{
  35. 		grundy[position]=0;	//Since already sorted, no moves are there
  36. 		return 0;
  37. 	}
  38.  
  39.  
  40. 	int idx=0;
  41. 	int count[size];
  42. 	for(int i=0;i<size;i++)		//We can remove any one element, so removing that, calculating and restoring the element
  43. 	{
  44. 		if(position & (1<<i))
  45. 		{
  46. 			position^=(1<<i);	//Changes ith bit, got from stackoverflow
  47. 			count[idx]=solve(arr,size,position);	//Stores grundy number of a position to which we can go
  48. 			idx++;
  49. 			position^=(1<<i);
  50. 		}
  51. 	}
  52. 	int ans=0;
  53. 	sort(count,count+idx);
  54. 	for(int i=0;i<idx;i++)	//Finding grundy number of present position which minimum value to where we cannot move
  55. 	{
  56. 		if(ans==count[i])
  57. 		{
  58. 			while(ans==count[i])
  59. 				i++;
  60. 			i--;		//decrementing coz it will be incremented again when loop ends
  61. 			ans++;
  62. 		}
  63. 	}
  64. 	grundy[position]=ans;
  65. 	return ans;
  66.  
  67. }
  68. int main()
  69. {
  70. 	int test,n;
  71. 	scanf("%d",&test);
  72. 	while(test--)
  73. 	{
  74. 		scanf("%d",&n);
  75. 		int arr[n];
  76. 		for(int i=0;i<n;i++)
  77. 			scanf("%d",&arr[i]);
  78. 		init();
  79.  
  80. 		if(solve(arr,n,(1<<n)-1)==0)
  81. 			printf("Bob\n");
  82. 		else
  83. 			printf("Alice\n");
  84. 		for(int i=0;i<(1<<n);i++)
  85. 			printf("%d\t",grundy[i]);
  86. 	}
  87. }
Success #stdin #stdout 0s 2988KB
comments (?)
stdin
copy 
2
3
1 3 2
5
5 3 2 1 4
stdout
copy 
Alice
0	0	0	1	0	1	0	2	Alice
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	2	1	2	2	1	1	2	2	1	2	1	1	2
https://ideone.com/kzswDO
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 years ago
visibility:
secret

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!