Zadatak dana: Easter eggs ili Čudnovate permutacije uskršnjih jaja

Izvor: https://www.nsa.gov/News-Features/News-Stories/Article-View/Article/1627299/september-2015-puzzle-periodical/

Alice has a dozen cartons, arranged in a 3×4 grid, which for convenience we have labeled A through L:

A B C D
E F G H
I J K L

She has randomly chosen two of the cartons and hidden an Easter egg inside each of them, leaving the remaining ten cartons empty. She gives the dozen cartons to Bob, who opens them in the order A, B, C, D, E, F, G, H, I, J, K, L until he finds one of the Easter eggs, whereupon he stops. The number of cartons that he opens is his score. Alice then reseals the cartons, keeping the eggs where they are, and presents the cartons to Chris, who opens the cartons in the order A, E, I, B, F, J, C, G, K, D, H, L, again stopping as soon as one of the Easter eggs is found, and scoring the number of opened cartons. Whoever scores lower wins the game; if they score the same then it’s a tie.

For example, suppose Alice hides the Easter eggs in cartons H and K.
Then Bob will stop after reaching the egg in carton H and will score 8, while Chris will stop after reaching the egg in carton K and will score 9. So Bob wins in this case.

Who is more likely to win this game, Bob or Chris? Or are they equally likely to win?

Pokušajte riješiti zadatak, a tek onda čitajte dalje.

Rješenje možete naći na gornjoj poveznici, ili malo ljepše napisano na http://datagenetics.com/blog/march12017/index.html.

Rezultat je vrlo neobičan jer se protivi mojoj, a možda i vašoj intuiciji, koja kaže da poredak ne bi smio igrati nikakvu ulogu. Riječ je o običnim permutacijama; po čemu je ABCDEFGHIJKL bolja (i uopće drugačija) od AEIBFJCGKDHL? U čemu je fora?

Ovaj zadatak vidio sam kada ga je shareao docent Vedran Čačić s PMF-a na (bivšoj) društvenoj mreži Google+, gdje je dao i dobar uvid u odgovor na ovu neobičnost, te postavio dodatni zadatak koji će osobito informatičarima biti zanimljiv:

Of course, it’s completely obvious that there are no absolutely better/worse strategies, as long as you stick to bijections between [1..12] and [A..L] (after all, that’s why S12 is called the symmetry group), so there must be some intransitivity in the “order” of strategies. Can you find a permutation that beats Bob’s ABCDEFGHIJKL, yet is beaten by Charlie’s AEIBFJCGKDHL? 🙂

Zadatak dana: kazaljke sata – ili Kad se sve poklopi

Sjećate li se prije godinu dana ugašene društvene mreže Google+? Ondje je nekad u 2017. godini Veky (docent Vedran Čačić s PMF-a) podijelio sljedeći zadatak:
 
Na analognom satu na kojem se sve tri (sat, minuta, sekunda) kazaljke pomiču kontinuirano, hoće li se ikad dogoditi da se sve tri nalaze unutar kuta od 1°?

Traži se vrijeme strogo između 0:0:1 i 11:59:59.

Kada se Google+ gasio, preuzeo sam arhivu svoje aktivnosti i tako došao i do tog zadatka i svojega rješenja koje sam bio napisao u komentarima. Evo tih komentara:
 
[Adrian]
3:16:16.3 i 8:43:43.7, dobiveno simulacijom po kutnim sekundama u Pythonu.
 
[Veky]
Hm, zanimljivo. 🙂 Ali nisam baš mislio na simulaciju, bar ne tako grubu. Probaj odgovoriti jesu li ikad unutar pola stupnja onda. 🙂
 
[Adrian]
1 kutna sekunda = 1/60 kutnih minuta = 1/3600 kutnih stupnjeva, što je vrlo fina simulacija. Poanta je da se može simulirati proizvoljno precizno, s brzinama kazaljki x, 12x i 12*60x.
 
[Veky]
Kad je već tako fina, odgovori na moje pitanje. 😀
 
(Ovdje sam bio zapeo. Programirao sam sve precizniju i precizniju simulaciju, kazaljke su se kretale beskonačno sporo, ali kut je uvijek ispadao mrvicu veći od pola stupnja. Vjerovao sam da je riječ o manjku preciznosti pri računanju realnim brojevima i da pravi kut iznosi točno pola stupnja, ali nisam bio dovoljno siguran da bih išta odgovorio. Sjetio sam se toga nakon više od godine dana pregledavajući history kad je Google+ upozorio da će se ugasiti.)
 
