{
Solution for task SORT3
-------- --- ---- -----
The basic idea behind our solution is the following.
Compute first the number of appearances Na[x] for elements x=1, 2, 3 in
the input sequence. Then the sorted sequence consists of Na[1] number of
1's followed by Na[2] number of 2's and then Na[3] number of 3's.
We say that an element x is in the place of y's if the current position of x
equals the position of an element y in the sorted sequence. We use the
abbreviation x:y to denote an element x in place of y's.
Next compute NEP[x,y], the number of elements x's in the place of y's for all
x and y. Consider the following algorithm written in pseudo-code.
NoCh:=0;
While Not Sorted(S) Do Begin
If there are x and y in each other's place Then Begin
Inc(NoCh);
Exchange x and y;
Update NEP[x,y] and NEP[y,x];
End Else Begin
If (NEP[1,2]>0) And (NEP[3,1]>0) Then Begin
Exchange a pair of elements 3:1 and 1:2 ;
Update NEP[1,2] And NEP[3,1];
Inc(NoCh);
End;
If (NEP[2,1]>0) And (NEP[1,3]>0) Then Begin
Exchange a pair of elements 2:1 and 1:3 ;
Update NEP[2,1] And NEP[1,3];
Inc(NoCh);
End;
End;
End;
First we show that the number of exchange operations performed by the
algorithm can be given by the expression
Ch(S)=Min(NEP[1,2], NEP[2,1])+
Min(NEP[1,3], NEP[3,1])+
Min(NEP[2,3], NEP[3,2])+
2*Abs(NEP[1,2]-NEP[2,1])
After performing Min(NEP[x,y], NEP[y,x]) exchange operations for all x<>y the
resulting sequence contains NEP[1,2]-NEP[2,1] number of elements 1:2, 2:3, 3:1
if NEP[1,2]>NEP[2,1] and 1:3, 2:1, 3:2 if NEP[1,2]1.
Let S be a sequence and OCh(S)=k.
Consider an optimal sequence of exchange operations that makes S sorted.
Assume that the first exchange operation exchanges elements x1:y1 and x2:y2
( or x1:y2 and x1:y1) and denote by S' the resulting sequence.
We distinguish the following two cases:
C1: x1=y2 and x2=y1 or
NEP[1,2]>NEP[2,1] and x1=1, y1=2, x2=3, y2=1 or
x1=1, y1=2, x2=2, y2=3 or
x1=3, y1=1, x2=2, y2=3 or
NEP[1,2]>NEP[2,1] and x1=2, y1=1, x2=3, y2=2 or
x1=2, y1=1, x2=1, y2=3 or
x1=3, y1=2, x2=1, y2=3 or
C2: all other combinations for x1, y1, x2, y2.
We can verify by a routine calculation that Ch(S')=Ch(S)-1 in case C1 and
Ch(S')>=Ch(S) in case C2. In case C1 we obtain by the inductive hypotheses
that the algorithm performs Ch(S)=Ch(S')+1=OCh(S')+1=OCh(S) exchange
operations.
Case C2 contradicts to the optimality condition, therefore an optimal
sequence of exchange operations can only start with an exchange specified in
case C1.
In order to develop efficient algorithm that constructs a sequence of exchange
operations, we introduce the array First, that First[x,y] always contains
the first position of x in place of y's. First[x,y] is computed by the
preprocess procedure and is updated after each exchange operation.
}
Program Sort3;
Const
MaxN =1000; { max number of elements to sort }
Type
ElemType = 1..3;
ArrayType= Array[1..MaxN] Of ElemType;
Matrix = Array[ElemType, ElemType] of Integer;
Var
N : Word; { number of elements to sort }
S : ArrayType; { array of elements to sort }
Na: Array[ElemType] Of Word;{ Na[x] is the number of x's in the input }
NEP : Matrix; { NEP[x,y] is the number of x's }
{ in place of y's }
First: Matrix; { First[x,y] is the first position of x }
{ in place of y's }
NoCh: Word; { number of exchange operations }
OutFile: Text;
Procedure ReadInput;
{ Global output variables: N, S, Na }
Var
InFile: Text;
i,j: Word;
Begin
Assign(InFile, 'input.txt');
Reset(Infile);
ReadLn(InFile, N);
For i:=1 To 3 Do Na[i]:=0;
For i:=1 To N Do Begin
ReadLn(InFile,S[i]);
Inc(Na[S[i]]);
End;
Close(InFile);
End { ReadInput };
Function Min(X,Y: Word):Word;
Begin
If X0 Then Begin
Repeat
Inc(First[i1,i2]);
Until S[First[i1,i2]]=i1;
End;
End { Next };
Procedure Pairs;
Var M,i,x,y :Word;
Begin
For x:=1 To 3 Do
For y:=x+1 To 3 Do Begin
M:=Min(NEP[x,y], NEP[y,x]);
For i:=1 To M Do Begin
WriteLn(OutFile, First[x,y],' ',First[y,x]);
Next(x,y); Next(y,x);
End;
End;
End { Pairs };
Procedure Triples;
Var M,i: Word;
Begin
If NEP[1,2] > 0 Then Begin
M:=NEP[1,2];
For i:=1 To M Do Begin
WriteLn(OutFile, First[3,1],' ',First[1,2]);
WriteLn(OutFile, First[1,2],' ',First[2,3]);
Next(3,1); Next(1,2); Next(2,3);
End;
End Else Begin
M:=NEP[2,1];
For i:=1 To M Do Begin
WriteLn(OutFile, First[2,1],' ',First[1,3]);
WriteLn(OutFile, First[1,3],' ',First[3,2]);
Next(2,1); Next(3,2); Next(1,3);
End;
End;
End;
Begin { Program }
ReadInput;
Preprocess;
Assign(OutFile, 'output.txt');
Rewrite(OutFile);
WriteLn(OutFile,NoCh);
Pairs;
Triples;
Close(OutFile);
End.
{ Scientific Committee IOI'96 }