[Solved] Algorithm Homework13-Olympic Average

Some sports, such as gymnastics, use a “trimmed mean,” in which the highest and lowest scores are discarded and theremaining ones averaged. This is also known as the Olympic average, due to its use in the Olympic events, to make thescore robust to a single outlier judge.You are a game developer. Your game Quarter Life 3 is now available on Sbeam. You have released multiple updates andpatches for this game to add new features, improve balance, fix bugs, etc. Since it has been very popular among gameplayers, you received lots of reviews on Sbeam each time you release a new patch. Your boss asked you to evaluate thetotal feedback for each update. And you decided to use trimmed mean to calculate the average review score after eachupdate.Each time you release an update, you will receive some new reviews. Then you will find two reviews on Sbeam, one withthe largest score and one with the smallest score. You will remove those two reviews from Sbeam as they are outliers.Finally you can calculate the trimmed mean from the remaining reviews. All the remaining reviews will be kept for nextupdate.Calculating mean is easy. Your task is to calculate the difference between the removed scores for each update.InputThe first line contains an integer n, 1 <= n <= 5000, the number of released patches.The subsequent n lines contains a sequence of non-negative numbers separated by whitespaces. The numbers in the (i+1)-st line give the reviews scores for the i-th update.The first number in each of these lines, k, 0 <= k <= 100,000 , is the number of reviews and the subsequent k numbers arepositive integers of the review scores.The review scores on Sbeam are integers ranged from 1 to 1,000,000, inclusive. The total number of all review scores is nobigger than 1,000,000.And there will be at least 2 reviews on Sbeam after receiving reviews for each update.OutputPrint n lines, the i-th line contains the difference between the largest score and the smallest score for the i-th update.Example 1Input:22 1 22 1 2Output:11Example 2Input:52 1 13 2 3 14 5 1 5 1001 2Output:0Page 2/22933Page 1/13D LabyrinthYou are in a 3D labyrinth of Conflict Empire and you want to escape it. The labyrinth could be represented as a threedimensional array where every cell is either empty or filled by rock. In every minute, you can travel in any direction parallelto the edges of the labyrinth, i.e. north, south, east, west, up and down, by one cell. You are not allowed to step onto a rockcell nor allowed to travel out of the labyrinth without reaching the exit point.Given the starting point and the exit point, your task is to determine the minimum time needed to escape this labyrinth.InputThe first line of the input contains three integers K, N and M (1 <= K,N,M <= 30), indicating the number of layers, rows andcolumns of the labyrinth, respectively. Then there follows K blocks of N lines each containing M characters. Each characterdescribes one cell of the labyrinth, where # indicates a cell of rock and . indicates an empty cell. The starting position isindicated by S and the exit by E . Note: there will be a single blank line after each level.OutputPrint one line Escaped in x minute(s). where x is the minimum time needed to escape this labyrinth, orTrapped! if it is impossible to escape.Example 1Input:3 4 5S…..###..##..###.#############.####…###########.#######EOutput:Escaped in 11 minute(s).Example 2Input:1 3 3S###E####Output:Trapped!Page 1/1Pocket MoneyIn Light Kingdom, there are $5, $10, $20, $50 and $100 notes and 5c, 10c, 20c, 50c, $1 and $2 coins. Kou’s parent is goingto give Kou some pocket money and your task is to figure out in how many ways that amount may be made up. Forexample, 20c could be made up in 4 ways: 4×5c, 10c+2×5c, 2×10c and 1×20c.InputThe input consists of a single line. This line contains one number M (0.00 < M <= 300.00, with two decimal places),representing the amount of money Kou will receive.OutputYou should print one line consisting of M (with two decimal places and right justified in a field of width 6), followed by thenumber of ways in which M may be made up (right justified in a field of width 17).Example 1Input:0.20Output:0.20 4Example 2Input:2.00Output:2.00 293Page 1/1Max Product SubarrayIn computer science, the maximum product subarray problem is the task of finding a contiguous subarray with the largestproduct, 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 producta[i] * a[i+1] * … * a[j-1] * a[j]is as large as possible.For example, for the array of values [5, -2, -10, -1], the contiguous subarray with the largest product is [5, −2, -10], withproduct 100.Write a program to calculate such product for the given input array.InputThe first line contains 1 integer n, the number of elements in the input array, 1 <= n <= 100.In the next line, there are n integers indicating the elements of the array, -10^5 <= A[i] <= 10^5 for 1 <= i <= n.OutputOutput one integer followed by a newline, indicating the product of the maximum product subarray.Example 1Input:45 -2 -10 -1Output:100Example 2Input:1-9Output:-9Page 1/1Deficit CycleYou drive a truck between N cities to earn your living. You live in city 0 and the highways among those cities have thefollowing properties:Highways are one-way only.Every highway has two endpoints and they shall not be the same city.There is at most one highway in either direction between any pair of cities.Starting from your home (city 0), you may travel to any other city using those highways.You can earn some money by traveling through a highway (someone will pay you for helping transport goods from onecity to another).The money earned could be negative (if the fuel is more expensive than what the trip pays).A deficit cycle is a driving path starting from one city, going through several highways and getting back to the same city withthe negative amount of total earnings for the trip. You may repeatedly loss money if you happen to drive along a deficit cycleagain and again. You wonder if such a deficit cycle exists given the highway map of those N cities.InputThe first line of the input contains two integers N (1 <= N <= 1000) and M (0 <= M <= 2000), indicating the number of citiesand the number of highways. Each of the following M lines contains three integers u, v and w, indicating there is a highwayby which you can travel from city u to city v and you can earn w dollars. (0 <= u,v < N, u != v, -1000 <= w <= 1000)OutputPrint one line containing possible or not possible to indicate if there exists a deficit cycle.Example 1Input:3 30 1 10001 2 152 1 -42Output:possibleExample 2Input:4 40 1 101 2 202 3 303 0 -60Output:not possibl