fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int ans,g[6],u[8888888][6],st[8888888],lim=0;
  4. #define S 73
  5. void dfs(int d,int uu,int su=0)
  6. {
  7. 	if(!d)
  8. 	{
  9. 		if(su!=lim) return;
  10. 		++ans; st[ans]=su;
  11. 		memcpy(u[ans],g,sizeof g);
  12. 		return;
  13. 	}
  14. 	for(int x=uu;su+x<=lim;++x)
  15. 		g[d-1]=x,dfs(d-1,x,su+x);
  16. }
  17. int p_[100000],*p=p_+50000;
  18. bool chk(int*t)
  19. {
  20. 	return t[1]==1&&t[2]==2&&t[3]==3&&t[4]==4&&t[5]==5&&t[6]==6&&t[7]==7&&t[8]==8;
  21. }
  22. bool ok[S][S];
  23. int main()
  24. {
  25. 	for(int mi=0;mi<S;++mi)
  26. 		for(int mx=mi;mx<S;++mx)
  27. 		{
  28. 			for(int d=max(max(mi/2,mx/8),2);mi>=d&&mx>=8*d;++d)
  29. 				if(mi/d==1&&mx/d==8) ok[mi][mx]=1;
  30. 			if(mx-mi==7) ok[mi][mx]=1;
  31. 			for(int d=max(mx,mi*8);d<2*mx&&d<9*mi;++d)
  32. 				if(d/mx==1&&d/mi==8) ok[mi][mx]=1;
  33. 			if(mi<1&&mx==8) ok[mi][mx]=1;
  34. 			if(mi==1&&mx>8) ok[mi][mx]=1;
  35. 		}
  36. 	for(lim=0;lim<=S;++lim)
  37. 		dfs(6,0);
  38. 	cout<<ans<<" different dices\n";
  39. 	long long pa=0,pb=0;
  40. 	for(int i=1;i<=ans&&st[i]+st[i]<=S;++i)
  41. 	{
  42. 		for(int j=i;j<=ans;++j)
  43. 		{
  44. 			if(st[i]+st[j]>S) break;
  45. 			++pa;
  46. 			int mi=u[i][5]+u[j][5];
  47. 			int mx=u[i][0]+u[j][0];
  48. 			if(!ok[mi][mx]) continue;
  49. 			++pb;
  50. 			#define FOUND_SOL(l,ex) \
  51. 			{int tot=0;for(auto a:u[i]) tot+=a;for(auto b:u[j]) tot+=b;\
  52. 			cout<<"[";for(auto a=5;a>=0;--a)cout<<u[i][a]<<",";cout<<"\b],";\
  53. 			cout<<"[";for(auto a=5;a>=0;--a)cout<<u[j][a]<<",";cout<<"\b] DS="<<tot<<" LINE"<<l; ex; cout<<"\n";}
  54. 			//plus or minus
  55. 			if(mx-mi==7)
  56. 			{
  57. 				memset(p,0,sizeof(int)*10);
  58. 				for(auto a:u[i])
  59. 					for(auto b:u[j]) ++p[a+b-mi+1];
  60. 				if(chk(p)) FOUND_SOL(__LINE__,void(0))
  61. 			}
  62. 			//neg minus
  63. 			if(mx-mi==7)
  64. 			{
  65. 				memset(p,0,sizeof(int)*10);
  66. 				for(auto a:u[i])
  67. 					for(auto b:u[j]) ++p[mx-(a+b)+1];
  68. 				if(chk(p)) FOUND_SOL(__LINE__,void(0))
  69. 			}
  70. 			//multiply surely cannot make a full covering
  71. 			//divison
  72. 			for(int d=max(max(mi/2,mx/8),2);mi>=d&&mx>=8*d;++d)
  73. 			{
  74. 				if(mi/d==1&&mx/d==8)
  75. 				{
  76. 					++pa;
  77. 					memset(p,0,sizeof(int)*10);
  78. 					for(auto a:u[i])
  79. 						for(auto b:u[j]) ++p[(a+b)/d];
  80. 					if(chk(p)) FOUND_SOL(__LINE__,cout<<" D="<<d)
  81. 				}
  82. 			}
  83. 			//back division
  84. 			if(mi&&mx)
  85. 			for(int d=max(mx,mi*8);d<2*mx&&d<9*mi;++d)
  86. 			{
  87. 				if(d/mx==1&&d/mi==8)
  88. 				{
  89. 					++pa;
  90. 					memset(p,0,sizeof(int)*10);
  91. 					for(auto a:u[i])
  92. 						for(auto b:u[j]) ++p[d/(a+b)];
  93. 					if(chk(p)) FOUND_SOL(__LINE__,cout<<" D="<<d)
  94. 				}
  95. 			}
  96. 			//max 1
  97. 			if(mi<1&&mx==8)
  98. 			{
  99. 				memset(p,0,sizeof(int)*10);
  100. 				for(auto a:u[i])
  101. 					for(auto b:u[j]) ++p[max(a+b,1)];
  102. 				if(chk(p)) FOUND_SOL(__LINE__,void(0))
  103. 			}
  104. 			//min 8
  105. 			if(mi==1&&mx>8)
  106. 			{
  107. 				memset(p,0,sizeof(int)*10);
  108. 				for(auto a:u[i])
  109. 					for(auto b:u[j]) ++p[min(a+b,8)];
  110. 				if(chk(p)) FOUND_SOL(__LINE__,void(0))
  111. 			}
  112. 		}
  113. 	}
  114. 	cout<<pa<<"  "<<pb<<"\n";
  115. 	for(;;);
  116. }
  117. //on my computer, runtime ~155s
  118.  
Time limit exceeded #stdin #stdout 5s 21552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oDbJe3
language:
C++ (gcc 8.3)
created:
4 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!