Recursion Problem from ECOO CS contest


#1

Hi,
I am using Python 3 and am practicing recursion. Here’s the problem.

Here’s my code:

from math import floor, log10


def square_packing(length, width):
    if length == 0 or width == 0:
        return 0

    min_side = min(length, width)
    power = floor(log10(min_side) / log10(2))
    side = 2 ** power
    max_side = max(length, width)
    m = max_side // side
    x = max_side % side
    y = min_side % side

    return m + square_packing(x, side) + square_packing(m * side, y) + square_packing(x, y)


a = eval(input())
b = eval(input())
print(square_packing(a, b))

It prints the correct output for all of the inputs except a 9999 x 8888 floor. Is there a problem in my code or does the question has a typo error?

Thanks!


#2

There is some disagreement between the sample input and the corresponding sample output, particularly on that set of parameters. One reads 9999 x 888 and the other 9999 x 8888. This could be the problem.

====== RESTART: D:/cc/discuss/users/coursecoder30879/square_packing.py ======
9999
888
4065
>>> 

That was your code. I did change three lines (below) to get around using eval(). The less attack vectors we allow, the better. That’s one of them we can easily dismiss. Granted it is a last resort tool, but deservedly so; and, it has a slough of provisos attached.

a = float(input('len: '))
b = float(input('wid: '))

print(int(square_packing(a, b)))
====== RESTART: D:/cc/discuss/users/coursecoder30879/square_packing.py ======
len: 9999
wid: 888
4065
>>> 

Dare I forget to mention, @coursecoder30879, nice piece of code. Good work!


#3

Thank you so much mtf!!! :slight_smile:


#4

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.