[Adrian]
Da odgovorim na ovo dok se Google+ ne ugasi 🙂 Simulacijom sam dobivao razliku toliko blizu 0.5 stupnjeva (ali ipak veću, nešto tipa 0.500x…) da sam mislio da se u stvarnosti postiže točno 0.5, ali da simulacija nikad ne može dobiti taj egzaktan položaj. Danas sam izguglao matematičko rješenje (manje je pametno nego što sam mislio) i vidio da najmanja razlika iznosi 360/719 = 0.5007 stupnjeva. Znači, simulacija je točno odgovarala na pitanje. Pouka: vjeruj kompjuteru čak i kad se čini da griješi.
 
Matematičko rješenje ostaje tajna – njega ostavljamo čitateljici za vježbu. Ali poruka je jasna.
 
Kao bonus, podijelit ću s vama dva članka o kazaljkama sata, objavljena prije mnogo godina u časopisu Matka. Prvi je članak Vladimira Devidéa iz 2000. godine o vjerojatnostima poklapanja kazaljki, a drugi je moj članak iz 2008. godine o pravilnim prikazima na digitalnom satu. Zanimljivo je da je vjerojatnost popuno različitih stvari u oba članka ispala jednaka – poklopila se. Slučajno ili ne?
 

Dva analogna zadatka

“Matematičar je osoba koja vidi analogiju između teorema, još veći je onaj koji vidi analogiju između dokaza raznih teorema; još je veći onaj koji vidi analogiju između teorija. A možemo zamisliti i onoga, koji vidi analogiju među analogijama.” –– Stefan Banach

Budući da nisam veliki matematičar, ja samo vidim analogiju među informatičkim zadatcima. U ovom slučaju to su zadatak NLO sa subotnjeg HONI natjecanja, te nešto lakši zadatak Vandal s Državnog 2007., čija rješenja dijele sličan trik u načinu razmišljanja.

U zadatku Vandal riječ je o matrici-šahovnici velikih dimenzija u kojoj su pokriveni jedan red, jedan stupac, neka dijagonala u jednom smjeru i neka dijagonala u drugom smjeru. Zadana je samo dimenzija matrice i oznake pokrivenog retka, stupca i dijagonala, a treba izračunati koliko je bijelih, a koliko sivih polja šahovnice barem jednom pokriveno.

Budući da je na ulazu samo pet brojeva, većina nas je to rješavala “matematički”, hrpom formula i ifova. To je u teoriji izvedivo, ali je jako komplicirano i teško izvesti bez greške za sve slučajeve. (Kad počnete crtati slučajeve, što se sa čime siječe ili ne siječe, bit će vam jasnije.) Takvo rješenje radi u konstantnoj složenosti (bez petlje), što je za informatički zadatak rijetkost: zadatak s takvim rješenjem bio bi loš, tj. zapravo matematički. Srećom, u ovom zadatku to nije očekivano rješenje.

Na suprotnom ekstremu nalazi se jednostavno brute-force rješenje koje za svako polje laganim formulama provjerava je li pokriveno. Ono je sporo jer matrica ima N x N polja za N ≤ 107 pa ne stignemo proći po svim poljima.

Na sličnu situaciju nailazimo u zadatku NLO, gdje matricu pokriva nekoliko krugova. U geometriji je formulama moguće izračunati presjek/uniju dvaju krugova, možda čak i triju, no ovdje ih je 100 i osim toga to nisu pravi krugovi nego su diskretizirani na polja. Zato bilo kakvo rješenje čija bi složenost ovisila samo o broju krugova možemo zaboraviti.

S druge strane, mogli bismo za svako polje vrlo jednostavno provjeriti koji krugovi ga pokrivaju i izračunati koliko će na njemu trave narasti – kad to ne bi bilo presporo.

Rješenje se nalazi u sredini, između perspektiva “gledam krugove odjednom” i “gledam svako pojedino polje”. Nemamo vremena proći po poljima (N2), ali imamo vremena proći po redovima (N). Dovoljno je riješiti zadatak zasebno za svaki red matrice. Dakle, promatramo pojedini red, formulama izračunamo na kojim poljima ga sijeku krugovi (to su jedina polja gdje se mijenja stanje) i prolaskom po tim “zanimljivim” poljima usput zaključujemo što je s poljima koje preskačemo.

