## Friday, March 18, 2011

### Codeforces Beta Round #62

Mar 18, 2011.
Accepted: 0.        WA: 2.        NotTried: 3.

## Tutorial

### Solution:

Naive method: Go through all of the permutations and then check the condition. O(24 * n), n is the number of elements.

Advanced method: After checking on the condition, if i-th element is smaller than those four integer, then this number will satisfy any permutation.

The reason I got WA is: I didn't sort the p before I start using the next_permuation function.

### Source Code:

//Friday, March  18, 2011 10:41 CDT
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, char* argv[])
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
vector<int> p(4, 0);
int a, b;
cin >> p >> p >> p >> p >> a >> b;
vector<int> pickup(b - a + 1, 0);
sort(p.begin(), p.end());
do
{
for (int i = a; i <= b; i++)
{
if (i == i % p % p % p % p)
{
pickup[i - a]++;
}
}
}
while (next_permutation(p.begin(), p.end()));
int count = 0;
for (int i = 0; i < pickup.size(); i++)
if (pickup[i] >= 7)
count++;
cout << count << endl;
//fclose(stdin);
//fclose(stdout);
return 0;
}

### Solution:

Use binary search, lower limit could be the smallest element, the upper limit should be largest element or the average of all the elements.
The reason I got the WA is: my esp(10^-10) is too small, 10^-8 should be small  enough.

### Source Code:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, char* argv[])
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
double n, k;
cin >> n >> k;
vector<double> energy((int) n, 0.0);
for (int i = 0; i < n; i++)
cin >> energy[i];
sort(energy.begin(), energy.end());
double first = energy;
double last = energy[n - 1];
if (first == last)
{
cout << fixed << setprecision(9) << first << endl;
return 0;
}
while (first < last)
{
//cout << first << ", " << last << endl;
double mid = (first + last) / 2.0;
//cout << setprecision(10) << mid << endl;
double sum = 0.0;
for (int i = 0; i < n; i++)
{
if (energy[i] > mid)
sum += (energy[i] - mid) * (100 - k) / 100.0;
else
sum += energy[i] - mid;
}
if (fabs(sum) < 0.000000001)
{
cout << fixed << setprecision(9) << mid << endl;
break;
}
else if (sum > 0.0)
{
first = mid;
}
else if (sum < 0.0)
last = mid;
}
//fclose(stdin);
//fclose(stdout);
return 0;
}