Grup
Administratorul retelei cu N calculatoare de la SRI împarte, din motive strategice, aceste calculatoare în mai multe grupuri. De fapt, important este doar numarul de grupuri si numarul de calculatoare din fiecare grup, asa ca împartirea este descrisa prin sirul numerelor de calculatoare din fiecare grup, ordonat crescator. Periodic, el procedeaza la o noua împartire pe grupe a calculatoarelor. Dintre toate împartirile posibile ale calculatoarelor în grupuri putem alege ca urmatoare împartire doar aceea a carei descriere precede sau succede lexicografic imediat împartirii curente.
Nota: Spunem ca sirul x1x2...xp precede lexicografic sirul y1y2...yk daca:
a)
exista un indice j, astfel
încât xi=yi pentru toti indicii i<j
si xj<yj
sau
b)
p<k si xi=yi
pentru toti indicii i<=p
Exemple:
a) 3
7 2 5 precede lexicografic 3 7 4 1 6 2
b) 1
2 3 precede lexicografic 2
Cerinta
Dându-se o împartire în grupe a celor N calculatoare, determinati cele
doua variante candidate pentru împartirea urmatoare.
Fisier de intrare: GRUP.IN
Linia 1: N k
– numere naturale nenule, reprezentând numarul total (N) al calculatoarelor din retea si numarul (k) de grupe.
Linia 2: g1 g2 . .
. gk
– numarul calculatoarelor din fiecare grupa.
Date de iesire
Fisier de iesire:
GRUP.OUT
p – numarul de grupe din împartirea care precede lexicografic
imediat împartirea data;
h1 h2 ... hp – numarul de calculatoare
din cele p
grupe ale împartirii precedente;
u – numarul de grupe din împartirea care succede lexicografic
imediat împartirea data;
t1
t2 ... tu – numarul de calculatoare
din cele u grupe ale împartirii urmatoare;
Restrictii si precizari
·
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
Exemplu
GRUP.IN |
GRUP.OUT |
14
3 |
3 |
Timp maxim de executare/test: 1 secunda