OFJ6CXTPE4 Welcome to BitWISE 2K2. We have decided to base the contest problems on the Mahabharata. In spite of being one of our oldest epics, it contains many lessons which are relevant even today. The Bhagavad Gita, with its philosophy of Karma gives one a radically different but pragmatic and optimistic outlook on life. We hope you enjoy programming with the Mahabharata. "Main Samay Hoon ..." (It's time speaking!) Disclaimer :- We hope that we do not inadvertently hurt anybody's sentiments. The incidents and characters depicted in the problems do resemble those in the Mahabharata, but the situations created may not have any authentic support from the epic. 1. Shloka Sutra (Formula for Verses) Let me take you back in time ,thousands of years back, to ancient India, in the era of Kings and Dynasties, where Maharshi Veda Vyas is at the verge of putting pen to paper to begin what is to date, the largest epic in human history 'The Mahabharata'. In his epic, Vyas is going to describe the history of Hastinapur, the story of Kauravas and Pandavas and the divine Lilas of Sri Krishna. The immensity and grandeur of his venture makes Vyas ponder upon the number of shlokas (ie verses) that each chapter must contain. The numbers must be in perfect synchrony for the beauty and majesty of the whole epic. Lord Ganesha, the God of wisdom, suggests Vyas that he should select a set of p prime numbers and enumerate all the numbers greater than 1, all of whose prime factors belong to the selected set. Then he must arrange those numbers in increasing order and form a rhythmic sequence. The number of shlokas in the Nth Chapter then, will be equal to the the Nth number of the rhythmic sequence. Vyas decides to work along the steps of Ganesha. Given the set of primes, and N, can you help Vyas calculate the number of shlokas in the Nth chapter? Input Format: First line will contain a positive integer p (The number of primes in the set) The second line will contain p distinct prime numbers separated by space. The third line will contain a positive integer N (The chapter number). Output Format: One positive Integer (The number of shlokas in the Nth chapter). Example Input: 3 3 5 7 4 Output: 9 2. Radha's Pots Vrindavan, located on the bank of river Yamuna, is blooming with spring. Radha and other gopis( Radha's friends) are out to get water from Yamuna. While returning she was enchanted by the melodious music of Krishna's flute. Being completely absorbed by the ethereal music she was unable to keep the water pots stable. Krishna came to her rescue. But the problem was more serious. Radha had several pots arranged one on top of another in order of their sizes on her head, the largest being at the bottom. To relieve Radha, Krishna has to move the stack from her head to Maitrali's head(one of the GOPIS). Krishna has decided to move only one pot at a time and Radha has warned him not to keep any pot on the ground but he can keep the pot on other gopi's head. He is not allowed to keep a bigger pot on a smaller one. Can you help Krishna relieve Radha ? For the sake of simplicity you can assume that initially none of the gopis had pots on their head. Input Format The first line of input will be the number of pots on Radha's head. The second line of input is the number of gopis excluding Radha and Maitrali. Output Format The First line of output should contain total number of moves. It should be followed by the set of moves. Each move should be a tuple specifying source gopi and destination gopi. You can number the gopis from 1 to n+1 with Radha being numbered 0 and Maitrali being n+1. Example Input 2 1 Comment : please note that the second line contains the Number Of Gopis apart from Radha & Maitrali . output 3 0 1 0 2 1 2 INPUT BOUNDS: Maximum number of pots=1500,Max number of gopis is 30. 3.Trikonastra (The Three-Headed Arrow) The Pandavas and their bride Draupadi return to a warm welcome in Hastinapur. King Dhritarashtra has gifted the jungles of Khandavprastha to them. The Pandavas will clear the jungle and set up the beautiful kingdom of Indraprastha. Arjuna plans to use the Trikonastra given him by Agni, the God of Fire to burn the jungle. The Trikonastra fires three arrows simultaneously .The land lying within the triangle defined by the points where the arrows land goes up instantly into flames. Arjuna fires the Trikonastra several times. You are to find out the total area that has gone up in flames. Input Format : The first line of input will have a positive integer n (the number of times the Trikonastra is fired). The n subsequent lines will have 6 integers: x1 y1 x2 y2 x3 y3 , specifying the coordinates where each of the three arrow land for each shot of the weapon. Output Format : The output should be the total area destroyed. Assumptions and guidelines : 1. Please note the Triangles may overlap. 2. Each Point is specified by two integer coordinate (x,y).Origin is at the bottom left corner. X axis increases towards right and y towards top. 3. No triangle will have two vertices having the same Y coordinate. 4. More than two edges never intersect in a point. Test Cases The test cases will be graded in difficulty. Partial credit will be given for evaluating the area of simpler shapes. Example : Input 4 75 55 65 20 10 30 74 53 110 49 95 82 70 105 10 90 70 79 35 65 70 145 120 75 Origin is at the bottom left corner Output 1576.28 Input Bounds: The Trikonastra is fired at most 20 times. 4. Sama-srinkhala( Balanced Sequences) The jungles are destroyed now. The Pandavas decide to make Indraprastha the world's most beautiful city. They have also planned to gift a beautiful palace to their beloved Draupadi. Mai Danav, the best known architect of that time was assigned that task. According to Vastu Shastra, there are specific rules about the number of rooms that should be connected to each room by dedicated corridors. These rules are coded in form of sequence of integers, where each number in the sequence specifies the number of rooms connected to that particular room. Such sequences are called "sama-srinkhala" or balanced sequences each of which is related to a specific mood. Draupadi consults an astrologer who comes up with a lucky sequence for her, which may or may not be a sama-srinkhala. She provides that sequence to Mai Danav and asks him to design the Royal Palace accordingly. Mai Danav being a brilliant architect devises a new technology to construct staircases in the corridors. Can you help Mai Danav to design the plan of the palace? Input Format : The first line of the input will have 'n', the number of rooms that Draupadi wants. Each of the subsequent 'n' lines will contain one integer specifying how many rooms that room should be connected to. Output Format : If no plan exists for that given sequence, print -1 Otherwise, the first line of the output should be 1 In each of the n subsequent lines, for each room, print a space separated list of room numbers to which that room is connected . The list should be terminated by -1. Guidelines : 1.The rooms should be numbered from 0 to 'n'-1. 2.Note that there might be more than one correct solution. Print only one solution. Example: Input 5 4 2 2 1 1 Comments: There are 5 rooms. The first room is connected to 4 others, the second one is connected to 2 others and so on. Output 1 1 2 3 4 -1 0 2 -1 0 1 -1 0 -1 0 -1 Comments: The first 1 denotes that a correct plan exists. If we number the room from 0 to 4, then room 0 is connected to rooms 1,2,3 and 4. room 1 is connected to rooms 0 and 2 and so on. Input Bounds : You may assume that the palace has at most 100 rooms. 5. Griha Pravesh Mai Danav has just completed the Indraprastha palace according to Draupadi's specifications and a Griha Pravesh (House Warming party) is planned. The Pandavas are sending out invitations for the party. Everybody has a lot of friends . There are mutual friends. The invitees will be drawn from the friend circle. Each of the Pandavas is going to invite a specific number of his friends to the party. However, the total number of invitations are limited and Kunti Ma( their mother) would like a balanced invitation list comprising a healthy mix of all professions (Kshatriyas, Brahmins, Traders ,etc). Moreover the family has decided that they will send out only one invitation to anybody, so even if you are friends with both Bhim and Arjuna, you will receive only one invitation, signed by either Bhim or Arjuna. Can you help them with the invitation list ? Input Format: The first line contains 4 integers: 1.The total number of invitations, (N) 2.The number of hosts, (H) 3.The total number of professions (P) 4.The total number of friends (possible invitees) (F) The next inputs are H integers specifying the quota for each host. The inputs after that are P integers specifying the quota for each profession. Then the information for all possible invitees is printed. The information for each possible invitee is his profession number and a list of host numbers, terminated by -1. Output format The list of invitees with the following information is printed for each invitee. 1.The sequence number of the invitee. 2.The number of the host by whom he was invited. If it is not possible to invite the specified number of invitees, while satisfying the specified quotas, print -1. For example 4 2 2 5 /*Comments: There are 4 invitations, 2 Hosts, 2 Professions and 5 possible invitees*/ 3 1 /*Comments: The quota for Host 0 is 3 and that for Host 1 is 1*/ 2 2 /*Comments: The quota for Profession 0 is 2 and that for Profession 1 is 2*/ 0 1 -1 0 0 1 -1 0 0 -1 1 0 -1 1 1 -1 /*Comments : Guest 0 belongs to Profession 0 and is friends with Host 1 similarly Guest 1 belongs to Profession 0 and is friends with Host 0 and Host 1 */ Output 1 0 2 0 3 0 4 1 /*comments: Guest 1 is invited by host 0 and Guest 2 is invited by Host 0 and so on ..*/ 6. Dhyuth Krida - The Gamble The ever cunning Shakuni Mama(uncle) has hit upon a new devious intrigue and the Pandavas are really in for it this time, that is unless you can help them. The Pandavas are invited to a new kind of Chausar , and the stakes are high indeed. In this new Chausar (version 6.4, we have it from Shakuni himself ) , there is a rectangular board with a variable number (say m) of squares on it, numbered from 1 to m. The players take turns trying to place n tokens on the board. The tokens can be stacked on top of one another so that there might be any number of tokens on a square. A player earns points for placing tokens on a square. The player earning the maximum number of total points wins. The number of points earned for a square depends on the number of tokens placed on that square but may not be directly proportional to it. Dharmaraj Yudhishthir has been handed a huge table which contains the points earned for placing a certain number of tokens on a specific square. The table can be thought of as a 2 dimensional integer matrix M. The entry M[i][j] gives the number of points earned if i tokens are placed in the j th square. Placing more tokens on any square can never decrease the points earned. Dharmaraj is flummoxed by Chausar v6.4 , can you help him win by telling us how many tokens you will place on each square. Input format: The first line contains two integers m (number of tokens) and n (number of squares), separated by a single space. The next m lines contain n positive integers each , where the jth integer on the ith line gives the number of points earned if i tokens are placed on the j th square. Output format: In the first line print the total number of points earned. Each subsequent line should contain a tuple specifying the square number and the number of tokens to be placed on that square .Even if the number of tokens is 0 in some square the output should have an entry for it. Example: Input : 3 3 /* Comments: There are 3 squares and 3 tokens */ 9 3 6 10 9 10 17 14 15 /* Comments: Placing 1 token in square 1 gives 34 points, placing 2 tokens in square 1 fetches 56 points and so on. */ Output : 19 /* Comments: The Maximum possible points that can be earned is 19 */ 1 1 2 0 3 2 /* Comments: For maximum points 1 token should be placed in square 1, 0 token in square 2 and 2 tokens in square 3. */ Input Bounds: The Maximum number of squares is 30. The maximum number of tokens is 50. Problem #7 Vajra kavach However, the sheet of Vajra though huge is limited. Not all the warriors in the 18 Akshouhini (1 Akshouhini = 21,870 chariots, 21,870 elephants, 65,610 horses and 109,350 soldiers) strong Kaurava army can be given a shield to protect themselves. Naturally, Duryodhan wants to provide shield to the warriors who are more promising in the battle-field. He decides on a scheme. He first groups the soldiers into several classes and assigns each class some points (which is a positive integer) directly proportionate to the utility of that class in the war. Then he determines the size of the kavach required for the soldiers of each class depending on the vulnerability of that class in the field . The shape of all the shields are rectangular and are specified by its length and breadth. Duryodhan gives these data to Vishwakarma, the divine engineer, and asks him to make the best possible utilization of the Vajra, so that the total utility of the sheet is maximum. But Vishwakarma faces a strange problem while dividing the sheet. He could find no scissors in the world that could cut that hard material. Finally he has to resort to the famous axe of Parashuram, which can be used to divide a sheet into two parts (need not be equal in size). Can you help Vishwakarma by guiding him how to divide the sheet? For the sake of the problem, assume an x, y coordinate system is superimposed on the original sheet. The origin lies on the top left corner of the sheet .The x axis runs from left to right and the y axis runs from top to bottom. Also assume that all cuts are straight lines parallel to one of the axii. Input Format: The first line contains three integers , separated by a single space , the length of the original sheet, the breadth of the original sheet and the number of classes (N) of warriors . There are N subsequent lines , each having three space separated integers. The second line contains the breadth of the class 1 kavach , its length and the associated points. The third line contains the breadth of the class 2 kavach , its length and the associated points. and so on............ Output Format : The first line contains the total number of points. Description of cuts Then there is a line each for describing the cuts that the axe makes. The cuts should be listed in the order they are made. Each line contains four integers , they are described Integer No. 1. This is 1 if a horizontal cut was made. It is 0 if a vertical cut was made. 2. The constant coordinate along the line of cut. The x coordinate of the line if a vertical cut was made. The y coordinate if the cut was horizontal. 3.Horizontal cut : x coordinate of left end point of cut Vertical cut : y coordinate of upper end point of cut. 4. Horizontal cut : x coordinate of right end point of cut Vertical cut : y coordinate of bottom end point of cut. Print -1 in a new line after having described the cuts. Description of the placement of each kavach After the cuts have been made, the sheet is divided into rectangles. Each rectangular piece can now be given to a warrior. In a line each describe each rectangle that was given to a warrior. Each line of description contains three integers which are 1. The x coordinate of the upper left corner of the rectangle. 2. The y coordinate of the upper left corner of the rectangle. 3. The class of the warrior to whom the rectangle was given. Example Input 5 5 2 2 2 1 1 3 1 Output 115 1 2 0 5 0 2 0 2 1 1 2 5 1 3 0 5 0 2 2 3 0 2 3 5 1 4 2 5 -1 0 0 0 1 2 1 1 2 2 0 0 3 1 2 3 1 2 4 -1 2 5 INPUT BOUNDS : the original sheet is at most 100 by 100 in size. There are at most 10 classes of warriors. 8. Offensive Strategy The war finally begins. The battlefields of Kurukshetra are being reddened with the blood of the soldiers of the two warring armies. The Kauravas have devised an elaborate strategy to create strong defensive battle formations of their infantry. Soldiers are arranged in formations in such a way that a particular soldier is shielded by some others. Each soldier can hold off upto k enemy soldiers indefinitely. However, if k or more soldiers attack simultaneously, he can defend himself for a limited time T, whose value might differ from soldier to soldier. In case a soldier is slain, all the soldiers defended by him will be attacked by one more soldier each, but the enemy soldier takes some time t to reach one of the soldiers being defended. The value of t could be different for different pairs of defenders and defendants. At the beginning of the day, there is a certain number of soldiers who are defended by no one and who can be attacked right away. Any of the other soldiers can be attacked only when at least one of the defenders has been killed. The Pandava army wants to decide upon an appropriate attacking strategy. The given information includes the value of T for each soldier, the defender-defendant pattern of the whole formation at the beginning of the day and t values for each of those pairs. The Pandavas want to kill a particular soldier (such as Karna, whose position in the formation is also known) in the minimum possible time. Can you help Pandavas come up with a plan of the order in which to attack and kill soldiers? Input Format : First line contains one positive integer n specifying number of soldiers. (Numbered 0 to n-1). Second line contains an integer between 0 and (n-1) which indicates the number of the soldier who is the final target. Third line contains an integer, k, which is the threshold of the number of attackers any soldier can hold off indefinitely, as mentioned above. n subsequent lines with each line containing following information about each of the soldiers - Value of T, a positive integer. For each defender of that soldier, the number of the defender and the value of t (an integer) for that pair, terminated by -1. All integers are separated by a whitespace. Output Format : If no attacking strategy exists, print -1 Otherwise, print in each line - Soldier's number, Time when he dies (separated by a space) for all the soldiers to be killed in order to kill the target. These entries should be sorted in the order in which the soldiers are killed so that the last entry corresponds to the death of the target warrior. Guidelines : 1.Note that there can be cycles in the sets of defending soldiers i.e. A could be defending B, who could defend C, who in turn may defend A. 2.Initially, there may no soldiers who are not defended by any others. In such a case, the formation would be impregnable. 3.It can be assumed that the number of attacking soldiers at the disposal of the Pandavas is effectively unlimited. Input Bound : Maximum Number of Warriors is 200. 9.Chakravyuha It was the 16th day of the Great War of Kurukshetra. Guru Dronacharya has fashioned an impenetrable Chakravyuha. Abhimanyu, the valiant son of his brave father Arjuna had picked up the art of penetrating the Chakravyuha, while still in his mother's womb. He ventured bravely inside the Vyuha. But unfortunately, his knowledge is limited to penetrating to the heart of the Vyuha. Having fought his way in, he got trapped at the center and became a martyr. Had he known how to find his way out, history might have been different indeed. The Chakravyuha is a formation of warriors resembling a beehive pattern as shown below. Each warrior occupies a hexagon by himself. Suppose the hexagons are numbered as shown in the figure, the center of the vyuha being numbered 1 where Abhimanyu was trapped. To get out he would have had to slay some specific warriors , but to get to them he must first slay all the warriors in his path to them. However , the Vyuha is an exacting formation , and the VyuhaBhed vidhi (the art of conquering the vyuha) prescribes that Abhimanyu would have needed to conserve his energies. He must get to his targets by slaying the minimum possible number of intermediate warriors. But he would have needed to take care when proceeding from a slain warrior to his next adversary. On the way, he must cross the hexagons by crossing the edges transversely, and never stepping on to vertices of the hexagons. Had he in his immeasurable distress, asked you how many warriors he would have to slay including his final adversary, could you have told him? The problem is divided into two parts . A) Abhimanyu is at the hexagon numbered 1 and wants to reach some other hexagon. B) Abhimanyu is standing somewhere in the arrangement and wants to reach some where else. Please note that Part A is easier and you might solve only part A for partial credit. Part B is a generalization of part A. The Input Format handles both the parts together. InputFormat: Two positive integers. The first is Abhimanyu's original position and the second his destination. Output Format: The minimum number of hexagons he must cross to reach his destination, as specified above. If you have only attempted part A, print -1 in the output for inputs pertaining to part B. Example 1 // For Part A Input : 1 20 Output: 3 Example 2 // For Part B Input 6 10 Output 3 10. Ashwamedha Yajna Finally the great war of Kurukshetra comes to an end and Pandavas emerge as the victors. Dharmaraj Yudhishthir is coronated the king of Hastinapur. Yudhisthir decides to perform the Ashwamedha Yajna(a ritual) which will make him King of all Bharat. In this Yajna, a horse is allowed to roam over the entire territory and when the horse enters a new kingdom, the King of that Kingdom is left with only two options. Either welcome the horse to his kingdom, which implies that he has surrendered to Yudhishthir, or capture it in which case it is an open challenge to Yudhisthir who must fight and defeat his adversary and free his horse again for the successful completion of the Yajna. Yudhishthir chooses a royal horse for the Yajna and chooses his best stablemen to follow and take care of it. The stablemen should take enough food for the horse, so that the horse can sustain the long journeys between different cities - the only places where the food is available. After reaching the cities they can refill the container with food upto its full capacity and continue the journey. The stablemen should determine the minimum capacity of the container so that the horse never starves. They know the map of all the cities where food is available and the roads connecting them and the amount of food the horse requires while traveling through each of these roads. Since the horse can travel from any point to any point through any path, the answer would be a container which is large enough to support the horse for the longest road. Imagine however , that Yudhishthir had an intelligent horse .The horse always took the best path whenever it wished to travel from one city to another such that the required capacity of the food-container was minimized. Note that the horse only chooses the optimal (minimum container capacity) path between two cities, but the choice of the cities is random. Given the network of cities, the roads connecting them , and the food required for the journey along each road, can you help the stablemen calculate the minimum capacity of the container? Input: In the first line a positive integer n specifying the number of cities where food is available. ( Assume that the cities are numbered from 0 to n-1.) In each subsequent line there are 3 integers a b f , where a and b are the number of the two cities and f is the amount of food the horse requires while traveling from a to b. (Note that this list may not contain all possible pairs of cities. Only those pairs are shown which are connected by roads. The last line contains -1 -1 -1 Output: One integer specifying the minimum capacity of the container required. Example: Input: 4 0 1 5 0 3 2 1 3 4 1 2 9 2 3 6 -1 -1 -1 Output: 6 Input Bounds: Maximum number of cities is 600.