Administratorul reţelei cu N calculatoare de la SRI împarte, din motive strategice, aceste calculatoare în mai multe grupuri. De fapt, important este doar numărul de grupuri şi numărul de calculatoare din fiecare grup, aşa că împărţirea este descrisă prin şirul numerelor de calculatoare din fiecare grup, ordonat crescător. Periodic, el procedează la o nouă împărţire pe grupe a calculatoarelor. Dintre toate împărţirile posibile ale calculatoarelor în grupuri putem alege ca următoare împărţire doar aceea a cărei descriere precedă sau succedă lexicografic imediat împărţirii curente.
Notă: Spunem că şirul x1x2…xp precede lexicografic şirul y1y2…yk dacă:
a) există un indice j, astfel încât xi=yi pentru toţi indicii i<j şi xj<yj
sau
b) p<k şi xi=yi pentru toţi indicii i≤p
Exemple:
a) 3 7 2 5 precedă lexicografic 3 7 4 1 6 2
b) 1 2 3 precedă lexicografic 2
Cerinţă
Dându-se o împărţire în grupe a celor N calculatoare, determinaţi cele două variante candidate pentru împărţirea următoare.
Date de intrare
Fişierul de intrare grupuri.in conţine pe prima linie două numere naturale nenule N k, reprezentând numărul total N al calculatoarelor din reţea şi respectiv numărul de grupe. Pe linia a doua se află o succesiune de k numere naturale, g1 g2 . . . gk reprezentând numărul calculatoarelor din fiecare grupă.
Date de ieşire
Fişierul de ieşire grupuri.out va conţine 4 linii. Pe prima linie se află numărul natural p (numărul de grupe din împărţirea care precedă lexicografic imediat împărţirea dată), iar pe a doua linie p numere naturale separate prin spaţii h1 h2 ... hp (numărul de calculatoare din cele p grupe ale împărţirii precedente). Pe a treia linie se află un număr natural u (numărul de grupe din împărţirea care succedă lexicografic imediat împărţirea dată), iar pe a patra linie se află u numere naturale separate prin spaţii t1 t2 ... tu (numărul de calculatoare din cele u grupe ale împărţirii următoare).
Restricţii
• 2 ≤ N ≤ 1000
• g1+g2+...+gk = h1+h2+...+hp = t1+t2+...+tu = N
• 1 ≤ g1 ≤ g2 ≤...≤ gk;
• 1 ≤ h1 ≤ h2 ≤...≤ hp;
• 1 ≤ t1 ≤ t2 ≤...≤ tu;
• 1 < k < N
• 1 ≤ p, u ≤ N