fork download 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5. vector<vector<int>> v;
  6. inline int f(int x){
  7.     return ((x^(x<<2))>>1)&((1<<7)-2);
  8. }
  9. void precompute(){
  10. 	vector<int> temp(1<<8,0);
  11. 	for(int j=0; j<32; j++){
  12. 	    for(int i=0; i<temp.size(); i++)
  13. 	        temp[i] = j?v.back()[v.back()[i]]:f(i);
  14. 	    v.push_back(temp);
  15. 	}
  16. }
  17. int iterative(int x, int n){
  18. 	while(n--)
  19. 		x = v[0][x];
  20. 	return x;
  21. }
  22. int nth_transform(int x, int n){
  23. 	for(int i=0; i<32; i++)
  24. 		if(n&(1<<i))
  25. 			x = v[i][x];
  26. 	return x;
  27. }
  28. int main() {
  29. 	if(v.empty())
  30. 		precompute();
  31. 	int n,x;
  32. 	cin>>n>>x;
  33. 	x %= 256;	// f is designed to handle only finite (256) values.
  34. 	if(!x)	x = 256;
  35. 	for(int i=0; i<n; i++)
  36. 		for(int j=0; j<x; j++)
  37. 			if(iterative(j,i)!=nth_transform(j,i))
  38. 				cout<<"mismatch for x = "<<x<<" n = "<<n<<endl;
  39. 	cout<<"check executed successfully"<<endl;
  40. 	return 0;
  41. }
Success #stdin #stdout 4.26s 4516KB
comments ()
stdin 
5000
256
stdout 
check executed successfully
https://ideone.com/I9WNY7
Arbitrary number of times repeated application of a transformation function over a finite domain
language:
C++14 (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!