Doua numere naturale nenule n1 si n2 se pot "alipi" pe K biti, daca īn reprezentarea lor binara au fiecare cel putin K biti (primul bit fiind 1), iar ultimii K biti ai numarului n1 coincid cu primii K biti ai numarului n2. Dupa alipire rezulta un alt numar, format din concatenarea lui n1 cu n2, dar īn care secventa comuna de K biti apare o singura data si īn ea fiecare bit este īnlocuit cu complementarul sau (0 devine 1 si invers).
Exemplu: Numerele 78=10011102 si 25=110012 se pot alipi pe 3 biti si rezulta numarul 1001001012=293, numerele 78 si 25 fiind pierdute.
Numerele nr1, nr2, ..., nrM formeaza o lista de alipiri pe K biti de lungimea M > 0, cu finalul P, daca nr1 se alipeste pe K biti cu nr2, rezultatul se alipeste pe K biti cu nr3, ... , rezultatul se alipeste pe K biti cu nrM, iar rezultatul final este numarul P.
Cerinta Pentru
un sir dat de numere naturale nenule si valorile naturale nenule K si
P, se cere:
a)
sa se determine lungimea maxima a unei liste de alipiri pe K
biti, formata cu elemente din sirul dat, nu neaparat īn ordinea din acest sir;
b)
sa se verifice daca se poate obtine, cu numere din sirul dat, o lista
de alipiri pe K biti cu finalul P; īn caz afirmativ sa se precizeze
o lista de lungime minima de alipiri pe K biti cu finalul P.
Date de intrare
Fisier de intrare: ALIPIRI.IN
Linia 1:
N
K P
· Trei
numere naturale nenule, separate prin cāte un spatiu, reprezentānd numarul N al numerelor date, lungimea K a secventelor comune din alipiri, respectiv valoarea P a numarului care trebuie obtinut prin alipiri;
Linia 2:
nr1
nr2 ... nrN
· N numere naturale nenule, separate prin cāte un spatiu,
reprezentānd sirul dat.
Fisier de iesire: ALIPIRI.OUT
Linia 1: M
·
numar
natural nenul, reprezentānd rezultatul de la cerinta a);
Linia 2: mesaj
·
daca
cerinta b) poate fi satisfacuta, pe aceasta linie se va scrie 'DA', īn caz contrar se va scrie 'NU';
Linia 3: nr1
nr2 ...
·
daca
pe linia 2 ati scris 'DA', pe aceasta linie se va scrie o lista de alipiri
(pe K biti) de lungime minima cu finalul P; numerele din lista
se vor separa prin cāte un spatiu.
Restrictii
· 0 < K < 16 , 0 < N < 31 , 0 < P < 2000000000
(doua miliarde).
·
daca
cerinta b) este satisfacuta de mai multe liste (de lungime minima), īn fisier
se va scrie una singura.
·
numerele
din sirul dat sunt mai mici ca 32000;
·
pentru ambele cerinte fiecare numar din sirul de intrare poate
aparea cel mult o data īn listele de alipiri considerate.
Exemplu
ALIPIRI.INALIPIRI.AUT
4
DA
59 31 14
Nota. Se acorda punctaje partiale: a) 40%; b) 60%
Timp maxim de executare/test: 3 secunde