fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. bool DEBUG = true;
  4. int solve(int base) {
  5. 	int bound = (base - 1) * (base - 2) + 1;
  6. 	auto adjust = [&](vector<int> mask, int digit) {
  7. 		vector<int> ret(bound, 0);
  8. 		for(int i = 0; i < bound; ++i)
  9. 			if(mask[i]) {
  10. 				ret[abs(i - digit)] = 1;
  11. 				if(i + digit < bound)
  12. 					ret[i + digit] = 1;
  13. 			}
  14. 		return ret;
  15. 	};
  16.  
  17. 	map<vector<int>, int> Hash;
  18. 	vector<int> diff;
  19. 	vector<vector<int> > trans;
  20.  
  21. 	function<int(vector<int>)> dfs;
  22. 	dfs = [&](vector<int> cur) {
  23. 		auto iter = Hash.find(cur);
  24. 		if(iter != Hash.end())
  25. 			return iter -> second;
  26. 		int idx = Hash.size();
  27. 		Hash[cur] = idx;
  28. 		if(DEBUG && Hash.size() % (int)1e4 == 0)
  29. 			cerr << "collected " << Hash.size() << " states" << endl;
  30. 		for(int i = 0; i < base; ++i)
  31. 			if(cur[i]) {
  32. 				diff.push_back(i);
  33. 				break;
  34. 			}
  35. 		trans.push_back(vector<int>(base, -1));
  36. 		for(int i = 0; i < base; ++i)
  37. 			trans[idx][i] = dfs(adjust(cur, i));
  38. 		return idx;
  39. 	};
  40.  
  41. 	vector<int> origin(bound, 0);
  42. 	origin[0] = 1;
  43. 	dfs(origin);
  44. 	if(DEBUG)
  45. 		cerr << "collected " << Hash.size() << " states" << endl;
  46.  
  47. 	int size = base;
  48. 	vector<int> pos(diff);
  49. 	for(int i = 0; i < base; ++i) {
  50. 		vector<int> pos2;
  51. 		map<vector<int>, int> Hash2;
  52. 		for(int j = 0; j < Hash.size(); ++j) {
  53. 			vector<int> vec;
  54. 			vec.push_back(diff[j]);
  55. 			for(int k = 0; k < base; ++k)
  56. 				vec.push_back(pos[trans[j][k]]);
  57. 			auto iter = Hash2.find(vec);
  58. 			if(iter != Hash2.end())
  59. 				pos2.push_back(iter -> second);
  60. 			else {
  61. 				int idx = Hash2.size();
  62. 				pos2.push_back(Hash2[vec] = idx);
  63. 			}
  64. 		}
  65. 		if(size == Hash2.size())
  66. 			break;
  67. 		if(DEBUG)
  68. 			cerr << "distinct states: " << size << " -> " << Hash2.size() << endl;
  69. 		size = Hash2.size();
  70. 		pos = move(pos2);
  71. 	}
  72. 	return size;
  73. }
  74. int main() {
  75. 	int base;
  76. 	while(cin >> base)
  77. 		cout << "number of states: " << solve(base) << endl;
  78. 	return 0;
  79. }
Success #stdin #stdout #stderr 0.26s 8852KB
comments (?)
stdin
copy 
2
3
4
5
6
7
8
9
10
stdout
copy 
number of states: 2
number of states: 4
number of states: 10
number of states: 21
number of states: 51
number of states: 89
number of states: 203
number of states: 370
number of states: 715
stderr
copy 
collected 2 states
collected 4 states
distinct states: 3 -> 4
collected 14 states
distinct states: 4 -> 7
distinct states: 7 -> 9
distinct states: 9 -> 10
collected 47 states
distinct states: 5 -> 12
distinct states: 12 -> 17
distinct states: 17 -> 20
distinct states: 20 -> 21
collected 174 states
distinct states: 6 -> 19
distinct states: 19 -> 36
distinct states: 36 -> 47
distinct states: 47 -> 50
distinct states: 50 -> 51
collected 485 states
distinct states: 7 -> 30
distinct states: 30 -> 58
distinct states: 58 -> 76
distinct states: 76 -> 85
distinct states: 85 -> 88
distinct states: 88 -> 89
collected 1681 states
distinct states: 8 -> 45
distinct states: 45 -> 111
distinct states: 111 -> 159
distinct states: 159 -> 186
distinct states: 186 -> 199
distinct states: 199 -> 202
distinct states: 202 -> 203
collected 4513 states
distinct states: 9 -> 67
distinct states: 67 -> 183
distinct states: 183 -> 278
distinct states: 278 -> 331
distinct states: 331 -> 355
distinct states: 355 -> 366
distinct states: 366 -> 369
distinct states: 369 -> 370
collected 10000 states
collected 12880 states
distinct states: 10 -> 97
distinct states: 97 -> 317
distinct states: 317 -> 505
distinct states: 505 -> 612
distinct states: 612 -> 671
distinct states: 671 -> 699
distinct states: 699 -> 711
distinct states: 711 -> 714
distinct states: 714 -> 715
https://ideone.com/zyzaFQ
language:
C++14 (gcc 8.3)
created:
6 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!