fork download
copy 
  1. 	#include <stdio.h>
  2. 	#include <stdlib.h>
  3. 	#include <utility>
  4. 	#include <map>
  5. 	using namespace std;
  6.  
  7. 	map<int,int> arr;
  8.  
  9. 	int min3(int a,int b,int c)
  10. 	{
  11. 		return a>b?((b<c)?b:c):((a<c)?a:c);
  12. 	}
  13.  
  14. 	int min2(int a,int b)
  15. 	{
  16. 		return a>b?b:a;
  17. 	}
  18.  
  19. 	int solve(int n)
  20. 	{
  21. 		if(n==1) return 0;
  22. 		if(n==2 || n==3 ) return 1;
  23. 		if(arr.find(n)!=arr.end()) return arr[n];
  24. 		int ans;
  25. 		if(n%2==0 && n%3==0 )
  26. 		  ans=(1+min3(solve(n-1),solve(n/2),solve(n/3)));
  27. 		else if(n%2==0)
  28. 			ans=(1+min2(solve(n-1),solve(n/2)));
  29. 		else if(n%3==0)
  30. 			ans=(1+min2(solve(n-1),solve(n/3)));
  31. 		else
  32. 			ans=(1+solve(n-1));
  33. 		arr[n]=ans;
  34. 		return ans;
  35. 	}
  36. 	int main()
  37. 	{
  38. 	    //printf("Hello World!\n");
  39. 	    int t;
  40. 	    scanf("%d",&t);
  41. 	    arr[1]=0;
  42. 	    arr[2]=1;
  43. 	    arr[3]=1;
  44.  
  45.  
  46. 	    while(t--)
  47. 	    {
  48. 	    	int n;
  49. 	    	scanf("%d",&n);
  50. 	    	printf("%d\n",solve(n));
  51.  
  52. 	    }
  53. 	}
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
2
4
9
stdout
copy 
2
2
https://ideone.com/3HfV9f
language:
C++ (gcc 8.3)
created:
10 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!