Ista je ideja u zadatku Vandal. Iako mi je bilo jasno da se zadatak može riješiti samo formulama i ifovima (iako ne znam je li to itko u potpunosti uspio), rečenica koju je Lovro Pužar izgovorio na prezentaciji rješenja bila mi je prosvjetljujuća: “N je do 107 – ako si možete priuštiti for petlju, priuštite si je.” Prođemo po redovima; za svaki red možemo relativno lako izračunati polja u kojima ga sijeku zadani stupac i zadane dijagonale; riječ je o najviše tri zanimljiva polja kojima lako odredimo boju.

Zadatak dana: ABCD

Ovaj zadatak statistički je najpopularnija stvar koju sam ikad napravio, budući da ga je na Spoju riješilo gotovo 2000 korisnika (a pokušalo riješiti vjerojatno još toliko — ukupan broj slanja trenutačno je 11844) iako se ne radi o posve trivijalnom zadatku.

Jedan od uzroka popularnosti zadatka mogla bi biti činjenica da je jedan od prvih po abecedi, pa se pojavljuje kao prvi na listi riješenih zadataka mnogih korisnika (kao npr. ovdje). Argument u prilog toj uzročnoj vezi je i činjenica da je “abecedno sličan” zadatak ABCDEF, čiji je autor naša legenda Luka Kalinovčić, također jako (čak i dva-tri puta više) popularan na istoj stranici.

No svakako u prilog zadatku ide i ljepuškastost njegovog rješenja — kad god otvorim stranicu zadatka, vidim bar jedan komentar koji kaže da je zadatak predivan. S time biste se mogli složiti ako volite najveći mogući adhocness level, zadatke koji se rješavaju “na prevaru”. Dovoljno je spomenuti da je zadatak nastao dok sam vježbao za matematička natjecanja tumarajući po bespućima tadašnjeg MathLinksa (današnjeg AoPS-a) i vidio zadatak na nekom starom, možda poljskom natjecanju, gdje je trebalo dokazati postojanje rješenja.

Zadatak sam najprije bio složio za ZRS-ovu Informatijadu (za mlađu i stariju podskupinu), gdje mi je tadašnji natjecatelj Zvonimir Medić ukazao na to da je uspješno provukao neko greedy/heuristično rješenje koje ne bi trebalo raditi na određenim test podatcima, ali ga nisam imao na umu prilikom izrade zadatka. Poslije mi je poslao nekoliko test podataka koji ruše njegovo i nekoliko sličnih rješenja. Stoga mu pripada dio zasluge za kvalitetu zadatka (tj. njegovih testova) na Spoju, kao i za frustraciju određenog broja korisnika koji ne mogu progurati svoje heuristike.

Zadatak dana: GTA

Izvor: Izborne pripreme 2014., prvi izborni ispit

Ovaj zadatak ima zanimljivu “backstage” priču koju sam odlučio ovdje podijeliti. Na početku napomena — post je relativno dug, a ni zadatak nije jednostavan, pa ako nemate neki miran chunk slobodnog vremena, ostavite ovo za poslije.

Inspiracija za zadatak

Autor zadatka je moja malenkost. Ideja je potekla od znatno lakšeg zadatka iz knjige Zgode i mozgalice družbe Matkači autora P. Mladinića, izvorno objavljenog na poleđini časopisa Matka. Bio je zadan u obliku stripa, a ukratko bi glasio otprilike ovako:

Jurica je izmislio novi jezik čije su riječi sastavljene od slova A, B i C. Različite riječi mogu označavati isti pojam: to su sinonimi. Vrijedi: ako dvama sinonimima dopišemo s iste strane ista slova, ponovno dobivamo dva sinonima. Poznati su sljedeći parovi sinonima: AB i C, BC i A, te CA i B. Riječi AB i BA nisu sinonimi. Koliko pojmova ima Juričin jezik?

Pokušajte najprije sami otkriti sličnost ovoga zadatka i zadatka GTA, ili čak riješiti ovaj zadatak, a onda čitajte dalje.

