Please ignore . my mistake. Terry wrote: > What about problem 1 ? i am really puzzled . > > > Problem 1: The Hunpur Visa > > Hunpur lies to the north of Siruseri and flights from Siruseri to many > parts of the world go through Samosa Airport, the busiest airport in > Hunpur. Hunpur demands that residents of Siruseri obtain "transit > visas" in order to fly through Samosa. > > Recently, the authorities of Hunpur have enforced some strange rules > regarding photographs to be submitted for obtaining visas. The size of > the face in the photograph is measured along K different directions to > get the numbers (m1,m2, ...,mK). The consulate has specified a lower > bound and upper bound (li and ui respectively) along each of the K > directions. So, a photograph with measurements (m1, m2, ...,mK) is > accepted if and only if li = mi = ui for 1 = i = K. Otherwise, > it is rejected. > > For example, if K =2 with l1 = 32, u1 = 36, l2 = 20 and u2 = 24, a > photograph with measurements (33,20) would be accepted, but photographs > with measurements (31,20) or (36,25) would be rejected. > > Many studios in Siruseri have come up with a partial solution to this > problem. They digitally alter the image. They have a fixed collection > of M "operations". Each operation is a tuple (d1, d2, ...,dK), where > each di is a (positive or negative) integer. The effect of this > operation on a image with dimensions (m1,m2, ...,mK) is to change the > dimensions to (m1+d1, m2+d2, ..., mK+dK). The studio cannot apply more > than two operations on a photograph as it damages the quality of the > image. Moreover, no operation can be applied more than once. > > For example, using the operations (-2,3) and (3,-1) we can transform an > image of size (31,20) to one of size (32,22) which would be accepted by > the Hunpur consulate. On the other hand, using these operations we > cannot alter an image of size (36,25) to an acceptable one. > > Your task is to determine whether the photograph whose dimensions are > given can be altered using at most two operations to an acceptable > photograph. > > Input format > > The first line contains two integers K and M. The second line contains > K integers giving the lower bounds for the K directions. The third line > contains K integers giving the upper bounds for the K directions. This > is followed by M lines each containing K integers describing the M > different operations. This is followed by the last line containing K > integers specifying measurements of the photograph. > > Output format > > If it is not possible to alter the image using at the most 2 operations > then print a single line with the word NO. Otherwise, the first line of > the output must have the single word YES, the second line must contain > an integer i, indicating the number of operations (0 = i = 2) that > may be used to transform the image into an acceptable one, and this > should be followed by i lines describing the i operations. There may be > more than one way to transform the image into an acceptable one, it > suffices to print any one. > > Note: In this task, test inputs will be arranged in groups and marks > will be assigned for groups of test inputs rather than to each > individual test input. For example, one mark may be assigned for a > group of three test inputs. This means that to score that one mark your > program must run correctly on all three test inputs in the group. Thus, > blindly printing NO is not likely to score many marks. > > Test data > > You may assume that K = 100 and M = 100. > > Example > > Here is a sample input and output corresponding to the example > discussed above. > > Sample input > > 2 2 > 32 20 > 36 24 > -2 3 > 3 -1 > 31 20 > > Sample output > > YES > 2 > 3 -1 > -2 3 > ********************************************************************************** > Solution; > I think the answer will always be YES. > > we have numbers like (l1,u1) ,(l2,u2),(l3,u3)...(ln,un) and numbers m1 > ,m2,m3,...mn. > > now to map mi to (li,ui) , it is always possible (forgetting overflow). > Is something wrong with my understanding of the problem. So i can > always find a vector d1,d2,d3..,dn which maps m1,m2,m3...,mn between > (l1,u1),(l2,u2)...(ln,un) in a single operation or 0 operations (if > they already are in the range ). If a point is on x axis, then to move > them between 2 points on x axis requires 1 displacement.similarly for > other > > Comments please.
--~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
