Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на С++:

#include < stdio.h >
#include < string.h >
#define MAXN 12345
class node{public:  int pos,aim;};
node que[2][MAXN];
int  tail[2];
int  disk[MAXN];
int n,m;
void readin(){   
     int i,j,k,l;   
     scanf("%d%d",&n,&m);   
     memset(disk,0,sizeof(disk));   
     l = 0;   
     for (i = 0; i < m; i++)   {      
         scanf("%d",&k);      
         for (j = 0; j < k; j++,l++)      {         
             scanf("%d",&que[0][l].pos);         
             que[0][l].aim  = l+1;         
             disk[que[0][l].pos] = que[0][l].aim;      
         }   
     }   
     tail[0] = l;
}
void doit(){   
     int flag1;   
     int i,j,k,l,o,p,q;   
     int count;   
     count = 0;   
     p = 0;   
     do   {      
          flag1 = 0;      
          q = p ^ 1;
          tail[q] = 0;      
          for (i = 0; i < tail[p]; i++)   {         
              if (que[p][i].pos == que[p][i].aim) continue;         
              if (disk[que[p][i].aim] == 0) {            
                    printf("%d %d\n",que[p][i].pos,que[p][i].aim);
                    flag1 = 1;            
                    disk[que[p][i].aim] = que[p][i].aim;            
                    disk[que[p][i].pos] = 0;            
                    count++;         
                    } 
              else  {            
                    que[q][tail[q]] = que[p][i];            
                    tail[q]++;         
                    }      
          }      
          p = q;      
          q = p ^ 1; tail[q] = 0;      
          for (i = tail[p] - 1; i >= 0; i--) {         
              if (que[p][i].pos == que[p][i].aim) continue;         
              if (disk[que[p][i].aim] == 0) {            
                  printf("%d %d\n",que[p][i].pos,que[p][i].aim); 
                  flag1 = 1;            
                  disk[que[p][i].aim] = que[p][i].aim;            
                  disk[que[p][i].pos] = 0;            
                  count++;         
                  } 
              else {            
                  que[q][tail[q]] = que[p][i];            
                  tail[q]++;         
                  }      
          }      
          p = q;      
          if (flag1) continue;      
          for (i = n; i >= 1; i--) 
             if (disk[i] == 0) break;      
             if (tail[p] == 0) continue;      
             j = tail[p] / 2;      
             printf("%d %d\n",que[p][j].pos,i);      
             disk[que[p][j].pos] = 0;      
             disk[i] = que[p][j].aim;      
             que[p][j].pos = i;      count++;   } 
             while (tail[p]);   
             if (count == 0) printf("No optimization needed\n");
}
int main(){  
    readin();  
    doit();  
    return 0;
}