Sljedeća je opservacija ključna za rješenje zadatka iz Matke: ako u nekoj riječi zamijenimo blok AB slovom C ili obrnuto (te analogno za zamjene BC – A i CA – B), dobivamo njezin sinonim. To vrijedi zato što, počevši od sinonima AB i C, dodavanjem istih slova slijeva i zdesna ponovno dobivamo sinonime, a upravo tako mogu nastati dvije riječi koje veže spomenuta zamjena blokova AB i C.

Tu vidimo sličnost ovoga zadatka sa zadatkom GTA. Kada bi u zadatku GTA molekule bile sastavljene od znakova A, B i C, kada bi tri dozvoljene mutacije bile AB – C, BC – A i CA – B te kada bismo molekule koje dobivamo jednu iz druge zvali sinonimima, zadatak bi bio praktički isti: pitanje “je li moguće jednu molekulu dobiti iz druge” svodi se na “jesu li ove riječi sinonimi, tj. odgovaraju li istome pojmu”.

Koliko je pojmova?

Igrajući se zadatkom iz Matke, možemo dobiti da je AA = ABC = CC i AA = BCA = BB, dakle: AA = BB = CC. Čini se da zasad imamo pojmove A, B, C, AA, AC, BA i CB. Nadalje, od svih riječi s tri slova samo je ACB novi pojam. Ostale su riječi sinonimi ovih osam pojmova. Primjerice, ACB = BCCB = BAAB = BAC, BAA = BCC = AC. Nadalje, lako se pokaže da je svaka riječ od četiri slova sinonim neke kraće riječi. To znači da među četveroslovnim riječima nema novih pojmova, a isto vrijedi i za riječi s još više slova jer ih lako “kratimo” zamjenom bilo kojeg četveroslovnog bloka njegovim kraćim sinonimom. Ukratko, Juričin jezik ima samo 8 pojmova.

Zadatak GTA nastao je iz sljedećeg pitanja: što ako se Juričin jezik proširi na četiri slova — A, B, C, D — sa sličnim pravilima? “Slična pravila” mogla su biti A – BC, B – CD, C – DA, D – AB (slovo se zamjenjuje blokom od “sljedeća dva” slova), ili pak A – DB, B – AC, C – BD, D – CA (slovo se zamjenjuje blokom od “okolnih” slova).

Za svaku od ovih varijanti napisao sam program koji broji pojmove jezika. Preciznije, za svaku riječ kraću od 8 znakova tražio sam njezine sinonime širenjem na njoj “susjedne” riječi (one koje nastaju zamjenom, tj. mutacijom), s pomoću DFS ili BFS algoritma. U tom kontekstu, “pojam” odgovara komponenti povezanosti, tj. sve riječi koje je moguće dosegnuti širenjem iz neke riječi čine isti pojam. Otkrivši malen broj pojmova za prvu varijantu (ne sjećam se koliko — isprobajte pa otkrijte!) i 24 pojma za drugu varijantu, odlučio sam se za drugu.

Primijetite da je lakše baratati sa slovima A, B, C i D, što ćemo i u nastavku teksta činiti. Slova A, C, G, T odabrana su u kasnijoj fazi izrade zadatka, kad sam uočio da su četiri slova i njihove zamjene zgodna podloga za priču o DNK i mutacijama.

Varijante zadatka i njegovog rješenja

Zadatak je isprva glasio: za dvije zadane (velike) riječi, je li moguće dobiti jednu iz druge? Očekivano rješenje bilo je sljedeće:

  1. napravimo flood-fill (širenje) za male duljine riječi da otkrijemo pojmove, tj. komponente povezanosti,
  2. odatle uočimo da se svaka riječ od 5 slova može skratiti na najviše 4 slova,
  3. kratimo ulazne riječi mijenjajući njihove peteroslovne blokove unaprijed pronađenim pokratama,
  4. na koncu za dobivene dvije kratke riječi pogledamo jesu li u istoj komponenti.

Luki Kalinovčiću, kolegi u izradi zadataka, nije trebalo računalo da uoči mogućnost kraćenja velikih riječi: on je “na papiru”, koristeći dozvoljene zamjene, dokazao da se svaka riječ može skratiti na najviše 6 znakova, uz komentar da bi na natjecanju uz pomoć računala tražio najkraću duljinu takvu da se bilo koja riječ te duljine može skratiti.

Luka je predložio da se ulazni podatak sastoji od N riječi (a ne samo dvije) te da za svaki par tih riječi treba ispisati može li se jedna dobiti iz druge. Prijedlog je prošao, a motiv je bio sljedeći: budući da je rješenje koje promatra svake dvije od N riječi (bez prethodnoga kraćenja) presporo, natjecatelju se sugerira ideja da se najprije svaka riječ skrati i/ili svrsta u pripadnu klasu.

