[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.