INFOMAN брой 5

{ This is the input data: N;  P[1]; P[2]; ....; P[N]
 7
 2
 3
 7
 4
 5
 6
 1
                               ГАФА НА БАНКАТА
                               ---------------

   Една банка имала много клонове. Веднъж след поредния upgrade в системата
 се оказало, че базите от данни на някои клонове са разменени. Всеки клон е
 получил база от данни, която принадлежи на някой друг клон. Известно е коя
 база от данни в кой клон е попаднала. За нормалната работа на банката тряб-
 вало в най-кратък срок  отделните клонове да си разменят базите от данни с
 цел всеки клон да получи собствената си.  Два произволни клона могат да си
 разменят базите, като това отнема 1 ден. В един и същи ден едновременно ня-
 колко различни двойки клонове могат да си разменят базите.За един ден един
 клон може да прави най-много една размяна.Да се намери минималния брой дни,
 необходими за подреждане на базите. За всеки ден да се посочат всички двой-
 ки колонове, които си размят базите.

    РЕШЕНИЕ: На практика е дадена една пермутация на числата от 1 до N и се
 пита за най-малко колко дни тя може да се преобразува в редицата 1,2,...,N,
 като за един ден всеки елемент може да се разменя с някой друг,но един еле-
 мент не може да участва в повече от 1 разместване за един ден. Лесно се до-
 казва, че броя дни е 0, 1 или 2. Дните са 0, ако пермутацията е 1,2,....,N.
 Ако за всеки елемент x = 1...N от дадената пермутация P[1...N] е изпълнено
 P[P[x]]=x, дните са 1, защото за 1 ден можем да разменим всички двойки еле-
 менти (x,P[x]) и ще получим търсената пермутация 1,2,..,N. Във всички оста-
 нали случаи броя дни са 2. Това е така, защото винаги можем за един ден да
 получим пермутация, за която за всеки елемент x е изпълнено P[P[x]]=x.  От
 такава пермутация вече показахме,че за един ден можем да получим решението.
 Как обаче става получаването на пермутация P[P[x]]=x от произволна друга ?
 Алгоритъмът е такъв: Започваме от двойката (1,P[1]). Понеже имаме двойката
 (1,P[1]), трябва задължително да имаме и двойката (P[1],1).  Това означава,
 че трябва да направим такава размяна, че след нея P[P[1]]=1.  Нека това бъ-
 де размяна на елемента с номер P[1] с елемента с номер P[x]. След това взе-
 маме двойката (P[x],P[P[x]]) и правим аналогична размяна. Това правим дока-
 то не се получи така, че двойката, която трябва да обработваме е вече обра-
 ботена. Тогава избираме друг елемент a, който не е обработен и съответства-
 щата му двойка (a,P[a]). За нея правим отново такава рзмяна,че да се изпъл-
 ни P[P[a]]=a.  Следваща двойка е двойката (b,P[b]), където b е числото, за
 което P[b]=a. Това отново продължаваме докато не се окаже,че текущата двой-
 ка е вече претътпявала размяна.  И понеже няма как по-ясно да се обясни ал-
 горитъма, най-добре е той да се илюстрира чрез псевдокод:
     for BegValue:= 1 to N
       a:=BegValue;
       if not претърпявал_размяна(a) then
         repeat
           NewA:=Poz[a];
           Swap(P[a],Poz[a]);
           претърпявал_размяна(P[a]):=true;
	   претърпявал_размяна(Poz[a]):=true;
           a:=NewA;
         until претърпявал_размяна(P[a]);
 където процедурата Swap(i1,i2) разменя стойностите елементите с индекси i1
 и i2, а с a=Poz[x] се означава числото a, за което P[a]=x. Как по-точно ра-
 боти алгоритъма може да се види от резултатите,които той извежда при корек-
 тни входни данни.  Процедурата Adjust прави нужните размени, за да преведе
 пермутацията P[i] във вид,  в който за всяко x=1...N е изпълнено P[P[x]]=x
 по посочения с псевдокод алгориъм за 1 ден.  Ако тя е първоначално в такъв
 вид, процедурата не прави нищо и не увеличава броя дни. Иначе отпечатва не-
 обходимите размени като програма за първия ден. Процедурата Arrange подреж-
 да получената от Adjust пермутация във вида 1,2,..,N за 1 ден. Ако пермута-
 цията е вече в този вид, не прави нищо.  Тя отпечатва нужните размени, ако
 има такива.
}

CONST InFileName  = 'BANK.PAS';
      MaxN = 10000;

VAR P,Poz: array[1..MaxN] of integer;
    N,Turns: integer;
    NewTurn: boolean;

Procedure ReadData; {read N and P[1...N] from input file}
Var F: Text;
Begin
  Assign(F,InFileName); Reset(F); ReadLn(F);
  ReadLn(F,N);
  for N:= 1 to N do
    begin ReadLn(F,P[N]); Poz[P[N]]:=N; end;
  Close(F);
End;

Procedure Swap(Index1,Index2:integer); {Swap P[Index1] with P[Index2]}
Var Tmp: integer; {if Index1 <> Index2. Otherwise do nothing}
Begin
  if Index1 = Index2 then Exit;
  if NewTurn then
    begin Inc(Turns); WriteLn('Turn ',Turns,' :'); NewTurn:=false; end;
  WriteLn(Index1,'-',Index2);
  Tmp:=P[Index1]; P[Index1]:=P[Index2]; P[Index2]:=Tmp;
  Poz[P[Index1]]:=Index1; Poz[P[Index2]]:=Index2;
End;

Procedure Adjust; {Adjust P[1..N] in such order that P[P[a]]=a for a=1..N}
Var a,BegValue,NewA: integer;
    Swapped: array[1..MaxN] of boolean;
Begin
  FillChar(Swapped,SizeOf(Swapped),false);
  NewTurn:=true;
  for BegValue:= 1 to N do
    begin
      a:=BegValue;
      if not Swapped[a] then
        repeat
          NewA:=Poz[a];
          Swap(P[a],Poz[a]);
          Swapped[P[a]]:=true; Swapped[Poz[a]]:=true;
          a:=NewA;
        until Swapped[P[a]];
    end;
End;

Procedure Arrange; {Arrange P in normal order. Swap every 'a' with 'P[a]'}
Var a: integer;
Begin
  NewTurn:=true;
  for a:= 1 to N do
    Swap(a,P[a]);
End;

BEGIN
  ReadData;
  WriteLn;
  Turns:=0;
  Adjust;
  Arrange;
  WriteLn('Total ',Turns,' turns');
END.