RECTSQ, am I unable to understand?

cakewalk
karthikv1392
rectsq

#1

https://www.codechef.com/problems/RECTSQ

My Code:

#include <stdio.h>

int ans;
int finder (int a, int b)
{
	if(b > a)
		{
			a += b;
			b = a-b;
			a = a-b;
		}
	
	int k = a/b;
	ans += k;
	if(a-(k*b))
		finder((a-(k*b)),b);
	else
		return 0;
}	
int main()
{
	int t;
	scanf(" %d",&t);
	while(t--)
		{
			int a, b;
			scanf(" %d%d",&a,&b);
			ans = 0;
			finder(a,b);
			printf("%d

",ans);
}
}

I know it is giving output as 3 even for the sample testcases given in the question, while the desired ones are 6 and 6.
But I want to ask that if we have to return the minimum number of square plots then why is this incorrect?
Take the first case 10, 15 for example,
Square 1: 10x10 (5x10 remains from original 10x15)
Square 2: 5x5 (5x5 remains from original 5x10)
Square 3: 5x5 (Return to main)

So Minimum is 3 squares, why is 6 the answer?
I think maybe I understood the question wrong, please help.

Thank You


#2

You should assign the value returned by the function finder to ans

Write ans=finder(a,b)


#3

He wants “minimum possible square plots to maximize profits”. Bit ambiguous but what the problem asks is, divide the land into minimum number of squares of Same size.

so 10 x 15 can be divided into 6 5x5 blocks

and 4 x 6 into 6 2x2 blocks

I hope i was clear enough, if not feel free to comment.


#4

In all these cases, one reference to some of the AC codes always helps.

The problem statement, by all means, is ambiguous because it doesnt state that the squares are of same size. However, if you have a look at few AC codes, you will instantly get what the problem is about. Its always better to give one of the codes a look to see if you can instantly get an answer to your query (because you might have to wait in discuss forums for someone to answer- though you got lucky this time XD)


#5

This too xD.


#6

BTW,I don’t understand your logic but you can do like this.

First find gcd

g=gcd(a,b)

Then final answer is (ab)/(gg)


#7

Thanks! :smiley:


#8

@hruday no need to do ans=finder(a,b). ans is a global variable so that is not required, for those who will say global variable will produce problems for more than 1 cases, please read the code it is initialized to 0 for every new case.
Thank You :slight_smile:


#9

My logic is to divide the biggest side with smallest side the result will be the number of squares that can be formed within, for eg: 15/10 = 1.5 = 1(int) therefore 1 square of 10x10 is eliminated (since k = 1 and b = 10 therefore I subtract that with a (=15) to get 5, then I get a 5x10 rectangle (which is true, thats what I should get) and then I call finder again and solve 5x10 likewise (recursion) :slight_smile:


#10

@vehemos

ans may be a global variable,but if you don’t assign anything to ans it will always print a garbage value.


#11

@hruday please read the comment and code xD I already assigned 0 to it and it will never print garbage value :stuck_out_tongue:


#12

I looked at 2 codes one of them had something like a^=b^=c and the other one will win #1 in world obfuscation challenge cuz of its indentation xD Then I gave up on reading others code, but in past whenever I got stuck that’s what I used to (and will keep doing :P)


#13

How are you able to ask questions with low karma ? Amazing :smiley:


#14

Lol hahaha. Sad luck! I got the simplest code possible in first try. Well, on average, it takes around 6-7 tries to get an understandable code. Or, keep track of some good coders and see if one of them solved the question.


#15

Karma requirement to ask Q is just 3, thats why :stuck_out_tongue:


#16

he using recursion, the function should have void as a return type, but works anyways


#17

@divyansh_gaba7 please explain to @vehemos that he is not assigning the value returned by the function finder to ans.


#18

@vehemos if you don’t know then try to learn from others but don’t tell that others are wrong without knowing


#19

global variables are assigned to zero by default. He is initializing it before every function call from main. only wrong thing he is doing is he doesn’t have finder as void return type, which btw doesn’t really matter except its not good practice.


#20

Function finder is returning an integer so it should have return type integer.But there should be some variable in the main function to catch that integer returned by finder.