O NOUA PROBLEMA DE CONCURS


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
A B N
in aceasta ordine, separate prin cate un spatiu, cu semnificatiile din enunt.

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!

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare /  Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare /  Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare /  Schimbă )

Conectare la %s

Acest site folosește Akismet pentru a reduce spamul. Află cum sunt procesate datele comentariilor tale.