In a school, a teacher is assigned to distribute the Cadbury to the students for Independence Day. The teacher has a box full of Cadbury with different width and height. He can only distribute the largest square shape Cadbury. So if he has a Cadbury of length 10 and width 5, then he needs to break the Cadbury in 5×5 square and distribute to the first student and then the remaining 5×5 square to the next student in the queue. The program must accept four integers P, Q, R and S representing the minimum length, maximum length, minimum width and maximum width of Cadbury in the box as the input. The program must print the total number of students who will get the Cadbury as the output.
Boundary Condition(s):
1 <= P < Q <= 1500
1 <= R < S <= 1500
Input Format:
The first line contains P, Q, R and S separated by a space.
Output Format:
The first line contains the total number of students who will get the Cadbury.
Example Input/Output 1:
Input:
5 6 3 4
Output:
14
Explanation:
There are four possible sizes of Cadbury.
5×3, 5×4, 6×3 and 6×4.
The size of the first Cadbury is 5×3.
The first student gets 3×3. The size of the remaining Cadbury is 2×3.
The next student gets 2×2. The size of the remaining Cadbury is 2×1.
The next two students get 1×1 each.
So 4 students can get the Cadbury from the 5×3 Cadbury.
The size of the second Cadbury is 5×4.
The first student gets 4×4. The size of the remaining Cadbury is 1×4.
The next four students get 1×1 each.
So 5 students can get the Cadbury from the 5×4 Cadbury.
The size of the third Cadbury is 6×3.
The first two students get 3×3 each.
So 2 students can get the Cadbury from the 6×3 Cadbury.
The size of the fourth Cadbury is 6×4.
The first student gets 4×4. The size of the remaining Cadbury is 2×4.
The next two students get 2×2 each.
So 3 students can get the Cadbury from the 6×4 Cadbury.
Hence 14 students can get the Cadbury from the box. So 14 is printed as the output.
Example Input/Output 2:
Input:
1 3 10 12
Output:
67
#include<stdio.h>
#include <stdlib.h>
#define mini(a,b) a<b ? a: b
int fun(int x,int y){
int ans=0;
while(x>0 && y>0){
int min=mini(x,y);
if(x==y){
x-=min;
y-=min;
}
else if(x<y){
y=y-min;
}
else{
x=x-min;
}
ans++;
}
return ans;
}
int main()
{
int p,q,r,s;
scanf("%d%d%d%d",&p,&q,&r,&s);
int ans=0;
for(int i=p;i<=q;i++){
for(int j=r;j<=s;j++){
ans+=fun(i,j);
}
}
printf("%d",ans);
return 0;
}LH,UH,LW,UW = map(int,input().split())
dct = {}
max_len = 0
count = 0
def f(x,y):
global count, max_len
count += 1
if x<y:
x, y = y,x
if x==0 or y==0:
return 0
if x==y:
return 1
else:
#return 1+f(x-y,y)
#'''
if (x,y) not in dct:
dct[(x,y)] = 1+f(x-y,y)
if len(dct)>max_len: max_len = len(dct)
if ((x-y,y) in dct): del dct[(x-y,y)]
return dct[(x,y)]
#'''
res = 0
for i in range(LH,UH+1):
for j in range(LW,UW+1):
res += f(i,j)
print(res)def f(a,b):
if a and b:
return a//b+f(a%b,b) if a>b else b//a+f(a,b%a)
return 0
p,q,r,s=map(int,input().split())
t=0
for i in range(p,q+1):
for j in range(r,s+1):
t+=f(i,j)
print(t)
