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.