http://www.spoj.pl/problems/PIE/
I solved this using Binary Search its similar to shake shake shaky of
spoj... but still get WA :(
Plzz help...
#include<iostream>
#include<algorithm>
using namespace std;
bool solve(int *pie, int n, int mid,int f)
{
int sum = 0;
for (int i=0; i<n; i++)
sum += pie[i] / mid;
if (sum >= f)
return true;
else
return false;
}
int binary_search(int *pie, int n, int f)
{
int low = 0, high = pie[n-1], mid;
while (low < high)
{
mid = low + (high - low + 1)/2;
if (solve(pie, n, mid, f))
low = mid;
else
high = mid - 1;
}
return low;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
const double pi = 3.14159265358979323846264338327950;
int T;
cin >> T;
while (T--)
{
int n, f, pie[10001];
cin >> n >> f;
for (int i=0; i<n; i++)
{
cin >> pie[i];
pie[i] *= pie[i];
}
f++;
sort(pie, pie + n);
int largest = binary_search(pie, n, f);
//cout << "largest is " << largest << endl;
double ans = largest * pi;
printf("%.4lf\n", ans);
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
