#include <stdio.h>
#define MAX_N 1000

int N,kolik[MAX_N];         //na jakém kolíku je i-tý disk
unsigned long long min_tahu[MAX_N+1][3]; //jak přemístit disky od i-tého na lib. kolík

int main(void) {
  int k,i,disk;

  printf("Zadejte počet disků:");
  scanf("%d",&N);
  for (k=0;k<3;k++) {
    printf("Zadejte disky na kolíku %d:",k+1);
    while (scanf("%d",&i),i) kolik[i-1]=k;
  }

  for (disk=N-1;disk>=0;disk--)
    for (k=0;k<3;k++)     //dáme disky od \uv{disk}-tého na k-tý kolík 
      if (kolik[disk]==k) {//disk je už na místě 
	min_tahu[disk][k]=min_tahu[disk+1][k];
      } else {                  //disk není na místě
	i=3-k-kolik[disk]; //pomocný kolík
	min_tahu[disk][k]=min_tahu[disk+1][i] + (1<<(N-disk-1));
      }

  printf("Nejlepší to bude na kolík %d, celkem %llu přesunů.\n",kolik[0]+1,min_tahu[0][kolik[0]]);
  return 0;
}