Lizuca are n flori ornamentale de înălţimi h1, h2, …, hn, exprimate în centimetri. Pentru a uda plantele, Lizuca stabileşte următorul program: în prima zi va alege o plantă pe care o va uda, în a doua zi va alege două plante pe care le va uda, în ziua a treia va alege trei plante pe care le va uda şi aşa mai departe. Dacă o plantă este udată într-o anumită zi, atunci creşte 1 centimetru până la sfârşitul acelei zile, iar dacă nu este udată, rămâne la înălţimea pe care o avea la sfârşitul zilei precedente.
Cerinţa
Scrieţi un program care determină:
a) un număr natural S, exprimat în centimetri, reprezentând suma înălţimilor finale ale tuturor plantelor, dacă Lizuca le-ar uda după procedeul descris, timp de n zile;
Lizuca are n flori ornamentale de înălţimi h1, h2, …, hn, exprimate în centimetri. Pentru a uda plantele, Lizuca stabileşte următorul program: în prima zi va alege o plantă pe care o va uda, în a doua zi va alege două plante pe care le va uda, în ziua a treia va alege trei plante pe care le va uda şi aşa mai departe. Dacă o plantă este udată într-o anumită zi, atunci creşte 1 centimetru până la sfârşitul acelei zile, iar dacă nu este udată, rămâne la înălţimea pe care o avea la sfârşitul zilei precedente.
Cerinţa
Scrieţi un program care determină:
a) un număr natural S, exprimat în centimetri, reprezentând suma înălţimilor finale ale tuturor plantelor, dacă Lizuca le-ar uda după procedeul descris, timp de n zile;
b) un număr natural K, reprezentând numărul maxim de zile în care Lizuca poate uda florile după procedeul descris anterior, astfel ca la sfârşitul celei de a K-a zi, nicio plantă ornamentală să nu atingă înălţimea H.
Date de intrare
Fișierul de intrare flori1.in conține pe prima linie două numere naturale n şi H, separate printr-un spaţiu, având semnificaţia din enunţ. Linia a doua conţine n numere naturale: h1, h2, …, hn, separate prin câte un singur spaţiu, reprezentând înălţimile iniţiale ale plantelor.
Date de ieșire
Fișierul de ieșire flori1.out va conține pe prima linie un număr natural S având semnificaţia descrisă în cerinţa a).
A doua linie va conţine un număr natural K, având semnificaţia descrisă în cerinţa b).
Restricții și precizări
1 ≤ N, H ≤ 1001 ≤ h1, h2, ... hn< H- O plantă poate fi udată o singură dată pe zi.
- Pentru rezolvarea corectă a cerinţei a) se acordă 30 % din punctajul total pentru fiecare test.
- Pentru rezolvarea corectă a cerinţei b) se acordă 70 % din punctajul total pentru fiecare test.
Exemplul 1
flori1.in
3 42 1 1
flori1.out
102
Explicație
Dacă în prima zi se udă planta 3, atunci înălţimile devin: 2 1 2
Dacă în a doua zi se udă plantele 1 şi 2, atunci înălţimile devin: 3 2 2
Procedeul se opreşte aici, deoarece în ziua a treia, ar trebui să se ude toate plantele, iar planta 1 ar ajunge să aibă înălţimea 4
Exemplul 2
flori1.in
4 51 3 2 1
flori1.out
173
Explicație
Dacă în prima zi se udă planta 1, atunci înălţimile devin: 2 3 2 1
Dacă în a doua zi se udă plantele 1 şi 4, atunci înălţimile devin: 3 3 2 2
Dacă în a treia zi se udă plantele 1, 3 şi 4, atunci înălţimile devin: 4 3 3 3.
#include <bits/stdc++.h>
using namespace std;
ifstream cin("flori1.in");
ofstream cout("flori1.out");
int n , k , h , a[101] , sum , ok;
int main()
{
cin >> n >> h;
for(int i = 0 ; i < n ; ++i)
{
cin >> a[i];
sum += a[i];
}
sum += n * (n + 1) / 2;
while(ok == 0)
{
sort(a , a + n);
for(int i = 0; i <= k && ok == 0 ; ++i)
if(a[i] + 1 >= h) ok = 1;
if(ok == 0)
{
for(int i = 0; i <= k ; ++i) a[i]++;
k++;
}
}
cout << sum << '\n' << k;
return 0;
}
