You are not logged in. Please login at www.codechef.com to post your questions!

×

RECTSQ, am I unable to understand?

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\n",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

asked 06 Jun '17, 22:28

vehemos's gravatar image

1★vehemos
356
accept rate: 0%

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

(07 Jun '17, 02:03) godslayer121★

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

(07 Jun '17, 02:49) vijju123 ♦♦4★

Okay got it @vijju123

(07 Jun '17, 15:43) godslayer121★

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.

link

answered 06 Jun '17, 22:43

divyansh_gaba7's gravatar image

4★divyansh_gaba7
76818
accept rate: 23%

edited 06 Jun '17, 22:51

Thanks! :D

(06 Jun '17, 23:14) vehemos1★

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)

link

answered 06 Jun '17, 23:14

vijju123's gravatar image

4★vijju123 ♦♦
15.4k12066
accept rate: 18%

1

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)

(07 Jun '17, 01:52) vehemos1★

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.

(07 Jun '17, 02:48) vijju123 ♦♦4★

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

Write ans=finder(a,b)

link

answered 06 Jun '17, 22:39

hruday968's gravatar image

4★hruday968
1.7k210
accept rate: 14%

This too xD.

(06 Jun '17, 22:45) divyansh_gaba74★

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)

(06 Jun '17, 22:46) hruday9684★

@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 :)

(06 Jun '17, 23:15) vehemos1★

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) :)

(06 Jun '17, 23:17) vehemos1★

@vehemos

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

(06 Jun '17, 23:37) hruday9684★

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

(07 Jun '17, 01:51) vehemos1★

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

(07 Jun '17, 07:54) divyansh_gaba74★

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

(07 Jun '17, 12:58) hruday9684★

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

(07 Jun '17, 12:59) hruday9684★

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.

(07 Jun '17, 14:26) divyansh_gaba74★

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.

(07 Jun '17, 14:36) hruday9684★

you don't understand his function it seems :(. The actual result is already stored in global variable "ans" which he prints. Finder always returns 0.

(07 Jun '17, 14:44) divyansh_gaba74★

oh yes,sorry i didn't see that.he is adding k to ans.

(07 Jun '17, 14:53) hruday9684★

"@vehemos if you don't know then try to learn from others but don't tell that others are wrong without knowing" @hruday968 ok, I'm listening tell me where I'm wrong, but just 1 thing ans=finder WILL NOT WORK cuz it reutrn 0 when recursion is finished, I may not be better than you but I am aware of what I wrote, but if you still find it wrong tell me why it is and I will remove/improve on it Thanks. @divyansh_gaba7 I didn't know it was bad practice sorry, initially I was returning via that finder function only but afterwards I declared global to make it simpler, that's why the int remained.

(07 Jun '17, 15:40) vehemos1★

@vehemos sorry i didn't see this thing (ans+=k) and thought you was wrong.

(07 Jun '17, 16:02) hruday9684★
1

@hruday968 np it happens, though you did make me bang my head over wall thinking why I should do ans = finder :P I had to retest my code 3 times to gain my confidence back xD Happy Coding! :D

(07 Jun '17, 16:07) vehemos1★
showing 5 of 16 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,646
×9
×4

question asked: 06 Jun '17, 22:28

question was seen: 586 times

last updated: 18 Jan, 19:06