Facebook
From Small Mosquito, 6 Months ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 62
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cstdlib>
  4. #include <ctime>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. void varianta_1(unsigned int v[], unsigned int n, unsigned int s)
  10. {
  11.     for(unsigned int i = 0; i < n; i++)
  12.     {
  13.         if(v[i] >= s/2)
  14.             break;
  15.  
  16.         unsigned int x = s - v[i];
  17.  
  18.         for(unsigned int j = i + 1; j < n; j++)
  19.         {
  20.             if(v[j] == x)
  21.             {
  22.                 cout << v[i] << ' ' << x << endl;
  23.                 break;
  24.             }
  25.  
  26.             if(v[j] > x)
  27.                 break;
  28.         }
  29.     }
  30. }
  31.  
  32. void varianta_2(unsigned int v[], unsigned int n, unsigned int s){
  33.  
  34.     for(unsigned int i = 0; i < n; i++)
  35.     {
  36.         if(v[i] >= s/2)
  37.             break;
  38.  
  39.         unsigned int x = s - v[i];
  40.  
  41.         unsigned int st = i + 1, dr = n-1;
  42.         while (st <= dr){
  43.             unsigned int mij = (st + dr)/2;
  44.             if (v[mij] == x){
  45.                 cout << v[i] << ' ' << x << endl;
  46.                 break;
  47.             } else {
  48.                 if (x < v[mij]){
  49.                     dr = mij-1;
  50.                 } else {
  51.                     st = mij + 1;
  52.                 }
  53.             }
  54.         }
  55.     }
  56. }
  57.  
  58. void generareTeste(const char nume_fisier[], unsigned int n)
  59. {
  60.     unsigned int i, vcrt, r, x, y;
  61.  
  62.     srand(time(NULL));
  63.  
  64.     ofstream fout(nume_fisier);
  65.  
  66.     fout << n << endl;
  67.     //primul numar este cuprins intre 1 si 100
  68.     vcrt = 1 + (rand() * rand()) % 100;
  69.     fout << vcrt << " ";
  70.  
  71.     //restul elementelor vor fi cuprinse intre vcrt+1  si vcrt+1000
  72.     x = y = 0;
  73.     for(i = 1; i < n; i++)
  74.     {
  75.         r = 1 + (rand() * rand()) % 1000;
  76.         vcrt = vcrt + r;
  77.  
  78.         //sansele ca r >= 500 sunt, teoretic, 50%
  79.         if(r >= 500)
  80.             if(x == 0)
  81.                 x = vcrt;
  82.             else if(y == 0)
  83.                 y = vcrt;
  84.  
  85.         fout << vcrt << " ";
  86.     }
  87.  
  88.     fout << endl << x + y << endl;
  89.  
  90.     fout.close();
  91. }
  92.  
  93. void citireDate(const char nume_fisier[], unsigned int v[], unsigned int &n, unsigned int &s)
  94. {
  95.     ifstream fin(nume_fisier);
  96.  
  97.     fin >> n;
  98.     for(int i = 0; i < n; i++)
  99.         fin >> v[i];
  100.     fin >> s;
  101.  
  102.     fin.close();
  103. }
  104. unsigned int v[1000000];
  105.  
  106. int main()
  107. {
  108.     unsigned int n, s;
  109.  
  110.     generareTeste("preturi.in", 1000000);
  111.  
  112.     citireDate("preturi.in", v, n, s);
  113.  
  114.     varianta_1(v, n, s);
  115.     cout << endl;
  116.     varianta_2(v, n, s);
  117.  
  118.     return 0;
  119. }
  120.