Patak Dača je dobio novi zadatak da prati planete po zadatom redosledu. Ukupno ima 26 planeta i one su obeležene malim slovima engleskog alfabeta. Patak Dača, međutim, ume da pobrka planete, pa se na kraju ispostavi da niz planeta koje je on obišao ne odgovara nizu planeta koji je stajao u njegovom zadatku. Svemirska komisija utvrđuje kaznene poene tako što nalazi minimalan broj korekcija putanje potreban da se niz planeta koje je Dača obišao prevede u niz planeta u zadatku. Jednu korekciju putanje može predstavljati: (1) zamena jedne planete drugom, (2) umetanje jedne planete, (3) izbacivanje jedne planete, i (4) zamena mesta dveju planeta koje su susedne u početnom nizu (tj. koje su bile susedne i pre svih korekcija). Vaš zadatak je da pomognete komisiji i izračunate broj kaznenih poena koji se dodeljuju Dači, znajući da on, zahvaljujući svom umeću, nikada ne dobija više od 100 kaznenih poena.

Za ovaj zadatak potrebno je da predate izlazne datoteke za 10 ulaznih datoteka pod nazivom planete.01.in, …, planete.10.in koje se nalaze u arhivi koja vam je data. Izlazne datoteke je potrebno nazvati imenima planete.01.out, …, planete.10.out, pri čemu broj u nazivu izlazne datoteke odgovara broju u nazivu ulazne datoteke za dati test primer. Izlazne datoteke treba priložiti (submitovati).

Ulaz:

U prvoj liniji ulaznog tekstualnog fajla nalaze se dva prirodna broja N i M razdvojenih blanko znakom, koji predstavljaju broj planeta u zadatku i broj planeta koje je Patak Dača obišao, respektivno. U drugoj liniji nalazi se N malih slova engleskog alfabeta koje predstavljaju niz planeta u zadatku koji je postavljen Dači. Pre i između slova u drugoj liniji ne postoji ni jedan blanko znak. U trećoj liniji nalazi se M malih slova engleskog alfabeta koje predstavljaju niz planeta koje je Dača obišao. Pre i između slova u trećoj liniji ne postoji ni jedan blanko znak.

Izlaz:

U prvoj liniji izlaznog tekstualnog fajla treba zapisati "# planete, nn" (bez navodnika) gde umesto nn treba zapisati broj test primera. U drugoj liniji izlaznog tekstualnog fajla upisati broj kaznenih poena K koje je Dača zaradio. U svakoj od narednih K linija upisati po jednu korekciju, tako da se njihovom primenom u datom redosledu niz planeta koje je Dača obišao može prevesti u niz planeta koje stoje u opisu njegovog zadatka. Za korekciju (1) ispis se vrši u formatu: 1 H Y, pri čemu H predstavlja redni broj planete koja se zamenjuje, a Y oznaku nove planete na toj poziciji. Za korekciju (2) ispis se vrši u formatu: 2 H Y, pri čemu H predstavlja redno mesto u nizu na koji se umeće planeta, a Y oznaku planete koja se umeće. Za korekciju (3) ispis se vrši u formatu: 3 H, pri čemu H predstavlja redni broj planete koja se izbacuje. Za korekciju (4) ispis se vrši u formatu: 4 H, pri čemu H predstavlja redni broj planete koja se zamenjuje sa sledećom. Ukoliko postoji veći broj sekvenci korekcija koje predstavljaju rešenje, štampati bilo koju od njih.

Primer:

8 8
computer
kmpjutre

# planete, 00
4
1 1 c
2 2 o
3 5
4 7

Objašnjenje:

Minimalan broj korekcija putanje je 4. U prvoj korekciji, prva planeta (k) se zamenjuje planetom c, pa se dobija niz: kmpjutre -> cmpjutre. U drugoj korekciji, na drugu poziciju umeće se planeta o, pa se dobija niz: cmpjutre -> compjutre. U trećoj korekciji, izbacuje se planeta sa pete pozicije, pa se dobija niz: compjutre -> computre. U četvrtoj korekciji, zamenjuju se planete na sedmoj i osmoj poziciji, pa se dobija niz: computre -> computer

#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, Krez, pomeraj;
vector<char> put1, put2;
vector<int> transfList[100001][101];
ofstream outFile("planete.00.out");

void ucitavanje()
{
  int i;
  char ch;

  ifstream inFile("planete.00.in");
  
  inFile >> N >> M;

  do
  {
    inFile >> ch;
  } while ((ch < 'a') || (ch > 'z'));

    put2.push_back(ch);  

  for (i = 0; i < N - 1; i++)
  {
    inFile >> ch;
    put2.push_back(ch);
  }

  do
  {
    inFile >> ch;
  } while ((ch < 'a') || (ch > 'z'));

  put1.push_back(ch);  

  for (i = 0; i < M - 1; i++)
  {
    inFile >> ch;
    put1.push_back(ch);
  }

  inFile.close();
}

