Na tanjiru su poređane palačinke, jedna na drugu. Sve palačinke su različite veličine, označene brojevima od 1 do n. Mali Đokica mora da poređa palačinke po veličini, tako da je palačinka sa brojem n na dnu, a palačinka broj jedan na vrhu. Jedino što on može da uradi jeste da podmetne spatulu ispod neke palačinke i prevrne sve palačinke koje su iznad spatule (obrne im redosled, pogledaj sliku desno). Pomozite malom Đokici da sortira palačinke, tako da broj prevrtanja bude manji od 2n. Za rešenje sa većim brojem prevrtanja se ne dobijaju poeni!

Ulaz:

U prvom redu ulazne datoteke ZAD5.DAT nalazi se prirodan broj n (1 ≤ n ≤ 5000), koji predstavlja broj palačinki. U sledećih n redova je data permutacija brojeva od 1 do n, u i-tom redu je broj a[i] (1 ≤ a[i] ≤ n), koji predstavlja veličinu palačinke na i-tom mestu, brojeći odozgo.

Izlaz:

U izlaznu datoteku ZAD5.RES upisati broj prevrtanja k (0 ≤ k < 2n). U svakom od sledećih k redova treba po jedan broj - redni broj palačinke ispod koje se postavlja spatula pri odgovarajućem prevrtanju (kada se određuje redni broj, palačinke se broje od vrha). Ako postoji više rešenja sa manjim brojem poteza od 2n, štampati bilo koje rešenje.

Primer:

5
2
5
1
3
4

4
3
2
5
4

Objašnjenje:

Izvršeno je 4 prevrtanja, a rezulatati su prikazani ispod.

2     1     5     4     1
5     5  →  1     3     2
1  →  2     2     2     3
3     3     3     1  →  4
4     4     4  →  5     5

Najlakši algoritam za problem “pancake sorting” zahteva najviše 2n - 3 prevrtanja. Optimalna konstanta je između 1 i 5/3, ali se tačna vrednost ne zna.

Uvek dovodimo najveću palačinku koja nije na svom mestu, jednim prevrtanjem na vrh gomile, a zatim još jednim obrtanjem je premestimo na njeno mesto. Ovo ponavljamo za sve preostale palačinke, dakle najviše n – 1 puta. Kada ostanu samo dve palačinke, vršimo najviše jedno prevrtanje spatulom.

Složenost algoritma je O (n^2), jer n puta vršimo prefiksno obrtanje i nalaženje maksimuma.

Pseudokod:

   Num_Flip = 0;
   for i = n downto 1 do
      if (a [i] <> i) then begin
         max = 1;
         while ((max < i) and (a [max] <> i))
            max++;
         if (max <> 1) then begin
            Num_Flip = Num_Flip + 1;
            s [Num_Flip] = max;
            Swap (max);
         end;
         Num_Flip = Num_Flip + 1;
         s [Num_Flip] = i;
         Swap (i);
      end;

#include <stdio.h>
#define MaxN 5001

long n, k, a [MaxN], s [2 * MaxN];

void Input ()
{
  FILE *in;
  long i;

  in = fopen ("zad5.dat", "r");
  fscanf (in, "%ld", &n);
  for (i = 1; i <= n; i++)
    fscanf (in, "%ld", &a [i]);
  fclose (in);
}

void Output ()
{
  FILE *out;
  long i;

  out = fopen ("zad5.res", "w");
  fprintf (out, "%ld\n", k);
  for (i = 1; i <= k; i++)
    fprintf (out, "%ld\n", s [i]);
  fclose (out);
}

void Swap (long k)
{
  long i, tmp;

  for (i = 1; i <= k / 2; i++)
  {
    tmp = a [i];
    a [i] = a [k + 1 - i];
    a [k + 1 - i] = tmp;
  }
}

void Solve ()
{
  long i, max;

  k = 0;
  for (i = n; i >= 1; i--)
    if (a [i] != i)
    {
      max = 1;
      while ((max < i) && (a [max] != i))
        max++;
      if (max != 1)
      {
        k++;
        s [k] = max;
        Swap (max);
      }
      k++;
      s [k] = i;
      Swap (i);
    }
}

int main ()
{
  Input ();
  Solve ();
  Output ();
  return 0;
}