Saleh127

UVA 10359

May 6th, 2021
195
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.22 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5.  
  6. string addd(string a,string c)
  7. {
  8.  
  9. ll s1,s2,l,i,j,k=0;
  10. string sum="";
  11.  
  12. reverse(a.begin(),a.end());
  13. reverse(c.begin(),c.end());
  14.  
  15. s1=a.size();
  16. s2=c.size();
  17. l=max(s1,s2);
  18.  
  19. for(i=0; i<l; i++)
  20. {
  21. if(i<s1)
  22. {
  23. k+=(a[i]-'0');
  24. }
  25. if(i<s2)
  26. {
  27. k+=(c[i]-'0');
  28. }
  29. sum+=((k%10)+'0');
  30. k/=10;
  31. }
  32.  
  33. if(k)
  34. {
  35. sum+=(k+'0');
  36. }
  37. reverse(sum.begin(),sum.end());
  38.  
  39. for(i = 0; i <sum.size(); i++)
  40. {
  41. if(sum[i]!= '0')
  42. {
  43. return sum.substr(i);
  44. }
  45. }
  46. return "0";
  47. }
  48.  
  49.  
  50. int main()
  51. {
  52. ios_base::sync_with_stdio(0);
  53. cin.tie(0);cout.tie(0);
  54.  
  55. string f[2222];
  56.  
  57. f[0]=f[1]="1";
  58. f[2]="3";
  59.  
  60. for(ll i=3;i<=251;i++)
  61. {
  62. f[i]=addd(f[i-1],f[i-2]);
  63. f[i]=addd(f[i],f[i-2]);
  64.  
  65. /// possible combination are 2/1 for 2*1 and for 2*2 2/1,2/2;
  66. /// for this calculate i-2, 2 times
  67. }
  68.  
  69. ll n;
  70. while(cin>>n)
  71. {
  72. cout<<f[n]<<endl;
  73. }
  74.  
  75. return 0;
  76. }
  77.  
Advertisement
Add Comment
Please, Sign In to add comment