Articolele lui Negreanu-Maior Lucia (lanteamlucia)

OLIMPIADA MUNICIPALA DE INFORMATICA, IASI 2019

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:

#include <fstream>

using namespace std;
ifstream cin(“planta.in”);
ofstream cout(“planta.out”);

int main() { int d, a, b, n, i;

cin >> d >> a >> b >> n; for (i = 1; i <= n;i++){ if (i % 2){d +=a;} else {d-= b;} } cout << d; cin.close(); cout.close(); return 0; }

Daca trimitem insa aceasta solutie pe site 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:

#include <fstream>

using namespace std;
ifstream cin(“planta.in”);
ofstream cout(“planta.out”);

int main() { int d, a, b, n; cin >> d >> a >> b >> n; if(n%2){ cout << d+(n/2)*(a-b)+a; }else{ cout << d+(n/2)*(a-b); }

cin.close(); cout.close(); return 0; }

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

#include <fstream>

using namespace std;
ifstream cin(“planta.in”);
ofstream cout(“planta.out”);

int main() { int d, a, b, n; cin >> d >> a >> b >> n; cout << d+(n/2)*(a-b)+a*(n%2); cin.close(); cout.close(); return 0;
}

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.
Mai multe articole gasiti pe blogul nostru https://academyitlan.wordpress.com
Va multumim ca ne urmariti!

In randurile urmatoare am dori sa va aratam niste solutii surprinzatoare la probleme care au fost date la concursuri (Olimpiada municipala de informatica Iasi 2013) – si nu numai.

O prima problema gasita pe pbinfo ar fi: problema XYZ (#2096)
Un număr natural se numeşte “număr xyz” dacă are x cifre, prima cifră a sa este egală cu y şi următoarele cifre sunt egale cu z. Scrieţi un program care să determine “numărul xyz” pentru x, y, z numere naturale date.
Daca se citeste atent textul se poate vedea ca numarul final care se doreste a fi format, nu va avea 3 cifre ci x cifre unde 1 <= x <= 9.
De exemplu (dam exemplul din problema), daca x = 5 numarul nostru va trebui sa aiba 5 cifre, daca y = 4 numarul nostru va avea prima cifra 4 urmata de restul 4 cifre de 3 atat cat arata z citit. De ce numarul trebuie sa contina 4 valori de z? Pentru ca din cele x cifre pe care trebuie sa le aiba numarul in total, y a ocupat o prima pozitie a numarului deci au ramas x-1 pozitii de ocupat pentru cifra z. Numarul va fi 43333.
Problema de pe site se cere rezolvata folosind fisiere – nu insistam pe acest aspect. Vrem sa evidentiem simplitatea algoritmului:
#include <fstream>

using namespace std;
ifstream cin(“xyz.in”);
ofstream cout(“xyz.out”);

int x,y,z,i;

int main() { cin>>x>>y>>z; cout<<y; for (i = 1; i < x; i ++) cout<<z; cin.close(); cout.close(); return 0;
}
Nu cred ca se poate ceva mai simplu de atat. Nu se formeaza efectiv un numar prin inmultirea cu factorul 10 a cifrelor si deplasarea lor spre stanga. Este o altfel de rezolvare, mai transparenta si mai fluida. Cealalta solutie va lasam sa o implementati singuri.

Daca v-a placut articolul nostru va promitem ca vor mai fi si altele similare!

https://academyitlan.wordpress.com/2018/10/30/despre-o-problema-frumoasa-de-concurs/