== include(page="template/taskheader" task_id="sormin") ==
Poveste şi cerinţă...
Se dau un şir $A[1..N]$ şi un număr $S$.
h2. Cerinţă
Dintre toate subşirurile de suma $S$, să se determine un subşir pentru care suma $OR$, pe biţi, este minimă.
h2. Date de intrare
Fişierul de intrare $sormin.in$ ...
Fişierul de intrare $sormin.in$ conţine pe primul rând numerele $N$ şi $S$. Pe a doua linie sunt scrise $N$ numere naturale separate prin câte un spaţiu.
h2. Date de ieşire
În fişierul de ieşire $sormin.out$ ...
În fişierul de ieşire $sormin.out$ se vor scrie pe prima linie numerele $R$ şi $M$, reprezentând suma $OR$, pe biţi minimă, respectiv numărul de elemente ale subşirului determinat. Pe a doua linie vor fi scrise, separate prin câte un spaţiu cele $M$ elemente ale subşirului determinat.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100000$
* $1 ≤ S ≤ 50000$
* $1 ≤ A[i] ≤ 5000$
* Fie $x$ şi $y$ două numere naturale. Pentru fiecare din ele avem câte o reprezentare în baza $2, x[k],x[k-1],…,x [1],x [0] şi respectiv $y[k],y[k-1],…,y [1],y [0]$. În cazul în care lungimile reprezentărilor sunt diferite, cea mai scurtă dintre ele se poate prelungi spre stânga cu zerouri. Prin suma $OR$, pe biţi, a numerelor $x$ şi $y$ se înţelege numărul $z$ cu reprezentarea $z[k],z[k-1],…,z [1],z [0]$ unde $z[j] = x[j] | y[j]$, este operaţia definită prin $0 | 0 = 0, 0 | 1 = 1, 1 | 0 = 1, 1 | 1 = 1, 0 ≤ k$. De exemplu $x = 12$ şi $y = 9$ au reprezentările binare $1100$ şi $1001$, iar $x | y = 1101 = 13$
* Pentru testele date se garantează existenţa unei soluţii
* Dacă există mai multe subşiruri cu suma $OR$ minimă, atunci oricare din ele va fi considerat corect. De asemenea, elementele subsirului pot fi afisate in orice ordine.
h2. Exemplu
table(example). |_. sormin.in |_. sormin.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 13 20
2 2 2 2 2 3 3 3 3 5 5 5 5
| 3 8
2 2 2 2 3 3 3 3
|
h3. Explicaţie
...
Nu putem obţine suma 20 doar cu elemente egale cu 2. Putem obtine suma 20 folosind elementele egale cu 2 şi 3. Suma OR este 3, deoarece 2 are reprezentarea binara 10, iar 3 are reprezentarea binară 11, deci 2 | 3 = 3
== include(page="template/taskfooter" task_id="sormin") ==
