Srini's Web Collections

Programming Problems

C-on-test ~~~~~~~~~ Brought to you by CSEA, IITB in association with VERITAS software. ==================================================================

You are Dunce E. Dumdum, freshie at IIT Bombay, Powai - 400076. Having cracked a cool 3567 rank in IIT JEE after 5 years of concentrated mugging, you think that the future is bright and a gentle smile plays on your lips as you look around at the verdant green campus and the hallowed halls of learning. Little do you know what a dark, gloomy future awaits you. So here's already PROBLEM 1: Credits: 10 ~~~~~~~~~~ Filled with the enthusiasm and excitement of hostel life, you are exploring your new home when suddenly you bump into what appears to be a wall. Closer examination reveals the "wall" to be actually a gigantic, disgruntled and unshaven SENIOR. You politely say "Hi!". SENIOR just grunts in reply. You are about to continue when suddenly SENIOR booms out "Hey FRESHIE!". The plaster is still falling off the ceiling as you turn back with trembling legs. So starts a nice interactive session with SENIOR. One-way intros over, SENIOR starts asking more technical questions. Your slowly losing that gentle smile on your lips as the questions get livelier. But here comes a question which puts the g.s. back where it belongs: SENIOR says, " I will give you a number (N). Find positive integers `x' and `y' so that x^y + y^x = N, and the sum (x + y) is maximum." So your job is to find such x and y. Input: The integer N in a line by itself. Output: The values of x and y in the format x y on a line by themselves, separated by a blank. Any order of x and y is ok.

PROBLEM 2: Credits: 20 ~~~~~~~~~~ After many such encounters of the SENIOR kind, finally you feel that things are in order and the gentle smile, though mellowed with bitter experience, is still there. But a week's over, and so is your stock of undies, which number 7 (seven). You have realised that now you need to wash them! (Becoz Mommy insists that you wear a clean pair of undies every day.) But now you have had a taste of an IITian's life: too many things to do, too less time. So following Mommy's advice, you decide to plan out things. You know your routine now, so you know exactly what days you will be able to do the washing and what days you won't. You decide 2 things: 1> Since the number of undies is 7 (seven), the washing dates can atmost be separated by 7. Thus, if you wash on the 15th, you have to wash on or before the 22nd. 2> Since basically you are a lethargic bum, you decide that you will wash only if you have atleast 2 dirty undies to wash. Thus the dates must be separated by atleast 3. (So you have to wash on or after 18th, if you wash on the 15th) Since, as mentioned above, you are a lethargic bum, you want to find out the MINIMUM number of days you need to have a fresh undie every day to wear. You also know the number of days you have to spend, and the possible washing days. Input: The total number of days(N) on the first line. The total number of washing days(M) on the second line. The dates of the washing days, M of them, one on each line. NOTE: The dates are numbered from 0 to (N-1). Assume that you start out with a fresh set of undies BEFORE 0th day, (i.e the -1th day), so you need to wash on or before 6th, but but not before the 2nd day. Output: The minimum number of days you need to do the washing. Just the number, on a line by itself. Output -1 if it is impossible to schedule washing days subject to the conditions. Sample Input: 10 4 0 3 6 9 Sample Output: 1 (Since you can wash on the 6th This was an error earlier). length of input > strings? could be at max 100000.
PROBLEM 3: Credits: 30 ~~~~~~~~~~ Now you have finally drained the bitter cup: you have realised that life in IITB is not all that rosy, and only by mutual co-operation and work-sharing (read cogging) can help you thru the troubled times. Particularly when you are trying to crack math problems. You have a long list of math problems.You and other fellow sufferers decide to handle it together. Each math problem takes you or your friends 1 man-hour to crack. But there's a catch: there are some problems that can be done only if some previous problems are done. You decide (as Mommy advices) to prioratize the problems. For problems A and B, for which A appears in the list before B, there are two possibilities: 1> If A has lower or equal priority than B, then 2 students can simultaneously work on problems A and B, to decrease the number of man-hours. 2> If A has higher priority than B, then A has to be completed before B. Now since this is a common cause, you have a huge number of freshies who can work on the problems, so there's no constraint on the number of problems being tackled at the same time, as long as the above two conditions are met. As mentioned above, you are a lethargic bum, and so are your friends, so you want to decide what's the MINIMUM number of man-hours to solve all the problems. Input: The total number of problems (N) on the first line. The priorities you assigned to the problems in the list, one after the other, on separate lines, as they appear in the list. Thus there are N more lines after the first one, each having a priority value, an integer. Output: The minimum number of man-hours needed to solve all the problems in the list. Just the number. Note that a higher priority problem can be done before a lower priority job, even if it comes later in the list. THUS: IF A comes before B in the list and B has higher priority than A, then B can be done before A, or with A simultaneously. BUT if B has lower priority than A, then B HAS to be completed before A. Sample Input: 10 1 1 2 3 1 4 1 2 1 5 Sample Output: 3 (1,1,2,3,4,5) are done first, (1,1,2) are done next, (1) last. Therefore the answer is 3
PROBLEM 4: Credits: 50 ~~~~~~~~~~ Return of the SENIORS. SENIORS strike back. Now your Hostel elections are round the corner. The SENIOR who's standing for G.Sec is unfortunately your wingmate, and so he wants you to go door to door canvassing for him. But lethargic bum that you are, you crib incessantly, and whine and say that Mommy forbids you from such hard work and to concentrate on your studies. So rather than listen to your whines, the SENIOR relents and gives you a list of `N' room numbers you have to visit in order, and tells you that you can visit any `k' of them. You are ecstatic. But again that lethargic bum in you tells you that you would like to minimize your travelling. So you decide to pick a `k' subsequence of room numbers so the the total consecutive absolute differences in room numbers is minimized. Input: N,k -- on the first line, the two numbers separated by a comma. Then the room numbers, N of them, one on a line. Output: The minimum total sum of consecutive absolute differences, just the number, on a line by itself. Sample Input: 7,3 67 35 89 37 100 36 4 Sample Output: 3 (By choosing 35,37, 36. Thus 3 = |35 - 37| + |37 - 36|).
PROBLEM 5: Credits: 40 ~~~~~~~~~~ Your roommate is in the Civil engg. dept. His project consists of setting hanging a heavy plane metal sheet from cables attached to the roof. Bad. Theorem 4.7.18 in the Green book says that to minimize tensile strain( DUH...) you have to have 4 (four) points from which the metal sheet is hung. So that means that these 4 points must be coplanar. WORSE. Your roomie, having got JEE rank 4754, is worse than you. Since your JEE is nearly 1000 more than his, he thinks you are GOD, and turns to you for help. He tells you that there are `N' points in 3D space which represent the ends of the cables. He also tells you that all these points have non-negative integer co-ordinates. Since you have a huge ego (rank 3500+ is GREAT, you feel) you have to find 4 coplanar points, given that there ARE 4 coplanar points in the data.The gentle smile replaced by a frown, you set to work. Input: The number of points `N' on the first line. The co-ordinates of the points, in the format x,y,z -- separated by commas, on the next N lines. NOTE: The points are numbered from indices 0 to (N-1), as they appear in the list. Output: The indices of 1 set of 4 points, in the format: i j k l where i, j, k, l represent the indices of the points. Sample Input: 5 2,0,0 0,2,0 1,1,1 1,1,0 0,0,2 Output: 0 1 3 4 (the plane is (x + y + z) = 2).
PROBLEM 6: Credits: 50 ~~~~~~~~~~ DANIYA time!!! Work time also for you lethargic bum. The gentle smile on your face is conspicuous by its absence. Finally DANDIYA day comes. Out of the small number of girls in IIT, an even smaller number has arrived. SENIORS being SENIORS, get priority and pairs are formed. You, poor sod, don't have a partner, and have to do the dirty work of arranging publix in circles. The (lucky) boys have already formed the outer circle. The girls have formed the inner one. Your newly elected G.Sec (your wingmate, remember?) puts you to work. The girls being ladies, stay where they are. So you have to rotate the outer circle of boys so as to match them with the girls they have paired up with, or decide if it can't be done. To avoid choas, you would like to have the smallest number of movements.To add to your problems, some guys won't mind dancing with some girls apart from their partners. Input: Two strings of characters of equal length, each on a separate line. You have to find the least index of the character in the second line where the 0th character in the first string should go, so that the two strings match. The characters are numbered from 0 to (length - 1). In short: If a(0) a(1) ... a(n-1) b(0) b(1) ... b(n-1) are the two strings, then find the minimum 'k' so that a(i) = b(k + i (mod n)); for all i = 0, 1, 2,.. (n-1); NOTE: Output -1 if such a 'k' does not exist. Output: The index 'k' as specified above, just the number, on a single line. NOTE: Output -1 if such a 'k' does not exist. Sample Input: aabaa abaaa Sample Output: 4 (Since the 0th character of the first string, a, matches with the 4th character of the second string, so that if you take the 0th character to the 4th character the first string matches with the second.) Epilogue: After spending 4 years in IIT Bombay, Powai-400076, you permanently lose that gentle smile from your lips forever, but atleast learn the value and importance of hard work, so that you are no longer a lethargic bum.