eolymp
bolt
Try our new interface for solving problems
Məsələlər

Crusher`s Code

Crusher`s Code

Zaman məhdudiyyəti 20 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Wesley Crusher is the teaching assistant for Introduction to Algorithms. During his rst class, the cadets were asked to come up with their own sorting algorithms. Monty came up with the following code:

while (!sorted(a)) {

int i = random(n);

int j = random(n);

if (a[min(i,j)] > a[max(i,j)])

swap(a[i], a[j]);

}

Carlos, inspired, came up with the following code:

while (!sorted(a)) {

int i = random(n-1);

int j = i + 1;

if (a[i] > a[j])

swap(a[i], a[j]) ;

}

Wesley needs to determine which algorithm is better.

For a given input array of up to 8 values, calculate and print the expected number of iterations for each algorithm. That is, on average, how many iterations should each algorithm take for the given input?

Giriş verilənləri

The first line contains T, the number of test cases: 2T100. Each test case is given on a single line. The first value is N, the number of array elements; 2N8. This is followed on the same line by N integer array elements. The array elements will have values between 0 and 100 inclusive. The array elements may not be distinct.

Çıxış verilənləri

For each test case, print out the expected number of iterations for Monty's algorithm and for Carlos's algorithm, as shown in the sample output section. There should be exactly one space between words and no spaces at the start of each line or at the end of each line. There should be exactly six digits after the decimal point. Rounding should be to nearest representable value.

Nümunə

Giriş verilənləri #1
12
2 1 2
2 2 1
3 1 2 3
3 3 2 1
4 1 2 3 4
4 4 3 2 1
4 2 1 4 3
5 1 1 1 1 1
5 5 4 3 2 1
8 8 7 6 5 4 3 2 1
8 3 1 4 1 5 9 2 6
8 2 7 1 8 2 8 1 8
Çıxış verilənləri #1
Monty 0.000000 Carlos 0.000000
Monty 2.000000 Carlos 1.000000
Monty 0.000000 Carlos 0.000000
Monty 6.000000 Carlos 5.000000
Monty 0.000000 Carlos 0.000000
Monty 14.666667 Carlos 12.500000
Monty 12.000000 Carlos 4.500000
Monty 0.000000 Carlos 0.000000
Monty 26.382275 Carlos 23.641975
Monty 89.576273 Carlos 79.496510
Monty 79.161905 Carlos 33.422840
Monty 63.815873 Carlos 38.910494
Mənbə 2013 North America - Pacific Northwest Region Programming Contest, Задача C