Tip of the day: odaberi srednji

[Osvrt na ovosezonske zadatke – 2. dio]

Zadatak Bitcoin sa Županijskog natjecanja 2018., 1. i 2. razred, imao je zadane cijene bitcoina (izražene u eurima) za svaki od N dana. Trebalo je od tih N dana odabrati tri dana, ne nužno uzastopna, u kojima ćemo najprije kupiti bitcoine za 10 eura (1. dan), potom te bitcoine prodati za eure (2. dan) i na kraju opet kupiti bitcoine za eure koje imamo (3. dan), tako da broj dobivenih bitcoina na kraju bude maksimalan. Zbog ograničenja N ≤ 100 000, provjera svih trojki (ili čak dvojki) bila je prespora.

Zadatak se može riješiti na dva načina. Jedan način koristi se u rješenju teže varijante, zadatka Ethereum na istom natjecanju za 3. i 4. razred, u kojemu je trebalo ispisati traženi maksimum za svaki mogući prvi dan. (Autor zadataka je Marin Tomić.)

Jednostavnije rješenje Bitcoina koristi ideju koju sam prvi put vidio u zadatku Berba sa Državnog 2009., a poslije sam je iskoristio za zadatak Audi na JHIO 2017.

Otkrijte sami koji je trik zajednički rješenjima ovih triju zadataka. Hint se nalazi u naslovu ovog posta. Ako netko zna još neki zadatak čije rješenje koristi sličnu foru, neka napiše u komentarima.

Update — još jedan zadatak na ovu foru: Three displays.

Jedna misao o “Tip of the day: odaberi srednji

  1. Usporedba rješenosti Audi s JHIO-a i zadatka Bitcoin/Ethereum (oni koji su bili na oba natjecanja; prvo piše broj bodova za Audi, po tom broju je sortirano, zatim bodovi za BTC/ETH):

    Jovanović, 100, 40(ETH)
    Fistrić, 100, 40(ETH)
    Markovinović, 100, 40(BTC)
    Nežmah, 100, 40(BTC)
    Bošnjak, 100, 12(BTC)
    Kocijan, 90, 40(BTC)
    Vidas, 80, 40(ETH)
    Nuić, 80, 40(ETH)
    Jambrešić, 70, 16(BTC)
    Meštrović, 50, 40(ETH)
    Brnetić, 50, 40(BTC)
    Rohak, 40, 36(BTC)
    Žužić, 30, 36(ETH)
    Cifrek, 30, 40(BTC)
    Čengić, 20, 32(BTC)
    Verović, 0, 40(ETH)
    Kliska, nije submito, 40(BTC)

    Sviđa mi se

Komentiraj

Popunite niže tražene podatke ili kliknite na neku od ikona za prijavu:

WordPress.com Logo

Ovaj komentar pišete koristeći vaš WordPress.com račun. Odjava /  Izmijeni )

Google+ photo

Ovaj komentar pišete koristeći vaš Google+ račun. Odjava /  Izmijeni )

Twitter picture

Ovaj komentar pišete koristeći vaš Twitter račun. Odjava /  Izmijeni )

Facebook slika

Ovaj komentar pišete koristeći vaš Facebook račun. Odjava /  Izmijeni )

Spajanje na %s