== include(page="template/taskheader" task_id="binsearch") ==

Poveste şi cerinţă...

*ATENTIE*: La aceasta problema, punctajul maxim va fi considerat $200$.
 
== code(cpp) |
bool binary_search(int n, int p[], int target){
  int left = 1, right = n;
  while(left < right){
    int mid = (left + right) / 2;
    if(p[mid] == target)
      return true;
    else if(p[mid] < target)
      left = mid + 1;
    else
      right = mid - 1;
  }
  if(p[left] == target) return true;
  else return false;
}
==
 
Este bine ştiut faptul că dacă *$p$* este sortat, atunci codul returnează *$true$* dacă şi numai dacă *$target$* apare în *$p$*. Pe de altă parte, acest lucru poate să nu se întâmple dacă *$p$* nu este sortat.
 
Vi se dă un număr natural $n$ şi o secvenţă $b{~1~},..., b{~n~} ∈ {*$true$*, *$false$*}$. Se garantează că există un număr natural $k$ pentru care $n = 2^k^ − 1$. Trebuie să generaţi o permutare $p$ a elementelor ${1, . . . , n}$ care îndeplineşte anumite condiţii. Fie $S(p)$ numărul de indici $i ∈ {1,..., n}$ pentru care *$binary_search(n, p, i)$* *nu* returnează $b{~i~}$. Trebuie sa alegeţi $p$ astfel încât $S(p)$ este mic (aşa cum este detaliat în secţiunea "Restricţii").
 
(Notă: a permutare a mulţimii ${1, . . . , n}$ este o secvenţa de $n$ numere naturale care conţine fiecare numar natural de la $1$ la $n$ _fix_ odată.)

h2. Date de intrare

Fişierul de intrare $binsearch.in$ ...

Fişierul de intrare $binsearch.in$ conţine pe prima linie $T$, numărul de teste. Urmează apoi testele.
 
Prima linie a unui test conţine numărul natural $n$. Pe cea de-a doua linie se găseşte un şir de $n$ caractere ce conţine doar caracterele $'0'$ şi $'1'$. Aceste caractere nu sunt separate prin spaţii. Dacă cel de-al $i$-lea caracter este $'1'$, atunci $b{~i~} = *true*$, iar dacă este $'0'$, atunci $b{~i~} = *false*$.

h2. Date de ieşire

În fişierul de ieşire $binsearch.out$ ...

În fişierul de ieşire $binsearch.out$ se va afla pentru fiecare test câte o linie, ce conţine o permutare $p$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* Fie $S$ suma tuturor valorilor $n$ într-un singur fişier.
* $1 ≤ N ≤ 100 000$
* $1 ≤ T ≤ 7 000$
* Există un număr natural $k$ pentru care $n = 2^k^ − 1$
* Dacă $S(p) ≤ 1$ pentru toate testele dintr-un subtask, atunci se primesc $100%$ din punctele alocate acelui subtask.
* În caz contrar, dacă $0 ≤ S(p) ≤ k$ (unde 2^k^ = n - 1) pentru toate testele dintr-un subtask, atunci se primesc $50%$ din punctele alocate acelui subtask.
* În plus:
 
table(restrictii). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $3$ | $b{~i~} = *true*$ |
| $2$ | $4$ | $b{~i~} = *false*$ |
| $3$ | $16$ | $1 ≤ n ≤ 7$ |
| $4$ | $25$ | $1 ≤ n ≤ 15$ |
| $5$ | $22$ | $n = 2^16^-1$ şi fiecare $b{~i~}$ este generat uniform aleator din mulţimea ${*true*, *false*}$ |
| $6$ | $30$ | Fără restricţii suplimentare |
 

h2. Exemplu

h2. Exemple

table(example). |_. binsearch.in |_. binsearch.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4
  3
  111
  7
  1111111
  3
  000
  7
  0000000
| 1 2 3
  1 2 3 4 5 6 7
  3 2 1
  7 6 5 4 3 2 1

|

| 2
  3
  010
  7
  0010110
| 3 2 1
  7 3 1 5 2 4 6
|

h3. Explicaţie

...

*Exemplul 1.* În primele două teste avem S(p) = 0.
În cel de-al treilea test, avem $S(p) = 1$. Acest lucru se întâmplă deoarece *$binary_search(n, p, 2)$* returnează *$true$*, deşi $b{~2~} = *false*$.
În cel de-al patrulea test, avem $S(p) = 1$. Acest lucru se întâmplă deoarece *$binary_search(n, p, 4)$* returnează *$true$*, deşi $b{~4~} = *false*$.
 
*Exemplul 2.* Avem $S(p) = 0$ pentru ambele teste.

== include(page="template/taskfooter" task_id="binsearch") ==