[Solved] Algorithm Homework6-Calvin’s Stars

Calvin likes to lie in a field and look at the night sky. Since he does not know any real star constellations, he makes them up:if two stars are close to each other, they must belong to the same constellation. He wants to name them all, but fears to runout of names. Can you help him and count how many constellations there are in the sky?Two stars belong to the same constellation if distance between their projections on a two-dimensional sky plan isn’t morethan D units.InputThe first line contains the number of stars N ( 0 <= N <= 1,000 ) and the distance D (a real number0.0 <= D <= 1,000.00 ). Next N lines have a pair of real coordinates X Y (where –1,000.00 <= X, Y <= 1,000.00 ) for each star in the sky. All real numbers in the input will have at most 2 (two) digitsafter a decimal point.OutputOutput the number N that is the number of constellations in Calnvin’s sky.Example 1Input:5 1.51.0 0.12.0 0.05.0 0.26.0 0.43.0 -0.1Output:2Example 2Input:3 4.0121.12 254.06645.04 301.85912.49 568.96Output:3Page 1/2VirusDue to the outbreak of unknown virus in 2029 in the mountains of Timbet, all the monks at Senpou Temple are required todo physical checkups at Iosefka’s Clinic. All checkups are scheduled on the same day. Each monk gets instructions in whichhe is given1. his unique patient number from the set { 1 … n }2. the time of the day when he is supposed to show up at Iosefka’s Clinic3. a list of doctors’ offices that he is to visit in the specified orderDoctors’ offices in Iosefka’s Clinic are numbered with numbers from the set { 1 … m }.Since a doctor can only check one monk at a time, if several people show up a doctor’s office at time t, they form a queue inincreasing order of their numbers and join the end of the queue already formed by monks who arrived earlier.If at time t in front of office x there is a queue of people who arrived earlier or at time t, then the first monk from the queueenters offic x. This monk exits the office after one time unit and at time t+1 appears at the next office from his list of officesto visit. At that time the next person from the queue enters office x.If a monk was supposed to show up at the clinic at time t, then at time t he shows up at the first doctors’ office on his list. If avisit at office x at time t was for the given monk the last visit on his list, then at time t+1 this monk leaves the clinic.Your task is to find the time when the last monk leaves the Iosefka’s Clinic.InputThe first line of input contains 2 natural numbers n and m, 1 <= n, m <= 10000, giving the number of the monks and thenumber of doctors’ offices. Each of the following n lines contains a sequence of natural numbers. Among these lines, line i(1 <= i <= n) has the following formatt k g1 g2 … gkmeaning that the ith monk arrives at time t and has to visit k offices in the order given by g1 g2 … gk where each gj is anumber of doctor’s office, 1 <= gj <= m. We have that 0 <= t <= 1,000,000 and there is no more than 1,000,000 visitsscheduled for a day at the clinic.OutputPrint one line giving the time when the last monk leaves the hospitalExample 1Input:5 31 3 3 2 10 7 2 3 1 1 1 1 22 1 11 2 3 34 3 1 1 1Output:12Example 2Input:5 103 1 62 3 3 2 82 1 4Page 2/22 4 7 9 9 60 2 8 7Output:6Page 1/1Math ClassKou is having her first math class. Her teacher gave her N positive integers and asked her to build a largest possiblenumber. The only allowed operation is to concatenate the numbers one after another. Kou can reorganized the numbers asshe sees fit, but she cannot remove or rearrange the digits within the numbers.However, Kou got stuck on this problem. She turns to you for help.InputThe first line of the input contains a single integer N (1 <= N <= 50), indicating the number of integers. The next linecontains N positive integers between 1 and 10100.OutputYou should print a single integer, the largest number that can be created by concatenating the given numbers in any order.Example 1Input:4123 124 56 90Output:9056124123Example 2Input:5123 124 56 90 9Output:99056124123Example 3Input:59 9 9 9 9Output:99999Page 1/2Sia’s BoxSia has a mysterious box and she wants to play a game with you. The box supports two types of operations:1 x : Put the number x into the box.2 : Take out a number from the box.Sia will give you a sequence of operations and the results of 2 operations. Your task is to determine what is really hiddenin the box: a stack, a queue, a max priority queue or something else.InputThe first line of the input contains a single integer N (1 <= N <= 1000), indicating the number of operations. Each of the nextN lines contains a single operation described above. For operation 2 , there is an additional number x indicating the resultof that operation. The value of x in both operations satisfies 1 <= x <= 100.OutputYou should print:stack if it is certain that the box is a stack.queue if it is certain that the box is a queue.priority queue if it is certain that the box is a max priority queue.impossible if it is certain that the box cannot be any of those three data structures.not sure if the box could possibly be more than one of those three data structures.Example 1Input:61 11 21 32 12 22 3Output:queueExample 2Input:61 11 21 32 32 22 1Output:not sureExample 3Page 2/2Input:21 12 2Output:impossibleExample 4Input:41 21 12 12 2Output:stackExample 5Input:71 21 51 11 32 51 42 4Output:priority queuePage 1/1Daily PrizeTrader Jane’s has a new promotion to attract even more customers to already crowded supermarket.To participate in a daily drawing of the prize a customer needs to fill out a form with their name, phone number and theamount that they paid for their groceries.At the end of the day, Trader Jane’s manager picks two forms from among the completed ones:first is the one that has the highest amount paidsecond is the one that has the lowest amount paid The person who paid the highest amount gets the prize equal to thedifference between their bill and the lowest bill.Given how busy Trader Jane’s supermarket is, you can be certain that at the end of each day there are at least two bills toselect (usually there are many many more).The selected forms are discarded, but the other ones remain in the pool for the next day, so each customer has a chance tobe selected as the prize winner on the day of their purchase, or any day after.Your task is to compute how much money Trader Jane’s pays out in prizes.InputThe input contains an integer n , 1 <= n <= 5,000 on the first line – this is the number of days in the promotion. Eachof the next n lines contains a sequence of non-negative integers separated by whitespace. The first number on each lineindicates the number of forms submitted on that day, 0 <= k <= 100,000 . The next k numbers specify the billamounts on the forms entered for the daily drawing on that day. Each amount is guaranteed to be no larger than 1,000,000.OutputPrint one number that is the sum of all the prizes that Trader Jane’s pays out during the promotion followed by a newline.Example 1Input:53 1 2 32 1 14 10 5 5 101 2Output:19Example 2Input:22 1 22 1 2Output: