Fişierul intrare/ieşire:binsearch.in, binsearch.outSursăEJOI 2021, ziua 2
AutorAlexa TudoseAdăugată decadmium_Voicu Mihai Valeriu cadmium_
Timp execuţie pe test1 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Binsearch

ATENTIE: La aceasta problema, punctajul maxim va fi considerat 200.

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ţă b1,..., bn ∈ {true, false}. Se garantează că există un număr natural k pentru care n = 2k − 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ă bi. 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 bi = true, iar dacă este '0', atunci bi = false.

Date de ieşire

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

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 = 2k − 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 2k = n - 1) pentru toate testele dintr-un subtask, atunci se primesc 50% din punctele alocate acelui subtask.
  • În plus:
#PunctajRestricţii
13bi = true
24bi = false
3161 ≤ n ≤ 7
4251 ≤ n ≤ 15
522n = 216-1 şi fiecare bi este generat uniform aleator din mulţimea {true, false}
630Fără restricţii suplimentare

Exemple

binsearch.inbinsearch.out
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

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 b2 = 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 b4 = false.

Exemplul 2. Avem S(p) = 0 pentru ambele teste.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?