SSORT - Silly Sort

no tags 

Your younger brother has an assignment and needs some help. His teacher gave him a sequence of numbers to be sorted in ascending order. During the sorting process, the places of two numbers can be interchanged. Each interchange has a cost, which is the sum of the two numbers involved.

You must write a program that determines the minimal cost to sort the sequence of numbers.


The input file contains several test cases. Each test case consists of two lines. The first line contains a single integer n (n>1), representing the number of items to be sorted. The second line contains n different integers (each positive and less than 1000), which are the numbers to be sorted.

The input is terminated by a zero on a line by itself.


For each test case, the output is a single line containing the test case number and the minimal cost of sorting the numbers in the test case.

Place a blank line after the output of each test case.


3 2 1
8 1 2 4
1 8 9 7 6
8 4 5 3 2 7

Case 1: 4

Case 2: 17

Case 3: 41

Case 4: 34

hide comments
satya_jha123: 2015-09-19 21:28:39

Struggled for almost two days then finally got the concept .Cycle and its values.Quality problem.

Last edit: 2015-09-19 21:29:21
Martijn Muijsers: 2013-12-01 21:47:11

Awesome problem, compliments!

shivendra panicker: 2012-12-15 05:28:30

very good problem!!

beginner :(: 2012-08-31 16:59:31

Really awesome prob :)

littlefriend: 2012-03-27 13:39:40


Devil D: 2012-02-29 09:58:37

How is the answer for second case 17 ?

Gurpreet Singh: 2011-06-22 19:20:12

@wael: "The second line contains n *different* integers "

The Scenario: 2011-05-05 15:36:37

Is there any repeated Number in the sequence ?

Added by:Fudan University Problem Setters
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM/ICPC World Final 2002 (unofficial testdata)