#include<iostream>
using namespace std;

struct nodo{int info; nodo* next; nodo(int a =0, nodo* b=0){info=a; next=b;}};
struct nodoL{nodo* info; nodoL* next; nodoL(nodo* a =0, nodoL* b=0){info=a; next=b;}};

nodo* clone(nodo*L)
{
  if(L)
    return new nodo(L->info,clone(L->next));
  return 0;
}

void stampaL(nodo*L)
{
  if(L)
    {cout<<L->info<<' '; stampaL(L->next);}
  else
    cout<<endl;

}

void stampaLL(nodoL*LL,int n)
{
  if(LL)
    {cout<<"fetta "<<n<<") "; stampaL(LL->info); stampaLL(LL->next,n+1);}
}

nodo* faiL(int n) {
  if(n>0)
    return new nodo(n, faiL(n-1));
  return 0;

}

// prototipi funzioni ricorsive
int contaric(nodo*);
nodo* tagliaric(nodo*&, int);
nodoL* affettaric(nodo*&, int*, int);

//prototipi funzioni iterative
nodo* concatiter(nodo*, nodo*);
int contaiter(nodo*);
nodo* tagliaiter(nodo*&, int);
nodoL* affettaiter(nodo*&, int*, int);

main()
{
  cout<<"start"<<endl;
  nodo* L= faiL(10);
  nodo*L0=clone(L);
  int n, A[10];
  cin >> n;
  for(int i=0; i<n; i++)
    cin >> A[i];
  nodoL*K=affettaric(L,A,n);
  cout<<"Lric=";
  stampaL(L);
  cout<<"LLric:"<<endl;
  stampaLL(K,1);
  cout<<endl;
  K=affettaiter(L0,A,n);
  cout<<"Liter=";
  stampaL(L0);
  cout<<"LLiter:"<<endl;
  stampaLL(K,1);
  cout<<"end"<<endl;

}

//PARTE RICORSIVA

//PRE=(lista(L) corretta, dimA>=0 e A contiene dimA interi non negativi, vL=valore iniziale di L)
nodoL* affettaric(nodo*& L, int* A, int dimA) {
    if(!L) return 0;
    if(!dimA) return 0;
    if(contaric(L)>=A[0]) {
    nodo* t=tagliaric(L, A[0]);
    nodoL* LL=new nodoL(t);
    //PRE_ric=(lista(L) corretta, dimA-1>=0 e A+1 contiene dimA-1 interi non negativi, vL=valore iniziale di L)
    LL->next=affettaric(L, A+1, dimA-1);
    //POST_ric=(restituisce una lista di nodi di tipo nodoL che puntano alle fette di vL secondo quanto descritto, L=vL-fette tolte
    return LL;
    } else return 0;
}
//POST=(restituisce una lista di nodi di tipo nodoL che puntano alle fette di vL secondo quanto descritto, L=vL-fette tolte)

/* DIMOSTRAZIONE DI CORRETTEZZA
CASO BASE:
    1. !L, cioe' la lista puntata da L e' vuota: in tal caso LL e' vuota e la funzione restituisce 0, L=vL-fette tolte=0 corretta
    2. !dimA, cioe' non ci sono valori nell'array: in tal caso LL e' vuota e la funzione restituisce 0, L=vL-fette tolte=vL-0=vL corretta
    3. contaric(L)<A[0]: in tal caso L contiene meno elementi del primo valore dell'array e lafunzione restituisce 0, L=vL-fette tolte=vL-0=vL corretta
PASSO INDUTTIVO:
    A questo punto abbiamo L!=0 (-> la lista puntata da L e' ben formata e non vuota) && dimA>0 (-> l'array A contiene degli elementi) &&
    numero di nodi di lista(L)>=primo valore di A (-> si puo' staccare una porzione) [N.B. assumendo contaric valida]. La PRE_ric e':
        1.lista(L) e' corretta;
        2.dimA-1>=0;
        3.A+1 contiene dimA-1 interi non negativi.
    Tutte le pre condizioni sono valide, in quanto (lista(L) e' corretta) && (dimA-1>=0 -> dimA>=1) da caso base && (A+1 contiene dimA-1 interi non negativi) di conseguenza.
    La PRE_ric e' quindi valida, e di conseguenza lo e' anche POST_ric
*/

