Codeforces Beta Round #62

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

Tutorial

Problem 1:

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[0] >> p[1] >> p[2] >> p[3] >> 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[0] % p[1] % p[2] % p[3])
            {
                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;
}

Problem 2:

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[0];
    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;
}

Problem 3:

Solution:

Source Code:

Problem 4:

Solution:

Source Code:

Problem 5:

Solution:

Source Code: