Problem E: Garbage Sort

Time limit: 3 sec

Now a days sorting is a common sub problem in programming contest. So many programmers want to simplify the complexity of sorting algorithm. Garbage, the best programmer of HSTU develops an efficient sorting algorithm. But there is a problem, only 80% times it gives the right ans. So Garbage start debugging and realize that 15% times just one swap needs to make the array sorted. So an array that is sorted using Garbage’s algorithm will be one of this three types given bellow…

  1. Fully sorted
  2. Require one swapping that makes the array sorted
  3. Require more than one swapping to sort the array

Your task is to identify this terms. [NB: Garbage sort is a non-decreasing order sort]

Input:

Each test case contains two lines. (Maximum test case 150 )

First line there will be an integer N that denotes the number of elements of this array. (0<=N<=100000). N=0 means that the program will terminate.

Second line there will be N integers (arr[1],arr[2],arr[3],…….,arr[N]) , represent the elements of an array that is sorted using Garbage’s algorithm. [0<=arr[i]<= 100000000].

Output:

For each test case first print the test cases.

  1. For fully sorted array: print “OK”
  2. For require one swapping that makes the array sorted: print “YES value1 value 2” where value1, value2 are the swapping values and value1<value2.
  3. For require more than one swapping to sort the array: print “NO”.

[Input file is huge. Use faster input output system.]

Sample Input:

4

1 2 3 4

4

4 2 3 1

4

4 3 2 1

0

 

Sample Output:

CASE 1 : OK

CASE 2 : YES 1 4

CASE 3 : NO

 

SUBMIT YOUR ANS

PDF Download link

One comment

  1. partha sarathi says:

    how can i collect garbage in c. i mean the process of collecting garbage in C. plz explain deeply !!!

Leave a Reply

Your email address will not be published. Required fields are marked *