OLIMPIADA MUNICIPALA DE INFORMATICA, IASI 2019
V-am promis intr-un articol mai vechi ca vom prezenta pe acest blog cateva problema interesante. Astazi ne-am propus sa va supunem atentiei o problema pe care o gasiti si pe site www.pbinfo.ro: problema PLANTA cu numărul 2908.
Ghita a primit de ziua lui o planta exotica, ce se comporta foarte ciudat. El a masurat-o cand a primit-o si a constatat ca are D cm, apoi a vazut ca se dezvolta intr-un ritm special:
In prima zi, planta creste cu A cm
In a doua zi, descreste cu B cm
In a treia zi, iar creste cu A cm
In a patra zi, descreste din nou cu B cm etc.
Pe scurt, in zilele cu numar de ordine impar creste cu A cm, iar in cele cu numar de ordine par, descreste cu B cm.
Cerinta
Știind D, inaltimea initiala a plantei si valorile A și B cu care aceasta creste, respectiv descreste, sa se afle ce inaltime va avea planta lui Ghita la finalul celei de-a N -a zile.
Date de intrare
Pe prima linie a fisierului planta.in se vor afla patru numere naturale D in aceasta ordine, separate prin cate un spatiu, cu semnificatiile din enunt.
A B N
Date de ieșire
Pe prima linie a fisierului planta.out se va afla un numar H, semnificand inaltimea finala a plantei in cm la finalul celei de-a N -a zile.
Restrictii si precizari
0 ≤ D ≤ 100
1 ≤ B ≤ A ≤ 1 000 000
1 ≤ N ≤ 1 000 000 000
Pentru 50% dintre teste, 1 ≤ N ≤ 1 000 000
Se garanteaza ca pentru toate testele valorile se incadrează in tipul int.
Pentru rezolvarea acestei probleme va vom prezenta 3 algoritmi corecti de rezolvare, dar care dupa o analiza matematica a problemei pot fi imbunatatiti in mod considerabil.
Daca citim textul problemei, primul algoritm la care ne gandim in momentul in care vedem ca ni se cere ce inaltime are planta la finalul celei de a N-a zile este un algoritm in care folosim structura repetitiva cu un numar bine determinat de pasi, structura FOR.
Observam de asemenea ca in zilele cu numar de ordine impar planta creste cu A cm iar in zilele cu numar de ordine impar, inaltimea ei scade cu B cm.
Algoritmul s-ar putea scrie asa:
Daca trimitem insa aceasta solutie pe site-ul mai sus amintit vom primi doar 55 de puncte.
Erorile care ni se raporteaza si numarul scazut de puncte se datoreaza folosirii structurii FOR care pentru numere mari, 1 ≤ N ≤ 1 000 000 000 determina depasirea timpului de executie cerut de problema.
Ce concluzie tragem dupa acest rezultat modest? Trebuie sa eliminam aceasta bucla repetitiva in care am calculat inaltimea plantei noastre.
Revenim la specificitatea procesului de crestere / descrestere al plantei: in zilele cu numar de ordine impar planta creste cu A cm iar in zilele cu numar de ordine impar, inaltimea ei scade cu B cm.
Altfel spus, dupa 2 zile planta a crescut cu A-B, deoarece A>=B este specificat în problema.
In total, cresterea plantei va fi de (N/2) * (A-B) daca N este par deoarece vor fi N/2 grupe de cate 2 zile in care procesul are loc la fel.
Daca N este impar vom mai avea la final, in a N-a zi o crestere cu A cm deci inaltimea plantei se va modifica cu (n/2) * (A – B) + A.
Am evitat astfel bucla repetitiva si am scris urmatorul algoritm:
Daca trimitem spre evaluare automata acest cod, vom obtine 100 puncte.
Mai putem face o ultima observație: operatiile care trebuie facute pe cele doua ramuri ale stucturii if pot fi condensate intr-o singura operatie in care daca N este par trebuie sa mai adaugam un A la lungimea deja calculata a plantei dupa N-1 zile, adica la (N/2) * (A-B).
Am obținut o soluție tot de 100 de puncte, dar este o solutiei mai eficienta decat cele anterioare, fara decizii si fara repetitii.
Asteptam intrebarile si sugestiile voastre in legatura cu acest articol. Va multumim ca ne urmariti!
LAN IT Academy 