fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. map<long long, long long>dp;
  4. long long first;
  5. 	long long second;
  6. 	long long third;
  7. 	long long First;
  8. 	long long Second;
  9. 	long long Third;
  10. 	long double a;
  11. 	unsigned long long answer;
  12. 	long long int recur(long long i)
  13. 	{
  14. 		if(i<2)
  15. 		{
  16. 			return dp[i];
  17. 		}
  18. 		a = i/2;
  19. 		first = floor(a);
  20. 		First = recur(first);
  21. 		cout<<"F "<<First<<"\n";
  22. 		a = i/3;
  23. 		second = floor(a);
  24. 		Second = recur(second);
  25. 		cout<<"S "<<Second<<"\n";
  26. 		a = i/4;
  27. 		third = floor(a);
  28. 		Third = recur(third);
  29. 		cout<<"T "<<Third<<"\n";
  30. 		long long int sum = First+Second+Third;
  31. 		cout<<"S "<<sum<<"\n";
  32. 		answer = sum>i?sum:i;
  33. 		cout<<"A "<<answer<<" i "<<i<<"\n";
  34. 		return answer;
  35. 	}
  36. void precompute()
  37. {
  38. 	dp.insert(pair<long long, long long> (0, 0));
  39. 	dp.insert(pair<long long, long long> (1, 1));
  40. 		for(long long i=2,sum=0;i<2;i++)
  41. 		{
  42. 				a = i/2;
  43. 				first = floor(a);
  44. 				a = i/3;
  45. 				second = floor(a);
  46. 				a = i/4;
  47. 				third = floor(a);
  48. 				sum = dp[first]+dp[second]+dp[third];
  49. 				if(sum>i)
  50. 				dp.insert(pair <long long, long long> (i, sum));
  51. 				else
  52. 				dp.insert(pair<long long, long long> (i, i));
  53. 		}
  54.  
  55. }
  56. int main()
  57. {
  58. 	precompute();
  59. 	long long num;
  60. 	while(cin>>num)
  61. 	{
  62. 		if(num<2)
  63. 		{
  64. 			printf("%lld\n",dp[num]);
  65. 		}
  66. 		else
  67. 		{
  68. 			printf("%lld\n",recur(num));
  69. 		}
  70. 	}
  71. 	return 0;
  72. }
  73.  
Success #stdin #stdout 0s 4280KB
comments (?)
stdin
copy 
12
stdout
copy 
F 1
S 1
T 0
S 2
A 3 i 3
F 3
F 1
S 0
T 0
S 1
A 2 i 2
S 2
T 1
S 4
A 6 i 6
F 6
F 1
S 0
T 0
S 1
A 2 i 2
F 2
S 1
T 1
S 4
A 4 i 4
S 4
F 1
S 1
T 0
S 2
A 3 i 3
T 3
S 5
A 12 i 12
12
https://ideone.com/KBRNx3
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 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!