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
amanjainnnn: 2021-05-06 13:03:07

Very good question. So many things I learnt. This is why SPOJ is best.

jrseinc: 2020-08-23 21:57:25

What a wonderful problem took me a day to get the concept. Just try to find cycles and make sure that you are using **minimum** element for swaps. similar question. Play "Lost but Won" by Zimmer and solve this.

kkuntal990: 2020-05-26 10:31:57

Output is format seems so unnecessary. Made me rethink my solution :(

sky_scraper: 2019-05-12 12:47:38

I felt really good after solving this problem

priyanshul: 2019-01-22 14:33:12

There is no constraint on N, nice problem.

jcode777: 2018-08-24 23:26:34

@supriyanta Ditto dude. Silly Format.

supriyanta: 2018-08-23 15:37:54

Output format cost 1 wa. :(

pk845: 2018-07-11 06:38:20

+1 to setter!

imkiller: 2018-06-03 08:25:34

Tricky One

tushar8848: 2017-12-24 17:57:45

swap 1 & 6 first

Last edit: 2017-12-24 18:54:47

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)