infoarena

Problema urmatoare mi-a mancat toata seara asa ca nemaiavand idei m-am gandit ca poate cineva cu suflet ( a se citi minte) ma va ajuta.

Problema:

“Stefan obisnuieste sa -si surprinda  prietenii cu exercitiile de memorie pe care le
face. “Stefan umbla  mereu la el cu un pachet de cartonase care sunt albe pe o
parte si negre pe cealalt . Ultima dat  le-a cerut prietenilor lui s  Ã®nsire toate
100 de cartonase (numerotate de la 1 la 100) în ordine, cu fata alba  Ã®n sus.
S“tefan este legat la ochi si pe rând, câte unul dintre prietenii lui întoarce toate
cartonasele de la i la j. Lui S“tefan i se spun doar valorile lui i si j de la fiecare
întoarcere. Din când în când, prietenii îl testeaz  pe “Stefan întrebându-l ce
culoare are fata de sus a cartonasului k. S“tefan le raspunde mereu corect.

Cerinte:

Proiectati o structura  de date eficienta  care sa  suporte pentru n cartonase cele
2 operatii:
 intoarce(i,j)
 culoare(k)
Analizati complexitatea celor 2 operatii ale structurii de date propuse pentru
cazul cel mai defavorabil. Scrieti un program C care sa  implementeze structura
de date propus  si sa o testeze.

Dupa ce m-am scremut indeajuns de mult(poate mult prea mult) am ajuns la urmatoare concluzie :

Complexitatea minima obtinuta de mine este O(n), insa mi se pare banal de simplu si de aceea sunt convins ca se poate mai eficient.

Apreciez orice ajutor, orice idee, fie ea si gresita.  
Fara cod sau alte minunatii, doar idei.

Poti obtine o complexitate de O ( log N ) pe query folosind un arbore de intervale. Pentru mai multe informatii despre aceasta structura de date, consulta http://infoarena.ro/problema/arbint (http://infoarena.ro/problema/arbint) .

Sau un arbore indexat binar.

De asta aveam nevoie. Va multumesc si ma inclin  \:D/