O NOUA PROBLEMA DE CONCURS OLIMPIADA MUNICIPALA DE INFORMATICA, IASI 2019 V-am promis într-un articol mai vechi ca vom prezenta pe acest blog câteva problema interesante. Astăzi ne-am propus sa va supunem atentiei o problemă pe care o găsiți și pe site www.pbinfo.ro : problema PLANTA cu numărul 2908. Ghiță a primit de ziua lui o plantă exotică, ce se comportă foarte ciudat. El a măsurat-o când a primit-o și a constatat că are D cm, apoi a văzut că se dezvoltă într-un ritm special: •În prima zi, planta crește cu A cm •În a doua zi, descrește cu B cm •În a treia zi, iar crește cu A cm •În a patra zi, descrește din nou cu B cm •etc. Pe scurt, în zilele cu număr de ordine impar crește cu A cm, iar în cele cu număr de ordine par, descrește cu B cm. Cerința Știind D, înalțimea inițiala a plantei și valorile A și B cu care aceasta crește, respectiv descrește, să se afla ce înălțime va avea planta lui Ghiță la finalul celei de-a N -a zile. Date de intrare Pe prima linie a fișierului planta.in se vor afla patru numere naturale D A B N în aceasta ordine, separate prin câte un spațiu, cu semnificațiile din enunț. Date de ieșire Pe prima linie a fișierului planta.out se va afla un număr H, semnificând înălțimea finală a plantei în cm la finalul celei de-a N -a zile. Restricții și precizări • 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 garantează că pentru toate testele valorile se încadrează în tipul int.
Transcript
O NOUA PROBLEMA DE CONCURSOLIMPIADA MUNICIPALA DE INFORMATICA, IASI 2019
V-am promis într-un articol mai vechi ca vom prezenta pe acest blog câteva problema interesante. Astăzi ne-am propus sa va supunem atentiei o problemă pe care o găsiți și pe site www.pbinfo.ro: problema PLANTA cu numărul 2908.
Ghiță a primit de ziua lui o plantă exotică, ce se comportă foarte ciudat. El a măsurat-o când a primit-o și a constatat că are D cm, apoi a văzut că se dezvoltă într-un ritm special:
•În prima zi, planta crește cu A cm
•În a doua zi, descrește cu B cm
•În a treia zi, iar crește cu A cm
•În a patra zi, descrește din nou cu B cm
•etc.
Pe scurt, în zilele cu număr de ordine impar crește cu A cm, iar în cele cu număr de ordine par, descrește cu B cm.
Cerința
Știind D, înalțimea inițiala a plantei și valorile A și B cu care aceasta crește, respectiv descrește, săse afla ce înălțime va avea planta lui Ghiță la finalul celei de-a N -a zile.
Date de intrare
Pe prima linie a fișierului planta.in se vor afla patru numere naturale D A B N în aceasta ordine, separate prin câte un spațiu, cu semnificațiile din enunț.
Date de ieșire
Pe prima linie a fișierului planta.out se va afla un număr H, semnificând înălțimea finală a plantei în cm la finalul celei de-a N -a zile.
Restricții și precizări
•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 garantează că pentru toate testele valorile se încadrează în tipul int.
Pentru rezolvarea acestei probleme va vom prezenta 3 algoritmi corecti de rezolvare, dar care după o analiza matematica a problemei pot fi imbunatatiti în mod considerabil.
Dacă citim textul problemei, primul algoritm la care ne gândim în momentul în care vedem ca ni se cere ce înălțime are planta la finalul celei de a N-a zile este un algoritm în care folosim structura repetitiva cu un numar bine determinat de pași, structura FOR.
Observam de asemenea ca în zilele cu numar de ordine impar planta crește cu A cm iar în zilele cu numar de ordine impar, înălțimea ei scade cu B cm.
Algoritmul s-ar putea scrie așa:
Dacă trimitem însă aceasta soluție pe site-ul mai sus amintit vom primi doar 55 de puncte,
Erorile care ni se raportează și numărul scăzut de puncte se datorează folosirii structurii FOR care pentru numere mari, 1 ≤ N ≤ 1 000 000 000 determina depasirea timpului de execuție cerut de problema.
Ce concluzie tragem după acest rezultat modest? Trebuie sa eliminam aceasta bucla repetitiva în care am calculat înălțimea plantei noastre.
Revenim la specificitatea procesului de creștere / descrestere al plantei: în zilele cu numar de ordineimpar planta crește cu A cm iar în zilele cu numar de ordine impar, înălțimea ei scade cu B cm.
Altfel spus, după 2 zile planta a crescut cu A-B, deoarece A>=B este specificat în problema.În total, creșterea plantei va fi de (N/2) * (A-B) dacă N este par deoarece vor fi N/2 grupe de câte 2 zile în care procesul are loc la fel.
Dacă N este impar vom mai avea la final, în a N-a zi o creștere cu A cm deci înălțimea plantei se va modifica cu (n/2) * (A – B) + A.
Am evitat astfel bucla repetitiva și am scris următorul algoritm:
Dacă trimitem spre evaluare automata acest cod, vom obtine 100 puncte.
Mai putem face o ultima observație: operatiile care trebuie făcute pe cele doua ramuri ale stucturii ifpot fi condensate într-o singura operatie în care dacă N este par sa mai adaugam un A la lungimea deja calculata a plantei după N-1 zile, adică la (N/2) * (A-B)
Am obținut o soluție tot de 100 de puncte, dar este o solutie mai eficienta decât cele anterioare, fără decizii și fără repetitii.
Referinte[1] Lucia Negreanu-Maior, Conducător stiintific Lect. Univ. Clara Ionescu, Lucrare de diplomă INTRODUCERE ÎN PROGRAMARE. SORTARE ŞI CĂUTARE, Universitatea „Babes-Bolyai”, Cluj Napoca, Facultatea de Matematicași Informatica 2002
[2] LAN It Academy – Academie de programare, pagina de Facebook accesibilă online la adresa https://www.facebook.com/lanitacademy
[3] LAN It Academy, blogul Academiei de programare accesibil online la adresa https://academyitlan.wordpress.com
[4] Site pbinfo accesibil online la adresa https://www.pbinfo.ro/
