fork(3) download
copy 
  1. /*input
  2. 1
  3. 2 4
  4. */
  5.  
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8.  
  9. int dp[55][8][8][8][8];
  10. vector<int> obvious(int ppreAttack)
  11. {
  12. 	vector<int> ret;
  13. 	int a = 0;
  14. 	if((ppreAttack & (1<<0))==0 || (ppreAttack & (1<<2))==0) a |= (1<<1);
  15. 	if((ppreAttack & (1<<1))==0){
  16. 		ret.push_back(a | (1<<0));
  17. 		ret.push_back(a | (1<<2));
  18. 	}
  19. 	if(ret.empty()) ret.push_back(a);
  20. 	return ret;
  21. }
  22. vector<int> allpossible(int now)
  23. {
  24. 	vector<int> ret;
  25. 	for(int i = 0; i<8; i++)
  26. 	{
  27. 		if((i&now) == now) ret.push_back(i);
  28. 	}
  29. 	return ret;
  30. }
  31.  
  32. pair<int, int> make_Attack(int ppreKnight, int preKnight, int preAttack, int now)
  33. {
  34. 	pair<int, int> ret = {preAttack, now}; //making {ppreAttack, preAttack}
  35. 	if((now & (1<<0))) ret.first |= (1<<2);
  36. 	if(now & (1<<2)) ret.first |= (1<<0);
  37. 	if((ppreKnight & (1<<0)) || (ppreKnight & (1<<2))) ret.second |= (1<<1);
  38. 	if(ppreKnight & (1<<1)){
  39. 		ret.second |= (1<<0);
  40. 		ret.second |= (1<<2);
  41. 	}
  42. 	if((preKnight & (1<<0))) ret.second |= (1<<2);
  43. 	if(preKnight & (1<<2)) ret.second |= (1<<0);
  44.  
  45. 	return ret;
  46. }
  47.  
  48. int m;
  49. int rec(int col, int ppreAttack, int preAttack, int ppreKnight, int preKnight)
  50. {
  51. 	if(col==-1) {
  52. 		if(preAttack==7 && ppreAttack==7)
  53. 			return 0;
  54. 		return 1000000007;
  55. 	}
  56.  
  57.  
  58. 	int &ret = dp[col][ppreAttack][preAttack][ppreKnight][preKnight];   
  59. 	if(ret != -1) return ret; // memoization
  60.  
  61.  
  62. 	ret = 1000000007;
  63. 	vector<int> vt = obvious(ppreAttack);   // the knight positions of this column which is obvious
  64. 	for(int x : vt)
  65. 	{
  66. 		vector<int> all = allpossible(x);  // all possible configuration with its obvious configurations
  67. 		for(int y : all)
  68. 		{
  69. 			auto z = make_Attack(ppreKnight, preKnight, preAttack, y);   // making attacking configurations of preAttack and this column
  70. 			ret = min(ret, __builtin_popcount(y) + rec(col-1, z.first, z.second, preKnight, y));
  71. 		}
  72. 	}
  73. 	return ret;
  74. }
  75.  
  76. int main()
  77. {
  78. 	int ans[55];
  79.  
  80. 	memset(dp, -1, sizeof dp);
  81. 	for(m = 4; m<55; m++){
  82.     	ans[m] = 1000000007;
  83.     	for(int i = 0; i<8; i++)
  84.     	for(int j = 0; j<8; j++){
  85.     		auto z = make_Attack(0, i, 0, j);  // initial config i and j and attacking config
  86.     		ans[m] = min(ans[m], __builtin_popcount(i) + __builtin_popcount(j) + rec(m-3, z.first, z.second, i, j));
  87.     	}
  88.     	// cout << m << " " << ans[m] << endl;
  89. 	}
  90.  
  91. 	int t;
  92. 	scanf("%d", &t);
  93. 	while(t--)
  94. 	{
  95. 		int n;
  96. 		scanf("%d %d", &n, &m);
  97. 		int res = 0;
  98. 		if(n==1) res = m;
  99. 		else if(n==2) {
  100. 			res = (m/6) * 4;
  101. 			m%=6;
  102. 			if(m <= 1) res += m * 2;
  103. 			else res += 4;
  104. 		}
  105. 		else{
  106. 			if(m==1) res = 3;
  107. 			else if(m<=4) res = 4;
  108. 			else res = ans[m];
  109. 		}
  110. 		printf("%d\n", res);
  111. 	}
  112. 	return 0;
  113.  
  114. }
Success #stdin #stdout 0s 16120KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DCuN9f
language:
C++14 (gcc 8.3)
created:
6 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!