Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2021-09-01 19:38:42.
Revizia anterioară   Revizia următoare  
Bad macro "include(page="template/taskheader" task_id="binsearch") == *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ţă 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?