//PRE=(lista(L) corretta)
int contaric(nodo* L) {
    if(!L) return 0;
    else return 1+contaric(L->next);
}
//POST=(restituisce il numero di nodi presenti in L)

//PRE=(lista(L) corretta e con numero di nodi>=n (garantito da contaric), n>=0 e' il numero di nodi da tagliare, vL=lista(L))
nodo* tagliaric(nodo*& L, int n) {
    if(!L) return 0;
    if(!n) return 0;
    nodo* t=L;
    L=L->next;
    t->next=tagliaric(L, n-1);
    return t;
}
//POST=(ritorna la porzione di vL tagliata, lista(L)=vL-porzione tagliata)


//PARTE ITERATIVA

//PRE=(lista(L) corretta, dimA>=0 e A contiene dimA interi non negativi, vL=valore iniziale di L)
nodoL* affettaiter(nodo*& L, int* A, int dimA) {
    if(!L) return 0; //casi base
    if(!dimA) return 0;
    if(contaiter(L)<A[0]) return 0;
    nodoL* LL=0;
    //PRE_while=(lista(L) corretta e non vuota, dimA>0, esiste almeno una prima parte da staccare, v_dimA=dimA, vL=lista(l))
    while(dimA && L) { //R=(lista(L) e' corretta e non vuota)&&(dimA>0)&&(LL contiene v_dimA-dimA nodi che sono le fette di L)&&(L=vL-n con n=v_dimA-dimA=fette staccate)
        if(contaiter(L)>=A[0]) {
            nodo* t=tagliaiter(L, A[0]);
            if(!LL) LL=new nodoL(t, 0);
            else {
                nodoL* X=LL; //mi ricordo dove sta
                while(LL->next) LL=LL->next;
                LL->next=new nodoL(t, 0);
                LL=X;
            }
            A++;
            dimA--;
        } else dimA=0; //condizione di uscita dal ciclo
    }
    //POST_while=(lista(LL) contiene le parti di lista staccate, L e' quello che avanza (come da esempio)
    return LL;
}
//POST=(restituisce una lista di nodi di tipo nodoL che puntano alle fette di vL secondo quanto descritto, L=vL-fette tolte)

//PRE=(lista(L) corretta)
int contaiter(nodo* L) {
    if(!L) return 0;
    int i=0;
    while(L) {
        i++;
        L=L->next;
    }
    return i;
}
//POST=(restituisce il numero di nodi presenti in L)

//PRE=(lista(L) corretta e con numero di nodi>=n (garantito da contaiter), n>=0 e' il numero di nodi da tagliare, vL=lista(L))
nodo* tagliaiter(nodo*& L, int n) {
    if(!L) return 0;
    if(!n) return 0;
    nodo* p=0;
    while(n && L) { //R=(n>0)&&(lista(L) non vuota)&&(v_n=n)&&(p contiene v_n-n nodi consecutivi di lista(L))
        nodo* t=L;
        L=L->next;
        t->next=0;
        p=concatiter(p, t);
        n--;
    }
    return p;
}
//POST=(ritorna la porzione di vL tagliata, lista(L)=vL-porzione tagliata)

//PRE=(lista(p) ben formata, lista(t) ben formata, v_p=lista(p))
nodo* concatiter(nodo* p, nodo* t) {
    if(!p) return t;
    if(!t) return p;
    nodo* X=p;
    while(p->next) p=p->next;
    p->next=t;
    return X;
}
//POST=(restituisce v_p@t con @=concatenazione)