•Cosmin
|
|
« : Ianuarie 07, 2012, 14:59:15 » |
|
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #1 : Ianuarie 07, 2012, 15:21:09 » |
|
La IOI 2007, atît eu cît și gcosmin am luat 80 de puncte pe o problemă pentru ca depășeam int-ul cînd adunam hi + lo.
Sfaturi foarte bune în acest post!
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•Victor10
Strain
Karma: 3
Deconectat
Mesaje: 11
|
|
« Răspunde #2 : Martie 01, 2012, 22:01:37 » |
|
Inainte de toate, al doilea cod functioneaza pentru un sir indexat de la 1 sau de la 0?
Oricum ar fi, mie nu-mi functioneaza pe cazul in care elementul cautat se afla pe ultima pozitie in sirul sortat.
|
|
|
Memorat
|
|
|
|
•soriyn
|
|
« Răspunde #3 : Martie 01, 2012, 22:10:16 » |
|
Nu sunt sigur dar cred ca,ironic, si cautarea aia binara e gresita Ia vezi iti merge daca in linia zece in loc de || pui && ?
|
|
|
Memorat
|
|
|
|
•Victor10
Strain
Karma: 3
Deconectat
Mesaje: 11
|
|
« Răspunde #4 : Martie 01, 2012, 22:13:29 » |
|
Atunci nu merge pentru cazul in care elementul cautat se afla pe prima pozitie )
|
|
|
Memorat
|
|
|
|
•soriyn
|
|
« Răspunde #5 : Martie 01, 2012, 22:16:55 » |
|
Mie imi merge si pentru prima pozitie. Poti pune codul aici ?
|
|
|
Memorat
|
|
|
|
•Victor10
Strain
Karma: 3
Deconectat
Mesaje: 11
|
|
« Răspunde #6 : Martie 01, 2012, 22:18:45 » |
|
#include <cstdio>
int N, A[1005];
int binary_search(int val) { int hi=N, lo=-1, mid; while(hi - lo > 1){ mid=lo+(hi-lo)/2; if(A[mid] <= val) lo=mid; else hi=mid; } if(hi==N && A[hi]!=val) return -1; else return hi; }
int main(){ freopen("date.in","r",stdin); int j, poz, x; scanf("%d",&N); for(j=0; j<N; ++j) scanf("%d",&A[j]); scanf("%d",&x); poz=binary_search(x); printf("\n%d",poz); }
|
|
|
Memorat
|
|
|
|
•soriyn
|
|
« Răspunde #7 : Martie 01, 2012, 22:26:23 » |
|
Mie tot imi merge. Pentru ce set de date nu ti-a functionat tie ?
|
|
|
Memorat
|
|
|
|
•Victor10
Strain
Karma: 3
Deconectat
Mesaje: 11
|
|
« Răspunde #8 : Martie 01, 2012, 22:27:59 » |
|
7 1 3 3 4 5 6 7 1
Pe prima linie numarul de elemente. Pe a doua elementele. Pe a treia elementul cautat
|
|
|
Memorat
|
|
|
|
•soriyn
|
|
« Răspunde #9 : Martie 01, 2012, 22:35:38 » |
|
Am descoperit o greseala in codul tau. Ai indexat vectorul de la 0, deci ultimul numar se afla pe pozitia N-1. Modifica in cautare hi=N-1
|
|
|
Memorat
|
|
|
|
•Victor10
Strain
Karma: 3
Deconectat
Mesaje: 11
|
|
« Răspunde #10 : Martie 01, 2012, 22:43:48 » |
|
neah, nu merge nici asa, imi zice ca 1 se afla pe pozitia 1, dar de fapt e pe 0. La tine merge cum trebuie? Ai sirul indexat de la 1 sau de la 0?
|
|
|
Memorat
|
|
|
|
•soriyn
|
|
« Răspunde #11 : Martie 01, 2012, 23:02:08 » |
|
Ai dreptate, asa e si la mine. Nu stiu, ma depaseste. O sa las pe altcineva mai in masura sa iti raspunda.
|
|
|
Memorat
|
|
|
|
•Victor10
Strain
Karma: 3
Deconectat
Mesaje: 11
|
|
« Răspunde #12 : Martie 01, 2012, 23:02:55 » |
|
Ok, mersi oricum pentru efortul depus
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #13 : Martie 01, 2012, 23:07:24 » |
|
Codul din blog post e bun.
Ti-am gasit greseala, ai schimbat din a[mid] < x in a[mid] <= x.
Adica ai bushit exact unde ziceam sa fi atent in articol, la pastrarea invariantului a[lo] < x <= a[hi]. daca lo = -1 si hi = N invariantul asta e valid, deci sugestia cu hi = N-1 era gresita daca vrei sa folosesti invariantul ce l-am mentionat.
Daca tii neaparat sa testezi a[mid] <= x atunci trebuie sa folosesti alt invariant cu a[lo] <= x < a[hi] si sa retunezi ca rezultat pozitia lo daca ea nu e -1 (adica, daca elementul a fost gasit in sir).
|
|
« Ultima modificare: Martie 01, 2012, 23:14:16 de către Cosmin Negruseri »
|
Memorat
|
|
|
|
•Victor10
Strain
Karma: 3
Deconectat
Mesaje: 11
|
|
« Răspunde #14 : Martie 01, 2012, 23:25:27 » |
|
Aoleu aoleu aoleu. Ai dreptate. Mersi mult
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #15 : Martie 01, 2012, 23:29:42 » |
|
Ai inteles acuma ce e cu invariantii astia?
|
|
|
Memorat
|
|
|
|
•Victor10
Strain
Karma: 3
Deconectat
Mesaje: 11
|
|
« Răspunde #16 : Martie 01, 2012, 23:46:04 » |
|
hmmmm... cred ca am inteles
Pentru cazul meu cu A[mid]<=val ar trebui sa afiseze pozitia cea mai mare pe care se afla numarul cautat, nu? Daca e asa, atunci cat de cat m-am prins.
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #17 : Martie 01, 2012, 23:53:51 » |
|
Invariantul a[lo] <= x < a[hi] gaseste ultima pozitie a lui x in sir cand hi = lo + 1 (daca x e in sir).
|
|
|
Memorat
|
|
|
|
•Victor10
Strain
Karma: 3
Deconectat
Mesaje: 11
|
|
« Răspunde #18 : Martie 02, 2012, 00:18:49 » |
|
Tocmai avusesi o revelatie. Cred ca m-am prins. Mersi mult pentru explicatii!
|
|
|
Memorat
|
|
|
|
•MciprianM
|
|
« Răspunde #19 : Martie 04, 2012, 22:06:12 » |
|
Poti sa incerci problema: http://codeforces.com/contest/158/problem/EE din ciclul cautare binara doua cautari binare in cautare binara in cautare liniara. Ca sa exersezi invariantii astia. Succes L.E.: Daca vrei sa iti fortezi creierii, fa-o fara functii.
|
|
« Ultima modificare: Martie 04, 2012, 22:11:39 de către Marginean Ninu Ciprian »
|
Memorat
|
|
|
|
•bogdan2412
|
|
« Răspunde #20 : Martie 04, 2012, 22:31:41 » |
|
Cum ai facut E folosind cautare binara? Ce complexitate ai per total?
|
|
|
Memorat
|
|
|
|
•MciprianM
|
|
« Răspunde #21 : Martie 04, 2012, 23:02:23 » |
|
Nu am terminat-o, dar ideea mea e asa: Pentru fiecare secunda i de la prima pana la ultima din zi, incercam sa determinam cat de mult poate dormi Ghita, daca incepe sa doarma in secunda i, ignorand cel mult k telefoane. Cat de mult poate dormi (l secunde), determinam cu o cautare binara pe intervalul [0, 86400]. Verificam daca poate dormi incepand din secunda i, timp de l secunde, facand doua cautari binare. Cu una gasim ultimul telefon care se termina inainte de secunda i, si cu cealalta, primul telefon care incepe dupa secunda i + l.
L.E.: Complexitatea ar fi O (S * log S * log N). Unde S e numarul de secunde din intervalul de timp pe care se poate dormi si N e numarul de telefoane. In cazul nostru S=86400. L.L.E: Totusi ma gandesc ca s-ar putea sa fie gresita solutia asta. Ironic, avand in vedere titlul "Cautarea ta binara este gresita"
|
|
« Ultima modificare: Martie 04, 2012, 23:36:50 de către Marginean Ninu Ciprian »
|
Memorat
|
|
|
|
•S7012MY
|
|
« Răspunde #22 : Martie 04, 2017, 10:52:45 » |
|
Eu folosesc while(st<dr). Si am grija la setarea mijlocului si la actualizarea intervalului de cautare. In final rezultatul va fi in st.
|
|
|
Memorat
|
|
|
|
|