# 2) Choose integers so that average is close to given real nu

a guest
Jan 9th, 2015
174
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2.
3. using namespace std;
4. #include <cmath>
5. #include <set>
6.
7. set<long> bestAverage(double target, long first, long range)
8. {
9.     set<long> ret;
10.
11.     double bestError = range;
12.     long bestDivider = 0;
13.     long bestIncrement;
14.     long divider;
15.
16.     if (target < first)
17.     {
18.         ret.insert(first);
19.         return ret;
20.     }
21.     if (target > first + range - 1)
22.     {
23.         ret.insert(first + range - 1);
24.         return ret;
25.     }
26.
27.     for(divider = 1; divider < range; divider++)
28.     {
29.         // find the franctions with given divider we can reach by averaging in the [first, first+range[ range
30.         double lowerBound = (first + (first + divider - 1)) / 2.0;
31.         double higherBound = ((first + range - 1) + (first + range - divider)) / 2.0;
32.         // there exists a set with average in the range [lowerBound, higherBound] of the form n/divider
33.
34.         double c1 = floor(target * divider) / divider;
35.         double c2 = ceil(target * divider) / divider;
36.         double error = min(target - c1, c2 - target);
37.
38.         if ((lowerBound <= target) && (target <= higherBound) && (error < bestError))
39.         {
40.             bestError = error;
41.             bestDivider = divider;
42.             if (target - c1 < c2 - target)
43.             {
44.                 bestIncrement = (long)floor((target - lowerBound) * divider);
45.             }
46.             else
47.             {
48.                 bestIncrement = (long)ceil((target - lowerBound) * divider);
49.             }
50.         }
51.     }
52.
53.     if (bestDivider == 0)
54.     {
55.         return ret;
56.     }
57.
58.     long incrementLarge = range - bestDivider; // how many increment (from the least possible average) of 1/divider we make my moving an integer all the way from one side of the range to the other
59.     long numberLarge = bestIncrement / incrementLarge; // how many integers we move all the way (integer division: rounds down)
60.     long numberSmall = bestDivider - numberLarge;
61.     long remainder = bestIncrement - numberLarge * incrementLarge;
62.
63.     if (remainder > 0)
64.     {
65.         numberSmall--;
66.     }
67.
68.     for(long index = 0; index < numberSmall; index++)
69.     {
70.         ret.insert(first + index);
71.     }
72.
73.     if (remainder)
74.     {
75.         ret.insert(first + numberSmall + remainder);
76.     }
77.
78.     for(long index = 0; index < numberLarge; index++)
79.     {
80.         ret.insert(first + range - numberLarge + index);
81.     }
82.
83.     return ret;
84. }
85.
86. int main()
87. {
89.     set<long>::iterator it;
90.
91.     double target = 3.1415926536;
92.     double sum = 0;
93.
94.     cout << "target is " << target << endl;
95.
96.     answer = bestAverage(target, -100, 200);
97.
98.     cout << "Average of " << endl;
100.     {
101.         cout << *it << ", ";
102.         sum += *it;
103.     }
104.     cout << endl << " is " << sum / answer.size() << endl;
105.
106.     return 0;
107. }
RAW Paste Data