Write a C code and write comments. Ann and King Kong are best friends. King Kong enjoys
Fantastic news! We've located the answer you've been seeking!
Question:
Write a C code and write comments.
Transcribed Image Text:
Ann and King Kong are best friends. King Kong enjoys playing games with Ann, no matter how silly the game is. Once, they were playing a very weird game, Ann arranged N cubes in a straight line on a table, each cube having a unique number in the range 1 to N marked all over it (essentially, the cubes when seen display some permutation of the numbers 1 to N). Now, King Kong bangs the table, the cubes fly in the air, get mixed up uniformly randomly and return to the table. Somehow, the cubes fall on the same straight line every time King Kong bangs the table, just that the positions of the cubes might change. The goal is to finally arrange the cubes such that the numbers on display are sorted in non decreasing order. Let us assume each time King Kong bangs the table as a round. This game could go on forever. Ann comes up with an idea to speed up the process. Ann can fix (or unfix, if already fixed) any cube to the table, at its position. She can do this to any number of cubes, before any round. When some cubes are fixed and if King Kong bangs the table, the fixed cubes don t fly, hence it s position remains same after that round. Also, the cubes which fly can only return to a position where there is no cube (while in flight) (cubes cannot stack on each other, or go to any other part of the table, or out of the table). Ann wants to complete the game as fast as possible, hence she wants to use this feature optimally. Given a random arrangement of the N cubes, can you find the expected number of rounds required to arrange the cubes in nondecreasing order, given the availability of the feature to fix/unfix cubes? Input: • The first line of the input contains a single integer T denoting the number of test cases. • T test cases follow. Each test case consists of two lines. The first line contains a single integer N, the number of cubes. • The second line contains N spaceseparated integers, denoting the values on the cubes C₁, in order of the initial arrangement on the table. Output: For each test case, output one line containing a single number E, denoting the expected number of rounds required to arrange the cubes in nondecreasing order. Your answer must match up to the 6th decimal place. Also, output your answer till 6 decimal places. For example: If your answer is 2.3, output 2.300000. If your answer is 2.345678921, output 2.345678. Constraints: • 1 ≤ T ≤ 100 • 1 ≤N ≤ 1000 1 ≤ C₁ ≤ N • The C; s form a permutation of the numbers 1 to N Sample Input: 2 N N N 2 2 1 4 2 143 Sample Output: 2.000000 4.000000 Explanation: One possible optimal strategy for the second test case, firstly Ann can fix the first two cubes. The expected number of rounds to sort 4 3 in nondecreasing order is 2. Then, unfix the first two cubes and fix the last two cubes. In a similar manner, it takes 2 rounds, in expectation, to sort 2 1 in nondecreasing order. Therefore, in expectation, it takes 4 rounds, in expectation, to sort the entire set of cubes in nondecreasing order.
Expert Answer:
Answer rating: 100% (QA)
The c code of the corresponding problem is attached below include include int main void setbuf stdou View the full answer
Related Book For
College Mathematics for Business Economics Life Sciences and Social Sciences
ISBN: 9780321614001
12th edition
Authors: Raymond A. Barnett, Michael R. Ziegler, Karl E. Byleen
Posted Date:
Students also viewed these algorithms questions

Plug Products owns 80 percent of the stock of Spark Filter Company, which it acquired at underlying book value on August 30, 20X6. At that date, the fair value of the noncontrolling interest was...

The following information was obtained from the records of Shae, Inc.: Merchandise inventory . . . . . . . . . . . . . . . . . . . . . . . . . $264,000 Notes payable (longterm) . . . . . . . . . . ....

Write a C code for Insertion Sort Insert element into sorted list Given a sorted list with an unsorted number in the rightmost cell, can you write some simple code to insert into the array so that it...

In Exercises use the Limit Comparison Test to determine the convergence or divergence of the series. 0 1 2 n=11n+1

Michael Trencher, a concrete layer, bought his current cement mixer two years ago for $9000, and it has one more year of life remaining. He is using straightline depreciation for the mixer. He could...

Suppose you won the lottery and had two options: (1) receiving $0.5 million or (2) taking a gamble in which at the flip of a coin you receive $1 million if a head comes up but receive zero if a tail...

What are the risks of international diversification? What are the challenges of managing multinational firms?

Rice Company performed services on account for $30,000 in 2013, its first year of operations. Rice collected $24,000 cash from accounts receivable during 2013 and the remaining $6,000 in cash during...

A truss is given in Figure 2. The crosssectional area of each member is 1800 mm and Young's modulus, E, for the material of the members is 200 GN/m. (i) (ii) (iii) 4m Determine the forces in each...

The Hesses live in a home that they had built in 1979. The home is located in River Vale, NJ and is titled in both spouses' names as (JTWROS). John inherited a summer home in Waterford, Vermont. His...

The layout of an organization is crucial in creating a productive and motivated staff of employees. Using which set of standards should companies decide on the best layout for their particular...

In a balanced threephase wyewye system, the source is an abcsequence set of voltages. , , and the load voltage on the a phase is Van = 398.1 <17.99o V rms Find the line voltage Vab.

An abcphasesequence threephase balanced wyeconnected 60Hz source supplies a balanced deltaconnected load. The phase impedance in the load consists of a resistor in series with a 50mH inductor,...

In a balanced threephase wyedelta system, the source has an abcphase sequence and Van = 120 <0o A rms. If the line current is IaA = 4.8 <20o A rms, find the load impedance per phase in the delta.

In a balanced threephase deltadelta system, the source has an abcphase sequence. The phase angle for the source voltage is

A balanced threephase wyewye system has two parallel loads. Load 1 is rated at 3000 VA, 0.7 pf lagging, and load 2 is rated at 2000 VA, 0.75 pf leading. If the line voltage is 208 V rms, find the...

Sahana's grandmother bought her a set of Russian dolls from St. Petersburg. The dolls stack inside of each other and are similar to each other. The diameters of the two smallest dolls are 2.1 cm and...

Find the velocity, acceleration, and speed of a particle with the given position function. r(t) = (t 2 , sin t  t cos t, cos t + t sin t), t > 0

In Problem, graph each inequality subject to the non negative restrictions. 24x + 30y > 7,200, x 0, y 0

The shelf life (in years) of a laser pointer battery is a continuous random variable with probability density function (A) Find the probability that a randomly selected laser pointer battery has a...

In Problems 2934, find the limiting matrix for the indicated standard form. Find the longrun probability of going from each non absorbing state to each absorbing state and the average number of...

A group of n students sit two exams. Exam one is on history and exam two is on chemistry. Let x i and y i denote the ith student's score in the history and chemistry exams, respectively. The...

Suppose that, in a Markov chain with just two states, the probabilities of going from state i to state j in one time unit are given by the entries of the matrix in which i represents the row and j...

Smith (1969, Section 21.10) quotes an example on genetic linkage in which we have observations x = (x 1 , x 2 , x 3 , x 4 ) with cell probabilities The values quoted are x 1 = 461, x 2 = 130, x 3 =...
Question Categories