2
\$\begingroup\$

Dole Out Cadbury

Problem Description

You are a teacher in reputed school. During Celebration Day you were assigned a task to distribute Cadbury such that maximum children get the chocolate. You have a box full of Cadbury with different width and height. You can only distribute largest square shape Cadbury. So if you have a Cadbury of length 10 and width 5, then you need to break Cadbury in 5X5 square and distribute to first child and then remaining 5X5 to next in queue

Constraints

\$0<P<Q<1501\$
\$0<R<S<1501\$

Input Format

First line contains an integer P that denotes minimum length of Cadbury in the box
Second line contains an integer Q that denotes maximum length of Cadbury in the box
Third line contains an integer R that denotes minimum width of Cadbury in the box
Fourth line contains an integer S that denotes maximum width of Cadbury in the box

Output
Print total number of children who will get chocolate.

Timeout
1

Example

Input

5
7
3
4

Output

24

Explanation

Length is in between 5 to 7 and width is in between 3 to 4.
So we have 5X3,5X4,6X3,6X4,7X3,7X4 type of Cadbury in the box. If we take 5X3:

First, we can give 3X3 square Cadbury to 1st child .Then we are left with 3X2. Now largest square is 2X2 which will be given to next child. Next, we are left with two 1X1 part of Cadbury which will be given to another two children.
And so on.

Here is my code, which works but returns . I'm looking for optimizations.

def cadbury(l,b):
    count = 0
    while True:
        lon=max(l,b)
        sh=min(l,b)
        count+=1
        diff=lon-sh
        if diff==0:
            return count
        else :
            l=min(l,b)
            b=diff
minl=int(input())
maxl=int(input())
minw=int(input())
maxw=int(input())
count=0
for i in range(minl,maxl+1):
    for j in range(minw,maxw+1):
        count+=cadbury(i,j)
print(count)
\$\endgroup\$
7
  • 5
    \$\begingroup\$ Did you consider to reuse results computed in the while loop of the cadbury function instead of computing these again and again with every call? \$\endgroup\$ Commented Jul 17, 2020 at 13:48
  • \$\begingroup\$ I thought of reusing it. so only i asked for help \$\endgroup\$ Commented Jul 18, 2020 at 14:09
  • 1
    \$\begingroup\$ Implement such a code that's working, and we willl happily suggest improvements of it for you. \$\endgroup\$ Commented Jul 18, 2020 at 14:41
  • 1
    \$\begingroup\$ There is an abstraction for repeat subtraction until not enough is left. \$\endgroup\$
    – greybeard
    Commented Jul 19, 2020 at 5:00
  • 2
    \$\begingroup\$ I agree this is a poorly written question and the initial revision could've used some more effort. However, a quick test indicates it does work so the the current 4 close votes it has that claim it doesn't should either be backed up with an example case or be retracted. \$\endgroup\$
    – Mast
    Commented Jul 24, 2020 at 18:38

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.