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. *********************************************************************************** Problem 2) Problem 2: Lavanya's Tower Lavanya has collection of cubes that can be stacked up to form a tower. She has cubes in three colours Green, Blue and Red. There are G green cubes, B blue cubes and R red cubes. Lavanya wants to know how many different towers she can build using all her cubes. For example, if she has 2 green cubes, 2 blue cubes and a red cube, then she can form 20 towers as listed here: rggbr, grgbb, ggrbb, ggbrb, ggbbr, gbgbr, gbgrb, gbrgb, grbgb, rgbgb, bbggr, bbgrg, bbrgg, brbgg, rbbgg, bgbgr, bgbrg, bgrbg, brgbg, rbgbg Given a description of Lavanya's cubes, your task is to determine the total number of different towers she can build. Of course, this number could be very large. Since Lavanya only knows numbers upto 10000, it is sufficient to calculate the answer modulo 10000. Input format A single line with three integers G, B and R giving the number of green, blue and red cubes respectively. Output format A single integer giving the number of different towers modulo 10000. Test data You may assume that G, B, R = 300. Example Here is a sample input and output corresponding to the example discussed above. Sample input 2 2 1 Sample output 20 ************************************************************************ Solution; I don't why the answer is 20, it should be 30 for 2G,2B,1R by 5!/(2!*2!). The author seems to do 5!/3! which i don't understand . Second is rggbr, grgbb, ggrbb, ggbrb, ggbbr, gbgbr, gbgrb, gbrgb, grbgb, rgbgb, bbggr, bbgrg, bbrgg, brbgg, rbbgg, bgbgr, bgbrg, bgrbg, brgbg, rbgbg the number of towers with "r" as base is only 4 where as it should be 6. Am i wrong. My answers would be rggbb rbbgg rbgbg rgbgb rgbbg ( i don't know why these were excluded ) rbggb ******************************************************** Seems like iarcs has no forum or contacts for corrections . If you know any please let me know. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