Luka je predložio i da zadatak bude tipa output-only (tj. da natjecatelji dobiju sve ulazne primjere i šalju samo odgovarajuće izlaze), vjerojatno u želji da motivira natjecatelje da kodiraju širenje za manje primjere i tako uoče rješenje. Goran Žužić, još jedan od tadašnjih autora za HIO/izborne, rekao je da je zadatak “u duši output-only”, ali da je još bolji kao standardni zadatak. Nisam se odlučio za output-only varijantu jer se njome gubi efekt iz prethodnog odlomka: teže bi bilo zaključiti da ne valja odmah gledati parove riječi jer bi vremensko (ne)ograničenje to dopustilo. Natjecatelj Dominik Gleich nakon natjecanja je komentirao da je odluka bila dobra: output-only varijanta možda bi pogrešno sugerirala da nema egzaktnog rješenja koje unutar sekunde rješava bilo koji primjer.

Motivaciju da naprave širenje za male primjere natjecatelji su imali u sekciji Bodovanje koja je opisivala čak šest malih primjera (s duljinama riječi od 2 do 6) koji su činili 60% bodova. Ipak, samo je Ivan Lazarić riješio te primjere. Zadatak se pokazao teškim: nitko ga nije riješio.

Je li rješenje točno?

Zanimljiva je činjenica da za vrijeme natjecanja nismo imali egzaktan dokaz točnosti rješenja.

Vjerojatno se pitate: što uopće treba dokazivati? Najprije primijetite da je drugi primjer iz teksta zadatka rješiv samo ako dopustimo širenje riječi na barem 8 slova. Jedini način da skratimo molekulu CGTAC jest da je najprije produljimo na 8 slova, a tek onda kratimo. Ako širenje ograničimo samo na riječi duljine do 7, dobit ćemo da su molekule C i CGTAC nepovezane, tj. da se nalaze u različitim komponentama. Nameće se sljedeće pitanje: kako znamo da je širenje do duljine 8 dovoljno da se spoje sve komponente koje se uopće mogu spojiti? Je li stvarni broj povezanih komponenti možda manji od 24? Kako znamo da npr. riječ A nije moguće dobiti iz riječi C? Što ako jedini “put” između njih ide po riječima od stotinjak slova pa ga širenjem po riječima duljine do desetak slova nije moguće otkriti?

Takve stvari obično se (npr. na matematičkim natjecanjima) dokazuju pronalaženjem invarijante. U našem slučaju trebalo bi svakoj riječi po nekom pravilu pridružiti matematički objekt (broj, niz ili nešto slično), tako da on ostaje isti prilikom mutacije riječi. Time će svim riječima iste komponente biti pridružen isti objekt. Ako su riječima A i B pridruženi različit objekti, jasno je da ne postoji put koji ih povezuje.

Na primjer, nije teško dokazati da postoje barem 3 različite komponente: ako slova A, B, C, D zamijenimo brojevima 1, 2, 1, 2, onda se zbroj slova u riječi, modulo 3, ne mijenja prilikom mutacije. To npr. dokazuje da od A nije moguće doći do B ili D, ali ne govori ništa npr. o tome postoji li put od A do C.

Na prezentaciji rješenja rekao sam da je ono “empirijski dokazano” jer sam uspio, uz napor, provjeriti da broj komponenti ostaje 24 i kada dopustimo širenje na riječi duljine do 12. Jer intuitivno je posve prihvatljivo da, ako između dviju riječi od 4 slova (a svaka komponenta sadrži takvu riječ) ne postoji put koji riječ smije širiti do duljine 12, onda između njih uopće ne postoji put.

Pitanje o tome je li moguće doći iz riječi A u riječi B, C ili D postavio sam na međunarodnom matematičkom forumu AoPS. Pet dana nakon natjecanja, jedan forumaš dokazao je da A, B, C i D pripadaju različitim komponentama, pronašavši invarijantu koja dokazuje da postoji barem 12 različitih komponenti, uz zahvalno objašnjenje svog načina razmišljanja. Ukratko, svakom slovu pridružio je permutaciju reda 4, a svakoj riječi kompoziciju permutacija njezinih slova.

