Marinada '24

[lang=hr] Fran R. uzgaja svoju farmu mahuna na kojoj se nalazi $200000$ biljaka. Prve dvije su visine $1m$, a svaka iduća je jednaka zbroju visina prethodne dvije. Kako su stabiljke nestabilne, ako je neka biljka veća od $2m$, smanjivat će se za $3m$ dok joj visina ne postane niža od $3m$. Ako Fran na svojoj farmi ima previše mahuna, morat će platiti golem porez. Na sreću, Fran je našao rupu u zakonu i zaključio je da ako je medijan svih biljaka na njegovoj farmi jednak $0$, policija ga neće privesti. Zbog toga želi porezati neke biljke, a jednim rezanjem visina biljke smanjuje se za $1m$. Fran želji maksimizirati svoj profit kod uzgajanja mahuna pa ga zanima koliko minimalno rezanja treba napraviti da bi bio siguran? [/lang] [lang=en] Fran R. grows his green bean farm, which contains $200000$ plants. The first two plants are $1m$ tall, and each subsequent plant's height is the sum of the previous two. Since the stalks are unstable, if any plant grows taller than $2m$, it will be reduced by $3m$ until its height is less than $3m$. If Fran has too many beans on his farm, he will have to pay a massive tax. Luckily, Fran found a loophole in the law and realized that if the median height of all plants on his farm is $0$, the police won’t arrest him. Because of this, he wants to trim some of the plants, and each trimming reduces a plant’s height by $1m$. Fran wants to maximize his profit from growing beans, so he wonders how many minimum trimmings he needs to perform to be safe. [/lang]