PROBLEM LINK:
Author: catchmeifyouca
Tester: catchmeifyouca
Editorialist: catchmeifyouca
DIFFICULTY:
MEDIUM -HARD
PREREQUISITES:
Integral Calculus , Binary Search
PROBLEM:
Alfie Solomons was a rum distillery owner in Camden town in the era of peaky blinders he was known for betting on horse races and also for making special kind of jars. Property of these jars was they were not regular but had some fancy shapes. Suppose the shape of the jar is same as that of revolving the curve of polynomial f(z) between z= zlow and z=zhigh around the z-axis .Therefore the z axis coincides with the vertical line through the centre of. The bottom of the jar is formed by a solid circular region at z = zlow, and the top of the bottle, at z = zhigh , is left open .For Example a bottle formed using the simple polynomial 4 − 0.25z, with zlow = 0 and zhigh = 12. The bottom of this jar is a circle with a radius of 4, and the opening at the top is a circle with a radius of 1. The height of this jar is 12. Volume markings are in increments of 25. Given a polynomial P, zlow, zhigh, and the volume increment (inc) between successive marks on the jar, compute the distances up from zlow for the marks at successive volume increments. A mark cannot be made past the top of the jar, and no more than the first 8 increments should be marked. Assume the value of P is greater than zero everywhere between zlow and zhigh. Input:- First Line contains the integer n degree of polynomial Second Line contains the coefficients of the polynomial f(z) = anzn + an−1z n−1 + . . . + a2z 2 + a1z + a0 Third Line contains 1) zl and zh, the boundaries of the bottle (−100 ≤ zlow < zhigh≤ 100 and zh − zl > 0.1) 2)inc, an integer which is the volume increment before each successive mark on the bottle (1 ≤ inc ≤ 500). Output:- Display the volume of the full jar on one line. On a second line, display the increasing sequence of no more than 8 successive distances up from the bottom of the jar for the volume markings. All volumes and height marks should be accurate to two decimal places. If the jar does not have a volume that allows at least one mark, display the phrase insufficient volume. No test case will result in a mark within 0.01 from the top of the jar. The volume of the jar will not exceed 1 000. All rounded distances for marks on a jar differ by at least 0.05.
Sample input:- 10 0.01 25.6 -57.6 76.8 -67.2 40.32 -16.8 4.8 -0.9 0.1 -0.005 0.0 4.0 143 10 12.0 0.0 -2.835 0.0 0.23625 0.0 -0.007875 0.0 0.000140625 0.0 -0.0000015625 -4.0 1.2 120 10 14 14 14 14 14 14 14 14 14 14 14 -1.0 0.5 100 10 23 -23 23 -23 23 -23 23 -23 23 -23 23 0.0 1.0 100
Output:- Case 1: 286.38 2.00 3.91 Case 2: 998.13 2.80 3.23 3.55 3.82 4.09 4.36 4.66 5.04 Case 3: 958.41 0.35 0.70 0.93 1.09 1.20 1.29 1.37 1.43 Case 4: 925.05 0.06 0.14 0.22 0.32 0.43 0.56 0.72 0.88
EXPLANATION:
Here basically in this problem we are given a polynomial F(z) we then rotate it along z axis to calculate the volume of the whole shape of the jar.
Here so volume of ∫▒π 〖(f(z))〗^2.dz . So in total we have to integrate the function from limits zl to zh.
Hence total volume will be ∫_zl^zh▒〖π〖(f(z))〗^2.dz〗. So total volume wiil be calculated by this here. Here integral can be will be calculated by ∑_(i=0)^n▒∑_(j=0)^n▒(ai.aj)/(i+j+1). The only remaining aspect of the problem is where to put the height marks. Observe that as we move from left to right, the volume of the bottle strictly increases, and so we can use binary search to find values of x at which the volume is a multiple inc.
Finally, there is one edge case to consider: when no height marks should be made, i.e., when the bottle is smaller than inc. There are many to check this, including computing the total volume before starting your binary search, or by counting the total number of height marks made before reaching the top of the bottle or the imposed maximum of 8.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define PI (2.0 * acos(0.0))//Here we have predefined pie
#define EPS 1E-5//
int n;
double Q[22];
double volume(double x) {
double powers[22], sum = 0.0;
powers[0] = 1.0;
for (int i = 1; i <= 2 * n + 1; i++)
sum += (powers[i] = powers[i - 1] * x) * Q[i];
return sum;
}
double bin_search(double lo, double hi, double t) {
if (abs(hi - lo) < EPS)
return lo;
double mid = (hi + lo) / 2;
if (volume(mid) < t)
return bin_search(mid, hi, t);
else
return bin_search(lo, mid, t);
}
int main() {
int caseno = 0;
double v, x, P[11], zlow, zhigh, inc;
while (++caseno && scanf(“%i”, &n) == 1) {
for (int i = 0; i <= n; i++)
scanf(“%lf”, P + i);
scanf(“%lf%lf%lf”, &zlow, &zhigh, &inc);
fill(Q, Q + 22, 0.0);
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
Q[i + j + 1] += P[i] * P[j] * PI / (i + j + 1);
v = volume(zlow);
printf("Case %i: %.02f\n", caseno, volume(zhigh) - v);
for (int k = 0; k < 8; k++)
if ((x = bin_search(zlow, zhigh, v += inc)) > zhigh - EPS) {
if (k == 0)
printf("insufficient volume");
break;
} else
printf("%s%.2f", k > 0 ? " " : "", x - zlow);
printf("\n");
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define PI (2.0 * acos(0.0))//Here we have predefined pie
#define EPS 1E-5//
int n;
double Q[22];
double volume(double x) {
double powers[22], sum = 0.0;
powers[0] = 1.0;
for (int i = 1; i <= 2 * n + 1; i++)
sum += (powers[i] = powers[i - 1] * x) * Q[i];
return sum;
}
double bin_search(double lo, double hi, double t) {
if (abs(hi - lo) < EPS)
return lo;
double mid = (hi + lo) / 2;
if (volume(mid) < t)
return bin_search(mid, hi, t);
else
return bin_search(lo, mid, t);
}
int main() {
int caseno = 0;
double v, x, P[11], zlow, zhigh, inc;
while (++caseno && scanf(“%i”, &n) == 1) {
for (int i = 0; i <= n; i++)
scanf(“%lf”, P + i);
scanf(“%lf%lf%lf”, &zlow, &zhigh, &inc);
fill(Q, Q + 22, 0.0);
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
Q[i + j + 1] += P[i] * P[j] * PI / (i + j + 1);
v = volume(zlow);
printf("Case %i: %.02f\n", caseno, volume(zhigh) - v);
for (int k = 0; k < 8; k++)
if ((x = bin_search(zlow, zhigh, v += inc)) > zhigh - EPS) {
if (k == 0)
printf("insufficient volume");
break;
} else
printf("%s%.2f", k > 0 ? " " : "", x - zlow);
printf("\n");
}
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define PI (2.0 * acos(0.0))//Here we have predefined pie
#define EPS 1E-5//
int n;
double Q[22];
double volume(double x) {
double powers[22], sum = 0.0;
powers[0] = 1.0;
for (int i = 1; i <= 2 * n + 1; i++)
sum += (powers[i] = powers[i - 1] * x) * Q[i];
return sum;
}
double bin_search(double lo, double hi, double t) {
if (abs(hi - lo) < EPS)
return lo;
double mid = (hi + lo) / 2;
if (volume(mid) < t)
return bin_search(mid, hi, t);
else
return bin_search(lo, mid, t);
}
int main() {
int caseno = 0;
double v, x, P[11], zlow, zhigh, inc;
while (++caseno && scanf(“%i”, &n) == 1) {
for (int i = 0; i <= n; i++)
scanf(“%lf”, P + i);
scanf(“%lf%lf%lf”, &zlow, &zhigh, &inc);
fill(Q, Q + 22, 0.0);
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
Q[i + j + 1] += P[i] * P[j] * PI / (i + j + 1);
v = volume(zlow);
printf("Case %i: %.02f\n", caseno, volume(zhigh) - v);
for (int k = 0; k < 8; k++)
if ((x = bin_search(zlow, zhigh, v += inc)) > zhigh - EPS) {
if (k == 0)
printf("insufficient volume");
break;
} else
printf("%s%.2f", k > 0 ? " " : "", x - zlow);
printf("\n");
}
return 0;
}