A sljedećega dana — gotovo tjedan dana nakon natjecanja — rješenje je konačno bilo dokazano: Ante Đerek, inače voditelj izrade zadataka, uz pomoć računala pronašao je invarijantu koja daje 24 komponente, također permutacijsku. Možete je vidjeti u opisu službenog rješenja na stranicama HSIN-a.

Zadatak dana: kineski poštar

Na Chinese postman problem prvi put sam naletio na jednom IBT-u gdje je postavljena verzija tog problema koja je dopuštala rješenje u O(2N · M) koje sam tada smislio i oduševio se tim rješenjem.

Iako je problem rješiv i u O(N3) kao što je objašnjeno na Wikipediji (to rješenje trebate implementirati ako želite naučiti weighted matching), meni se ovo prvo rješenje daleko više sviđa jer je lijepo/neobično i zahtijeva manje znanja. Napisao sam ga ovdje ispod, bijelom bojom (SPOILER!).

Ako graf ima Eulerov ciklus (zatvoreni put koji točno jednom prolazi svakim bridom), on je optimalno rješenje. Inače je potrebno duplicirati neke bridove sa što manjom ukupnom težinom (to su bridovi kojima ćemo proći dvaput) tako da rezultirajući multigraf ima Eulerov ciklus, a to će biti onda kada svaki vrh bude imao paran stupanj. Promatrajmo bitmasku parnosti stupnjeva svih vrhova, za koju želimo da na kraju bude 000…00. Dupliciranje nekog brida mijenja parnosti njegovih vrhova pa dobivamo neku drugu bitmasku. Rješenje je, dakle, Dijkstrinim algoritmom naći najkraći put od početne bitmaske do nul-maske u novom grafu čiji su vrhovi bitmaske — njih je najviše 2N, što je dovoljno malo za N ≤ 15.

Ljepota rješenja je u tome što se problem na grafu rješava konstrukcijom sasvim novoga grafa.

Zadatak dana: Cow School

Postoji trik koji se ponekad javlja da bismo ubrzali rješenja optimizacijskih (min/max) zadataka. Riječ je o transformaciji u geometrijsku domenu gdje je lakše vizualizirati stvari, skužiti što treba tražiti i tako smanjiti složenost. Taj trik ljudi ponekad zovu “dinamika s pravcima” jer se često javlja u ubrzanju prijelaza dinamike. Mislim da se koristi i naziv envelope.

Ovdje je taj trik ugrađen u ne-dinamički zadatak, za koji je profesor Brian Dean (USA Computing Olympiad) još prije desetak godina ispričao (snimio) rješenje na pametnoj ploči i tako popularizirao ovaj trik. Autori zadatka su dvije legende natjecateljskog programiranja, Bruce Merry i Richard Peng.

Zadatak: http://poj.org/problem?id=3266

Analiza: http://contest.usaco.org/TESTDATA/JAN07.schul.htm

Video s rješenjem: http://www.cs.clemson.edu/~bcdean/cowschool.swf — preuzmite i pokrenite (nekim flash playerom ili na http://flashplayer.fullstacks.net/ – povećajte width i height).

Još zadataka na ovu temu slobodno stavljajte u komentarima.

Nepotpuno stablo

[Osvrt na ovosezonske zadatke – 3. dio]

Na Županijskom natjecanju 2018. za 3. i 4. razred, zadatak Poduzeće autora Dominika Gleicha bio je najzanimljiviji. Pogotovo zato što naše rješenje ima bug, tj. postoje slučajevi u kojima ono daje pogrešan rezultat, što smo uočili tek nakon natjecanja. Srećom, takvi slučajevi nisu se pojavili u test podatcima, tj. zadatak je ispravno evaluiran.

Vrijeme je da zadatak riješimo kako treba: http://www.spoj.com/problems/PODUZECE/

Ovdje su dodani test podatci koji ruše rješenje objavljeno na portalu, kao i neka natjecateljska rješenja koja su na natjecanju dobila sve bodove. Potpuno točna rješenja (koja prolaze i na novim test podatcima) na natjecanju su imali Vilim Lendvaj, Josip Klepec i Lovro Kalinovčić. Svaka čast!

(Greška u službenom rješenju krije se u računanju vrijednosti B_min. Ako ne uspijete riješiti zadatak na spoju, slobodno mi se javite da vam pošaljem primjer koji vam pada.)