HackerRank 'Halloween Party' Solution | MartinKysel.com
Alex is attending a Halloween party with his girlfriend Silvia. At the party, Silvia spots the corner of an infinite chocolate bar..
If the chocolate can be served as only 1 x 1 sized pieces and Alex can cut the chocolate bar exactly K times, what is the maximum number of chocolate pieces Alex can cut and give Silvia?
http://analgorithmaday.blogspot.com/2014/08/maximum-number-of-pieces-with-cuts.html
Read full article from HackerRank 'Halloween Party' Solution | MartinKysel.com
Alex is attending a Halloween party with his girlfriend Silvia. At the party, Silvia spots the corner of an infinite chocolate bar..
If the chocolate can be served as only 1 x 1 sized pieces and Alex can cut the chocolate bar exactly K times, what is the maximum number of chocolate pieces Alex can cut and give Silvia?
http://analgorithmaday.blogspot.com/2014/08/maximum-number-of-pieces-with-cuts.html
what is the math logic here? when you divide any number by 2, you get a exact median of all the cuts. The median might be even or odd. The remaining value can be taken either as horizontal or vertical to maximize number of cuts (it doesn’t matter larger value need to be horizontal or vertical). You can event print out how many vertical & horizontal now safely. :)
This means if somebody asks you to cut a cake for 30 people, then try for a multiple of 30 which can give as exactly equal pieces(3x10 or 15x2 wont give as that, we need both the factors as much near as possible). So its (6+5) 11 cuts. (i.e) you put a 5 horizontal and then a 6 vertical cuts (or vice versa) to get 30 pieces total.
for(int i = 0; i < T; ++i)
{
long q, r, val;
cin>>val;
q = val / 2;
r = val - q;
out.push_back(q*r);
}The product a*b (where a+b = k) is maximal, when a is close to b as possible. We can only use integral values, so a and b are rounded halves of k.
def
oneOneBars(K):
half
=
K
/
/
2
return
half
*
(K
-
half)
if
__name__
=
=
'__main__'
:
t
=
input
()
for
_
in
xrange
(t):
k
=
input
()
print
oneOneBars(k)