fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <cstdlib> 
  5.  
  6. class largeNumber{
  7. public:
  8. 	// constructor
  9. 	largeNumber(void);
  10. 	// constructor
  11. 	largeNumber(const std::string& a);
  12. 	// deconstructor
  13. 	~largeNumber(void);
  14.  
  15. 	// wrapper of std::string
  16. 	char operator[](unsigned int i) const {
  17. 		return rawString[i];
  18. 	}
  19. 	unsigned int length() const {
  20. 		return (unsigned int)rawString.length();
  21. 	}
  22.  
  23. 	// align the string
  24. 	void alignDigits(std::string& leftString, std::string& rightString) const;
  25. 	// add operation
  26. 	const largeNumber operator +(const class largeNumber& right) const;
  27. 	// add operation
  28. 	largeNumber& operator +=(const largeNumber& right){
  29. 		*this = *this + right;
  30. 		return *this;
  31. 	}
  32. 	// substitution
  33. 	largeNumber& operator =(const largeNumber& a){
  34. 		rawString = a.rawString;
  35. 		return *this;
  36. 	}
  37.  
  38. 	std::string getString() const {
  39. 		return rawString;
  40. 	}
  41.  
  42. private:
  43. 	// container of the actual index/key/value
  44. 	std::string rawString;
  45. };
  46.  
  47. std::ostream& operator << (std::ostream& out, const largeNumber& right);
  48.  
  49. largeNumber::largeNumber(void)
  50. {
  51. }
  52.  
  53.  
  54. largeNumber::~largeNumber(void)
  55. {
  56. }
  57.  
  58. largeNumber::largeNumber(const std::string& a){
  59. 	rawString = a;
  60. 	bool hasNonNumberCharacter = false;
  61. 	for(unsigned int i = 0;i < rawString.length();i++){
  62. 		if(rawString[i] < '0' || '9' < rawString[i]){
  63. 			hasNonNumberCharacter = true;
  64. 			break;
  65. 		}
  66. 	}
  67. 	if(hasNonNumberCharacter){
  68. 		rawString = '0';
  69. 	}
  70. }
  71.  
  72. void largeNumber::alignDigits(std::string& leftString, std::string& rightString) const {
  73. 	unsigned int maxLength = leftString.length() < rightString.length() ? rightString.length() : leftString.length(); // get the length of longest string
  74.  
  75. 	int offset = (int)maxLength - (int)leftString.length();
  76. 	while(offset >= 0){
  77. 		leftString.insert(leftString.begin(), '0');
  78. 		offset--;
  79. 	}
  80. 	offset = (int)maxLength - (int)rightString.length();
  81. 	while(offset >= 0){
  82. 		rightString.insert(rightString.begin(), '0');
  83. 		offset--;
  84. 	}
  85. 	return;
  86. }
  87.  
  88. const largeNumber largeNumber::operator +(const class largeNumber& right) const {
  89. 	std::string leftString = rawString;
  90. 	std::string rightString = right.rawString;
  91. 	alignDigits(leftString, rightString);
  92.  
  93. 	char carryUp = 0;
  94. 	int i =0;
  95. 	for(i = leftString.length()-1;i > 0;i--){
  96. 		char a = leftString[i] - '0';
  97. 		char b = rightString[i] - '0';
  98. 		char c = a + b + carryUp;
  99. 		if(10 <= c){
  100. 			carryUp = 1;
  101. 			c -= 10;
  102. 		}else{
  103. 			carryUp = 0;
  104. 		}
  105. 		leftString[i] = c + '0';
  106. 	}
  107. 	if(carryUp == 1){
  108. 		// When carry up happens at the MSB
  109. 		leftString[0] = carryUp + '0';
  110. 	}else{
  111. 		// else
  112. 		leftString.erase(0,1);
  113. 	}
  114. 	return largeNumber(leftString);
  115. }
  116.  
  117. std::ostream& operator << (std::ostream& out, const largeNumber& right)
  118. {
  119. 	out << right.getString();
  120. 	return out;
  121. }
  122.  
  123. std::vector<class largeNumber> fibonacci;
  124.  
  125. class largeNumber simpleFibonacciNumber2(int i)
  126. {
  127. 	if(fibonacci.empty())
  128. 	{
  129. 		fibonacci.push_back(largeNumber("0"));
  130. 	}
  131. 	if(fibonacci.size() == 1)
  132. 	{
  133. 		fibonacci.push_back(largeNumber("1"));
  134. 	}
  135. 	if(fibonacci.size() == 2)
  136. 	{
  137. 		fibonacci.push_back(largeNumber("1"));
  138. 	}
  139. 	if(i <= 0)
  140. 	{
  141. 		return largeNumber("0");
  142. 	}
  143. 	if((unsigned int)i < fibonacci.size())
  144. 	{
  145. 		return fibonacci[i];
  146. 	}
  147. 	for(unsigned int j = fibonacci.size()-1;j < (unsigned int)i;j++)
  148. 	{
  149. 		class largeNumber p = fibonacci[fibonacci.size()-1];
  150. 		class largeNumber q = fibonacci[fibonacci.size()-2];
  151. 		fibonacci.push_back(p+q);
  152. 	}
  153. 	return fibonacci[i];
  154. }
  155.  
  156. class largeNumber solveMayoiDoro(int n)
  157. {
  158. 	class largeNumber retValue("0");
  159. 	for(int i = 1;i <= n;i += 2)
  160. 	{
  161. 		retValue += simpleFibonacciNumber2(i+2);
  162. 	}
  163. 	return retValue;
  164. }
  165.  
  166. int main(int argc, char **argv)
  167. {
  168. 	using namespace std;
  169. 	std::string stub;
  170. 	cin >> stub;
  171. 	int i = atoi(stub.c_str());
  172.  
  173. 	cout << solveMayoiDoro(i) << endl;
  174.  
  175. 	return 0;
  176. }
  177.  
Success #stdin #stdout 0.02s 3472KB
comments (?)
stdin
copy 
2015
stdout
copy 
24410294683171395267259945469996127000411199333760853190535535281681195871429510314079442068798555059453792431772087225245168879580469159794544170936403149540819320510882801573596907938222922817134288725100817648047405608500267748766714030468003650259685406411646787207097050545802045736020993909154298598218721111963426993884619351338577630868510716463423585020972878819198991971234596733617320373133963970742975210614208
https://ideone.com/ngG5Jk
language:
C++ (gcc 8.3)
created:
9 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!