its failing for 9*12 with n=7, if i take max square considered of hcf(9,12), left space is 6*6 and 3*3. i'll have more left space than what i consider three 4*4 squares, four 1*1 squares. leftspace is 1*5. i think needs different trick
surender On Mon, Jul 11, 2011 at 9:59 PM, Yogesh Yadav <[email protected]> wrote: > > largest size of square would be = H.C.F of width and height . > > now with size known we have to just arrange squares > > this can be done such that we can make a big square by adding them... > > for ex 1st square can be made by just (1 square) > 2nd square can be made by adding 3 sqaures around it like 1 > 2 //suppose 2,3,4 are newly addded squares > > 4 3 > 3rd square can be made by adding 5 sqaures around it like 1 2 5 > > 3 4 6 > > 9 8 7 > 4th square can be made by adding 7 sqaures around it like 1 2 5 > 10 > > 3 4 6 11 > > 9 8 7 12 > > 13141516............ and so on > > so we have to first check the no of squares and try to make largest > possible square...*we have to check also that the largest possible square > should not exceed either length or breadth.*...... and then we can add > rest around it anywhere > > > in this case height =3, width=2 so HCF=1 > > hence side of square will be 1 > > and n=5 given ...so largest possible square can be of 4.... and rest can be > added around it... > > > On Sun, Jul 10, 2011 at 10:44 PM, vaibhav shukla > <[email protected]>wrote: > >> with n=(height*width)/side^2 .. u can calculate the side if n would be >> given. >> >> >> On Sun, Jul 10, 2011 at 10:37 PM, vaibhav agarwal < >> [email protected]> wrote: >> >>> @vaibhav this fails as n will be provided in the question. >>> >>> >>> On Sun, Jul 10, 2011 at 9:56 PM, vaibhav shukla <[email protected] >>> > wrote: >>> >>>> wastage can be minimized if side of square is maximized. >>>> so largest size of square would be = H.C.F of width and height . >>>> >>>> and also number of squares needed will be = (width*height)/side^2 . >>>> >>>> >>>> >>>> On Sun, Jul 10, 2011 at 9:11 PM, Akshata Sharma < >>>> [email protected]> wrote: >>>> >>>>> Given a rectangle with known width and height, design an algorithms to >>>>> fill the rectangle using n squares(n is integer, also given) and make sure >>>>> in the result the wasting area is minimized. Length of square doesn't have >>>>> to be integer. >>>>> I.e, given width=3,height=2,n=5, one solution is that rectangle can be >>>>> filled with five 1x1 squares and the wasting area is 1. Another solution >>>>> could be filled with five 0.9x0.9 squares, but the wasting area is more >>>>> than >>>>> first solution. >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Algorithm Geeks" group. >>>>> To post to this group, send email to [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]. >>>>> For more options, visit this group at >>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>> >>>> >>>> >>>> >>>> -- >>>> best wishes!! >>>> Vaibhav Shukla >>>> DU-MCA >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To post to this group, send email to [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> best wishes!! >> Vaibhav Shukla >> DU-MCA >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
