Penktas uždavinys - skruzdės

Uždavinys gal ir netaps pačiu geriausiu uždaviniu, bet susimąstyti šiek tiek privertė. Iš pradžių galvojau kad laikas priklausys nuo n^2, buvo mintis apie sqrt(n) bet klydau. O išspręsti pavyko pagalvojus apie tai, kaip vyksta skruzdžių susidūrimas: tarkime viena ateina iš kairės, kita - iš dešinės. jos susitinka taške x. Abidvi akimirksniu apisisuka į kitą pusę ir pajuda priešingomis kryptimis. Rezultatas toks: skruzdės buvo vienodu atstumu nuo taško x, susitiko taške x ir vienodu greičiu tolsta nuo x. Dabar kai ką supaprastinkime: susitikusios skruzdės nepakeičia judėjimo krypties, tiesiog viena kitą perlipa taške x. Rezultatas bus toks pats: skruzdės buvo vienodu atstumu nuo taško x, susitiko taške x ir vienodu greičiu tolsta nuo x. Todėl užuot tarę kad n skruzdžių beprotiškai trankosi viena į kitą ir kiekviena keičia savo judėjimo kryptį, lygiai taip pat galime tarti kad skruzdės tiesiog "praeina" viena pro kitą lyg niekur nieko, esmės tai nekeičia. Taigi mano atsakymas būtų toks: 100sekundžių. Čia tuo atveju jei bent viena skruzdė yra ant atkarpos galo ir eina link kito galo. Ir atsakymas visai nepriklauso nuo skruzdžių skaičiaus. Padariau prielaidą kad skruzdės gali nueiti nuo atkarpos pro abu galus.

Jo, manau 100s, bet funkcija aprašyti nepavyko kažkodėl.. Dingo žinos

Tikrai, pateiktas nuostabus sprendimas. Giedriax pastebėjimas " Todėl užuot tarę kad n skruzdžių beprotiškai trankosi viena į kitą ir kiekviena keičia savo judėjimo kryptį, lygiai taip pat galime tarti kad skruzdės tiesiog "praeina" viena pro kitą lyg niekur nieko, esmės tai nekeičia." yra tiesiog atskleidžiantis visą loginio mąstymo ir esmės įžvelgimo grožį. Tai prilygsta ėjimui su šauktuku šachmatuose.

. Taip sekant, nesunku O(1) algoritmu paskaičiuoti kiekvienos skruzdės kiekvieno susidūrimo laiką ir koordinatę, bei koordinatę kiekvienu laiko momentu t. Pilno medžio sukonstravimas yra O(k-1), kur k - skruzdėlių skaičius. Taip pat nesunku parodyti, kad paskutinis susidūrimas įvyks momentu t=(b-a)/2 taške c=(a+b) tarp viduriniųjų skruzdėlių (jei jų skaičius lyginis), tarp viduriniosios ir jos kairiosios (jei ji pradeda į dešinę), arba tarp viduriniosios ir dešiniosios kaimynės (jei pradeda į kairę).