Big Number

kokosek_sof1 2010-01-21 19:52:16 UTC #21

Szukaj na forum wątków po nazwie zadania, bo większość zadań już była omówiona ze wskazówkami.
tiny.pl/hmfgl
Czyli sortowanie stringów i wyszukiwanie binarne.

xan_sof 2010-10-11 15:02:52 UTC #22

Ostatnio wziąłem się za porządki w zadaniach gdzie mam nie zaliczone 100% testów (ładnie wyglądają statystyki bez żadnych setnych części ). Mam pytanko, czy w końcu to binarne w wyszukiwanie wystarczy, czy trzeba jeszcze coś lepszego zrobić. Jakaś wskazówka? Bo wcześniej pojawiła się wypowiedź że nawet z binarnym TLE w 4 i 5 teście..

gong911 2011-02-26 11:12:09 UTC #23

A moglby ktos pokazac przyklad takiego przeszukiwania binarnego ?
bo tylko widzialem dla liczb
wczesniej jak szukalem liniowo to szukalem tak dlugo az znalazlem i-ty element byl dluzszy od szukanego(szukana liczba tez wczytana jako string byla) badz rownej dlugosci ale leksykograficznie mniejszy... i wypisywalem liczbe i wtedy...

Ale jak to binarne zastosowac do pogrupowanych stringow?

int lewo=0;
int prawo=a-1 //gdzie a to byla liczba oznaczajaca liczbe elementow zbioru
while(lewo<prawo){
int s=(lewo+prawo)/2;
string x=tab[s]// gdzie tab[a] to tablica pogrupowanych juz stringow

i dalej to juz nie wiem co zrobic...

gong911 2011-03-03 17:07:29 UTC #24

Niestety jak przeniose funkcje do while(lewo

...
int n;
    scanf("%d",&n);
    while(n--){char sss[399];
               scanf("%s",&sss);
               int lewo=0,prawo=a-1;
               if((strlen(sss)<strlen(tab[lewo]))or(strlen(sss)==strlen(tab[lewo])&&sss<tab[lewo]))
              {printf("%d\n",lewo); continue;}  
               if((strlen(sss)>strlen(tab[prawo]))or(strlen(sss)==strlen(tab[prawo])&&sss>tab[prawo]))
               {printf("%d\n",a); continue;}
               while(lewo<prawo)
               {
                                int s=(lewo+prawo)/2;
                                if(strlen(tab[s])>strlen(sss)) prawo=s;
                                else if(strlen(tab[s])==strlen(sss) && tab[s]>sss) prawo=s;
                                else if(strlen(tab[s])==strlen(sss) && tab[s]<sss) lewo=s+1;
                                else if(strlen(tab[s])<strlen(sss)) lewo=s+1;
                                else if(tab[s]==sss) prawo=s;
                }
                printf("%d\n",lewo);
                }

gong911 2011-03-09 19:12:51 UTC #25

OJ... myslalem juz ze zostane poratowany z tym zadaniem
Bo nadal nie moge jakos zmienic tego wczytywania zmiennej sss z stringa+cin na char+scanf jakies bledne wyniki mi podaje ;/

kokosek_sof1 2011-03-11 20:17:31 UTC #26

Jasne, że nie trzeba, ale tutaj chodzi o nawyk.
Nigdy nie wiesz, kiedy stracisz kilka godzin na debuggowanie, bo będziesz miał za małą tablicę.

Adriansurf_sof 2011-07-09 17:49:44 UTC #27

Dobra, nie wiem jak to się stało ale zamiana cout'a na printfa podziałała, dzięki