DIFFICULTY:
EASY
PREREQUISITES: Data Structures, Looping, Discrete Mathematics
PROBLEM:
In a show, seats are divided into columns with fixed barriers. People are sitting in each column. The columns are tagged 1 to n , where n is the total number of seats in that column. Every person is holding a ticket with a tag number which is the same as the seat number. The seat number will be started from 1. Anyone can swap their position by giving Rs. 1000 to the next person sitting in that column but no one can spend more than Rs. 2000. Everyone wants to spend money to change the seat in one direction (towards the front side). After swapping their seats, they will hold the same numbered ticket. The Organizer decided to calculate the amount of money that has been exchanged among the people on average so that he can raise the price of each ticket. The average will be calculated for only those people who will spend extra money.
Added this Portion in Announcement after starting exam–
For each test case, the output will be a single line containing the price expended on an average by each person changed their seat. If you get fractional number rounded down to 2 decimal places as it is price but if it is integer then don’t print decimal point. Check sample in question. Everyone wants to spend money to change the seat in one direction (towards front side). After swapping their seats, they will hold the same numbered ticket. Seat number will be started from 1 and will increase consecutively.
Input:
- First line will contain T number of testcases. Then the testcases follow.
- For each test case, the first line will contain n , number of columns and in the second line the input will be space separated n integers.
Output:
For each test case, the output will be a single line containing the price expended on an average by each person who have changed their seats .If you get fractional number rounded down to 2 decimal places as it is price but if it is integer then don’t print decimal point. Check sample output. If program found more than Rs. 2000 has been spent, it will give a string output “Too Much”.
Constraints:
- 1≤ n ≤106
Sample Input:
2
7
1 4 2 3 5 6 7
5
5 1 2 3 4
Sample Output:
2000
Too Much
EXPLANATION:
Find minimum adjacent swap to sort the array. Find how many elements traverse in one direction to calculate average.
Suppose this is input 1 4 3 2 5 6 9 8 7 10
This is actual Tag 1 2 3 4 5 6 7 8 9 10
Tag is used here as it always holds consecutive number while it denotes seats or memory location or anything.
It will start from 1 and increases consecutively although only consecutive positions will serve the purpose.
The 4th person should spend 2k to reach second position as it is stated in question they can change to next seat that means 3rd person new 4th and 2nd person become new 3rd. Now 3rd person will pay 1k to reach his position. Same thing will happen for 7, 8, and 9.
Total 4 persons spend money and that is 6k.
So average will be 1.5k.
Compare the index of each element with its value
If it is misplaced then how much
If it is more than two than print too much
Else if it is 2 then he spent 2k
And requires 2 swap with next seat to reach actual position
(In your code you have to swap)
If it differs by one position then
He spent 1k and requires one swap to next position reach actual position
At the end calculate total money expended and how many people expended, derive the average.
Test Cases:
Input:
1
4
1 4 2 3
Output: 2000
Input:
1
7
3 2 1 7 4 5 6
Output: Too Much
Input:
1
6
1 3 2 6 4 5
Output : 1500
Input :
1
9
3 1 2 4 5 8 6 7 9
Output : 2000
Input:
1
4
4 1 2 3
Output: Too Much