Friday, March 1, 2013

The Best Box(codejam problem solved)

Question: Johnny needs to make a rectangular box for his physics class project. He has bought P cm of wire and S cm2 of special paper. He would like to use all the wire (for the 12 edges) and paper (for the 6 sides) to make the box. What is the largest volume of the box that Johnny can make? Input The first line contains t, the number of test cases (about 10). Then t test cases follow. Each test case contains two integers P and S in a line (1 ≤ P ≤ 40000, 1 ≤ S ≤ 20000). You may assume that there always exists an optimal solution for the given input cases. Output For each test case, print a real number that is the largest volume of the box that Johnny can make, rounded to two decimal places. Example Input: 2 20 14 20 16 Output: 3.00 4.15 Output details First case: the dimensions of the largest box may be 3, 1 and 1. Second case: the dimensions of the largest box may be 7/3, 4/3 and 4/3. Link to this question At first I couldn't do this but after having a look at this solution it became easier.. test cases have their importance... Original Soln==>http://www.codechef.com/viewsolution/701328
from math import sqrt
def highest_vol(p,s):
    """
    s=2(lb+bh+hl)==>formula for surface area of cuboid
    p=4(l+b+h)=====>Sum of all edges
    based on test case results given we can observe that b=h substitute in the above equations
    l=p/4-2h
    3h^2-ph/2+s/2=0 solve this quadratic for h1,h2
    """
    constant=sqrt(p*p-24*s)
    H=[(p+constant)/12.,(p-constant)/12.]
    L=[(p-8*H[0])/4.,(p-8*H[1])/4.]
    V=[L[0]*H[0]*H[0],L[1]*H[1]*H[1]]
    return max(V)
inp=int(raw_input())
for i in range(inp):
     p,s= map(int, raw_input().split())
     print '%0.2f' % highest_vol(p,s)


No comments:

Post a Comment