fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int arr[100000];
  4. void seive()
  5. {
  6. 	arr[0]=1;
  7. 	arr[1]=1;
  8. 	int i;
  9. 	for(i=2;i<sqrt(100000)+1;i++)
  10. 	{
  11. 		if(arr[i]==0)
  12. 		{
  13. 			for(int j=2*i;j<100000;j=j+i)
  14. 			{
  15. 				arr[j]=1;
  16. 			}
  17. 		}
  18. 	}
  19.  
  20. }
  21. int changekthdigit(int num,int x,int with)
  22. {
  23. 	int one=num/pow(10,x);
  24. 	one*=10;
  25. 	one+=with;
  26. 	one*=pow(10,x-1);
  27. 	one=one+(num%(int)pow(10,x-1));
  28. 	return one;
  29. }
  30. int main()
  31. {
  32. 	seive();
  33. 	long long int i;
  34. 	long long int T;
  35. 	scanf("%lld",&T);
  36. 	for(i=0;i<T;i++)
  37. 	{
  38. 		int a,b;
  39. 		scanf("%d %d",&a,&b);
  40.  
  41. 		std::queue<pair<int ,int > > myQ;
  42. 		int temp=a;
  43. 		pair<int ,int > mu;
  44. 		mu=make_pair(a,0);
  45. 		myQ.push(mu);
  46. 		arr[a]=1;
  47. 		int level=0;
  48. 		while(temp!=b)
  49. 		{
  50. 			temp=(myQ.front()).first;
  51. 			level=myQ.front().second;
  52. 			myQ.pop();
  53. 			for(int j=0;j<4;j++)
  54. 			{
  55. 				for(int k=0;k<10;k++)
  56. 				{
  57. 					if(j!=3 || k!=0)
  58. 						{
  59. 							int hello=changekthdigit(temp,j+1,k);
  60. 							if(arr[hello]==0)
  61. 								{
  62. 									arr[hello]=1;
  63. 									myQ.push(make_pair(hello,level+1));
  64. 								}
  65. 						}
  66.  
  67. 				}
  68. 			}
  69.  
  70. 		}
  71. 		printf("%d\n",level);
  72. 	}
  73.  
  74.  
  75. 	return 0;
  76. }
Runtime error #stdin #stdout 0s 15632KB
comments (?)
stdin
copy 
3
1033 8179
1373 8017
1033 1033
stdout
copy 
Standard output is empty
https://ideone.com/tJHKpU
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!