bool postoji(int i, int j, int k)
{
  bool already = false;
  int l = 0;
  while ((!already) && (l < transfList[i][j].size()))
  {
    if ((transfList[i][j][l] >> 3) == k)
      already = true;
    l++;
  }
  return already;
}

int obrada()
{

  int i, j, k, l, t;
  bool found1, found2;

  transfList[0][0].push_back(0);

  /// main loop
  for (k = 0; k <= 100; k++)
  {
    found1 = false;
    
    found2 = false;

    cout << k << endl;

    for (i = 0; i <= put1.size(); i++)
      for (l = 0; l < transfList[i][k].size(); l++)
      {
        j = transfList[i][k][l] >> 3;
        /// brisanje i + 1
        if (i < put1.size())
          if (k + 1 + abs(put1.size() - (i + 1) - put2.size() + j) <= 100)
            if (!postoji(i + 1, k + 1, j))
            {
              transfList[i + 1][k + 1].push_back((j << 3) | 1);
              if ((i + 1 == put1.size()) && (j == put2.size()))
                found2 = true;
            }
        /// dodavanje izmedju i i i + 1
        if (j < put2.size())
          if (k + 1 + abs(put1.size() - i - put2.size() + j + 1) <= 100)
            if (!postoji(i, k + 1, j + 1))
            {
              transfList[i][k + 1].push_back(((j + 1) << 3) | 2);
              if ((i == put1.size()) && (j + 1 == put2.size()))
                found2 = true;
            }
        /// zadrzavanje ili promena i + 1
        if ((i < put1.size()) && (j < put2.size()))
          /// zadrzavanje i + 1
          if (put1[i] == put2[j])
          {
            if (!postoji(i + 1, k, j + 1))
            {
              transfList[i + 1][k].push_back(((j + 1) << 3) | 3);
              if ((i + 1 == put1.size()) && (j + 1 == put2.size()))
                found1 = true;
            }
          }
          /// promena i + 1
          else
          {
            if (k + 1 + abs(put1.size() - i - put2.size() + j) <= 100)
              if (!postoji(i + 1, k + 1, j + 1))
              {
                transfList[i + 1][k + 1].push_back(((j + 1) << 3) | 4);
                if ((i + 1 == put1.size()) && (j + 1 == put2.size()))
                  found2 = true;
              }
          }
        /// zamena i + 1 i i + 2
        if ((i + 1 < put1.size()) && (j + 1 < put2.size()))
          if ((put1[i] == put2[j + 1]) && (put1[i + 1] == put2[j]) && (put1[i] != put1[i + 1]))
            if (k + 1 + abs(put1.size() - i - put2.size() + j) <= 100)
              if (!postoji(i + 2, k + 1, j + 2))
              {
                transfList[i + 2][k + 1].push_back(((j + 2) << 3) | 5);
                if ((i + 2 == put1.size()) && (j + 2 == put2.size()))
                  found2 = true;
              }
      }

    if (found1)
      return k;
    else
      if (found2)
      return k + 1;
  }

  return -1;
}

void stampanje(int i, int k, int j)
{
     int l, c;
     bool ponovi = true;
     
     while (ponovi)
     {
         ponovi = false;
         
     l = 0;
         while (l < transfList[i][k].size())
         {
               if ((transfList[i][k][l] >> 3) == j)
                  break;
               else
                   l++;
         }
         
         c = transfList[i][k][l] & 7;
         
         switch (c)
         {
                case 1 :
                     stampanje(i - 1, k - 1, j);
                     outFile << "3 " << i + pomeraj << endl;
                     pomeraj--;
                     break;
                     
                case 2 :
                     stampanje(i, k - 1, j - 1);
                     outFile << "2 " << i + 1 + pomeraj << " " << put2[j - 1] << endl;
                     pomeraj++;
                     break;
                     
                case 3 :
                     i--;
                     j--;
                     ponovi = true;
                     break;
                     
                case 4 :
                     stampanje(i - 1, k - 1, j - 1);
                     outFile << "1 " << i + pomeraj << " " << put2[j - 1] << endl;
                     break;
                     
                case 5 :
                     stampanje(i - 2, k - 1, j - 2);
                     outFile << "4 " << i - 1 + pomeraj << endl;
         }
     }
}

int main()
{
  ucitavanje();
  Krez = obrada();
  outFile << Krez << endl;
  pomeraj = 0;
  if (Krez > -1)
       stampanje(put1.size(), Krez, put2.size());
  outFile.close();

  return 0;
}