Resenja zadataka sa okruznih takmicenja predhodnih godina

Pozdrav svima,

Da li neko ima resenja zadataka sa sledecih takmicenja
ili neke smernice za algoritme i koja znanja zahtevaju za bilo koji od zadataka?
Svaki hint mi je od znacaja, kao i korisni linkovi vezani za njihovo resavanje ili druge tehnike potrebne za okruzno takmicenje.
Dakle:
okruznog 2015 B1,B2,B3
okruznog 2016 B1

Link ka zadacima:
https://petlja.org/biblioteka/r/Lectures/2015-okruzno-ss
https://petlja.org/biblioteka/r/Problems/2015-okruzno-ss-davis-zona

Davis Zona

Front
Vojnici su nam već dati sortirani po x koordinati, ali mi ćemo ih ponovo sortirati tako da ukoliko dva vojnika imaju iste x koordinate, gledamo y koordinatu. Možemo primetiti da za n > 1, prvi vojnik nikad neće biti u frontu, dok će poslednji uvek biti na frontu. Sada je potrebno sufiksno pronaći minimume za svaku y koordinatu od 0 do n-2 (poÅ”to znamo da je vojnik na poziciji n-1 sigurno u frontu). Konačno, znamo da će svaki vojnik sem poslednjeg imati vojnika koji ima veću ili jednaku x koordinatu. Tako da je potrebno samo proveriti da li je y koordinata i-tog vojnika veća od maksimalne y koordinate u intervalu od i+1 do n-1. Ukoliko jeste, znamo da je i-ti vojnik u frontu.
Moje reŔenje

Å ifra
Krećemo od prvog niza, koji će biti samo prvi element M puta. Sada, dok je k > 1, delimo ga sa n, a ostatak njihovog deljenja nam govori koji je to element po redu u originalnom nizu (ovo je moguće poÅ”to je niz sortiran).
Moje reŔenje

Sudari
Isto kao i kod Davis Zone, potrebno je samo pažljivo implementirati.
ReŔenje

2 Likes

Hvala ti Milose na tome sto si jasno objasnio kako problemi trebaju da se rese i pokazao to u kodu, stvarno mi puno pomaze za pripremu i uporedjivanje sa mojim pokusajima. A siguran sam da ce dobro doci ostalima :grin::grin::grin:
Veliki pozdrav!

1 Like