Advertisement
dmitryokh

Untitled

Jan 1st, 2018
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.65 KB | None | 0 0
  1. #include <cstdio>
  2. #include <deque>
  3. #include <fstream>
  4. #include <iostream>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. void sum (deque <int>& a, deque <int>& b) {
  10. if (a.size() < b.size()) {
  11. long long int dif = b.size() - a.size();
  12. for (size_t i = 0; i < dif; ++i) {
  13. a.push_front(0);
  14. }
  15. } else {
  16. long long int dif = a.size() - b.size();
  17. for (size_t i = 0; i < dif; ++i) {
  18. b.push_front(0);
  19. }
  20. }
  21. long long int size = a.size();
  22. int sign = (a[size - 1] + b[size - 1]) / 10;
  23. a[size - 1] = (a[size - 1] + b[size - 1]) % 10;
  24. for (long long int i = size - 2; i >= 0; --i) {
  25. int sign_new = (a[i] + b[i] + sign) / 10;
  26. a[i] = (a[i] + b[i] + sign) % 10;
  27. sign = sign_new;
  28. }
  29. if (sign) {
  30. a.push_front(1);
  31. }
  32. }
  33.  
  34. void composition (deque <int>& a, deque <int>& b) {
  35. if (a.size() < b.size()) {
  36. deque <int> temp = a;
  37. a = b;
  38. b = temp;
  39. }
  40. int count = 0;
  41. for (long long int i = a.size() - 1; i >= 0; --i) {
  42. if (a[i] == 0) {
  43. ++count;
  44. a.pop_back();
  45. } else {
  46. break;
  47. }
  48. }
  49. for (long long int i = b.size() - 1; i >= 0; --i) {
  50. if (b[i] == 0) {
  51. ++count;
  52. b.pop_back();
  53. } else {
  54. break;
  55. }
  56. }
  57. vector <deque <int> > v;
  58. for (int j = b.size() - 1; j >= 0; --j) {
  59. deque <int> c = a;
  60. int sign = (c[c.size() - 1] * b[j]) / 10;
  61. c[c.size() - 1] = (c[c.size() - 1] * b[j]) % 10;
  62. for (long long int i = c.size() - 2; i >= 0; --i) {
  63. int sign_new = (c[i] * b[j] + sign) / 10;
  64. c[i] = (c[i] * b[j] + sign) % 10;
  65. sign = sign_new;
  66. }
  67. if (sign) {
  68. c.push_front(sign);
  69. }
  70. for (int i = j; i < b.size() - 1; ++i) {
  71. c.push_back(0);
  72. }
  73. v.push_back(c);
  74. }
  75. deque <int> d = {0};
  76. for (auto i : v) {
  77. sum(d, i);
  78. }
  79. for (int i = 0; i < count; ++i) {
  80. d.push_back(0);
  81. }
  82. a = d;
  83. }
  84.  
  85. deque <int> inttodeque (int i) {
  86. deque <int> d;
  87. while (i > 0) {
  88. d.push_front(i % 10);
  89. i /= 10;
  90. }
  91. return d;
  92. }
  93.  
  94. int main() {
  95. int a;
  96. freopen("input.txt", "r", stdout);
  97. cin >> a;
  98. fclose(stdout);
  99. deque <int> answ = {1};
  100. for (int i = 1; i <= a; ++i) {
  101. deque <int> d = inttodeque(i);
  102. composition(answ, d);
  103. }
  104. freopen("output.txt", "w", stdout);
  105. for (auto i : answ) {
  106. cout << i;
  107. }
  108. fclose(stdout);
  109. return 0;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement