[Solved] Algorithm Homework10-Bus Tour

Hangzhou is a beautiful city for tourist. The buses with numbers that begin with ‘Y’ go to scenic spots, train stations, touristcenters and bus stations (all the things that the tourists need). Y1 is a bus route starting from Lingyin Temple and aroundthe West Lake in the counter clockwise direction. There is N stops for Y1.The scenery between two adjacent stops can be measured by a integer scale of “niceness”. Positive niceness valueindicates nice view and negative value indicates the scenery between stops is dull.Macro Pool is a reporter for Tourists’ World_ who arrived inHangzhou last week. His task is to find two different stops along theY1 bur route such that the niceness score is the largest.Can you help him to find those stops?InputThe first line of input contains an integer, N, the number of stops along the Y1 bus route, 2 <= N<= 20,000Each of the next N-1 lines contains a single integer. The i-th integer indicating niceness between stop i and stop i+1.The absolute value of niceness will not exceed 10^9.Output If the maximum possible sum between two stops is not positive, your program should print a line:“Yet another overrated tourist destination”Otherwise, your program should identify the beginning bus stop i and the ending bus stop j that identify the segment of theroute which yields the maximal sum of niceness.If more than one segment is equally maximally nice, choose the one with the longest bus ride (largest number of stops, j – i).To break ties further in longest maximal segments, choose the segment that begins with the earliest stop (lowest i).Print a line in the form:“The nicest part of Y1 is between stops i and j”Example 1Input3-25OutputThe nicest part of Y1 is between stop 2 and 3Example 2Input4-1-1-1OutputYet another overrated tourist destinationPage 1/1Heating RodThere is a rod with length L mounted between two fixed walls.When the rod is heated, it will expand lengthwise according to theformula L*(1+T*C) where T is the temperature difference and C isthe expansion coefficient of the metal from which the rod is made.Your task is to calculate the displacement of the center of the rodfrom its original position.InputThe input consists of only one line, containing three non-negativenumbers: L, T and C, indicating the length of that rod, thetemperature heated by and the expanding coefficient. It isguaranteed that the new length after expansion will be no morethan 1.5*L.OutputPrint one line, containing a single number D, the displacement of the center of the rod. D should be rounded to 3 decimalplaces.Example 1Input:1000 100 0.0001Output:61.329Example 2Input:15000 10 0.00006Output:225.020Example 3Input:10 0 0.001Output:0.000Page 1/1Math HomeworkKou just finished her first math class. Her teacher gave her a problem as homework and Kou again, asked you for help.Recall that prime gap is the difference between two consecutive primes. In this problem you are to find the mode of primegaps formed by primes in the given lower and upper bound.InputThe input consists of a single line containing two integers L and U (0 <= L <= U <= 1,000,000), representing the lower andupper bounds.OutputYou should print a single integer representing the mode of prime gaps or -1 if there are multiple single modes or there is noprime gap.Example 1Input:2 11Output:2Example 2Input:2 5Output:-1Example 3Input:30 50Output:4Page 1/1ParcelsAnazon has 6 types of products. Each is packed in a box of height H with base equal to one ofthe following sizes: 1×1, 2×2, 3×3, 4×4, 5×5, 6×6. (All sizes are specified in feet.)The individual boxed products are always delivered to customers in the shipping packages withheight H and base of 6×6 (again in feet).To reduce the number of shipping packages (and therefore the cost), Anazon wants you to writea program to calculate the minimal number of packages necessary to deliver the given order ofproducts.Input A single line containing 6 non-negative integer no greater than 100,000, specifies an order.The i-th integer indicates the number of boxes of individual size i×i.Output Output the minimum number of packages needed to ship the order.E×ample 1Input0 0 0 0 1 1Output2E×ample 2Input0 0 4 0 0 1Output2E×ample 2Input6 5 1 0 0 0Output1Page 1/1Max Sum SubarrayIn computer science, the maximum sum subarray problem is the task of finding a contiguous subarray with the largest sum,within a given one-dimensional array A[1…n] of numbers.Formally, the task is to find indices i and j with 1 <= i <= j <= n, such that the suma[i] + a[i+1] + … + a[j-1] + a[j]is as large as possible.For example, for the array of values [−2, 1, −3, 4, −1, 2, 1, −5, 4], the contiguous subarray with the largest sum is [4, −1, 2,1], with sum 6.Write a program to calculate such sum with given input array.InputThe first line contains 1 integer n, the number of elements in the input array. 1 <= n <= 100000.In the next line, there are n integer indicating the elements of the array. We have -10^9 <= A[i] <= 10^9 for 1 <= i <= n.OutputOutput one line containing the value of the sum for the maximum subarray.Example 1Input:9-2 1 -3 4 -1 2 1 -5 4Output:6Example 2Input:4-3 -2 -4 -1Output:–