Guest User

Untitled

a guest
Feb 22nd, 2020
81
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #define N 100005
  4. using namespace std;
  5.  
  6. int n;
  7. long long v[32], a[N];
  8.  
  9. void Generare()
  10. {
  11. int i;
  12. long long x;
  13. x=1;
  14. for(i=1; i<=30; i++)
  15. v[i]=x, x*=2;
  16. }
  17.  
  18. void ReadSort()
  19. {
  20. ///citire
  21. cin >> n;
  22. for(int i=1; i<=n; i++)
  23. cin >> a[i];
  24. ///sortez vectorul
  25. sort(a+1, a+n+1);
  26. }
  27.  
  28. int CBS(int st, int dr, long long x)
  29. {
  30. int m, poz=0;
  31. while(st<=dr)
  32. {
  33. m=(st+dr)/2;
  34. if(x == v[m])
  35. poz=m, dr=m-1;
  36. else if(x<v[m])
  37. dr=m-1;
  38. else if(x>v[m])
  39. st=m+1;
  40. }
  41. return poz;
  42. }
  43.  
  44. int CBD(int st, int dr, long long x)
  45. {
  46. int m, poz=0;
  47. while(st<=dr)
  48. {
  49. m=(st+dr)/2;
  50. if(x == v[m])
  51. poz=m, st=m+1;
  52. else if(x>=v[m])
  53. st=m+1;
  54. else if(x>v[m])
  55. dr=m-1;
  56. }
  57. return poz;
  58. }
  59.  
  60. int main()
  61. {
  62. int x, y, ct=0;
  63.  
  64. ReadSort();
  65. ///generam toate puterile lui 2
  66. Generare();
  67.  
  68. ///formam perechi
  69. for(int i=1; i<n; i++)
  70. for(int j=1; j<=30; j++)
  71. {
  72. x=CBS(i+1, n, v[j]-a[i]);
  73. y=CBD(i+1, n, v[j]-a[i]);
  74. ct+= (y-x+1);
  75. }
  76.  
  77. cout << ct;
  78. return 0;
  79. }
RAW Paste Data