Fişierul intrare/ieşire:	binsearch.in, binsearch.out	Sursă	EJOI 2021, ziua 2
Autor	Alexa Tudose	Adăugată de	Voicu Mihai Valeriu •cadmium_
Timp execuţie pe test	0.5 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Binsearch

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₁,..., 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ă.)

Date de intrare

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.

Date de ieşire

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

Restricţii

• ... ≤ ... ≤ ...

Exemplu

Explicaţie

...

Cum se trimit solutii?