Question

#2084 water trap
Plouă, plouă, plouă…

IT -istul Ghită vă propune următoarea problemă:
pe o platformă sunt montate pe poziții consecutive n bare verticale de lățime 1cm (vezi exemplul). Vom presupune că platforma este mărginită față/spate de ziduri transparente de înălțime infinită. Cantitatea de apă ce poate fi reținută într-o unitate de volum (1cm x 1cm x 1cm) este de 1 mililitru.

Cerința
Determinați cantitatea maximă de apă reținută (exprimată în mililitri).

Date de intrare
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, ce reprezintă înălțimile barelor.

Date de ieșire
Programul va afișa pe ecran numărul W, ce reprezintă cantitatea de apă ce poate fi reținută.

Restricții și precizări
2 ≤ n ≤ 100.000
cele n numere citite vor fi mai mici decât 1.000
Exemple:
Intrare

6
3 0 0 2 0 4
Ieșire

10
12
0 1 0 2 1 0 1 3 2 1 2 1
Ieșire

6
Explicație
Pentru primul exemplu:

//m-am gandit ca portiunea care are apa este det.
//de dif. dintre primul elem si urm cu cond ca ele sa nu depaseasca marimea
//primului element al vectorului

Answer 1

Buna, sa iti fie de folos. Am facut ceva banal. Mai este o metoda pe baza algoritmului lui Monte Carlo si mai este inca o metoda parca cu verificarea vecinilor.

#include <iostream>

using namespace std;

int main()

{

  int *vLBari;

  int **matrix;

 

  //Citeste n

  int n=0;cin>>n;

 

  vLBari = new int[n];

 

  int maxColumnLength = 0;

  //Citire elemente vector lungime coloane

  for(int i = 0; i<n;i++)

  {

       cin >> vLBari[i];

       if(vLBari[i] > maxColumnLength)

           maxColumnLength = vLBari[i];

  }

  matrix = new int*[n];                  //Creare matrice

  for(int i = 0; i < n; i++)

       matrix[i] = new int[maxColumnLength];

       

  for(int j=0;j<n;j++)

       for(int i=maxColumnLength-1;i>=maxColumnLength - vLBari[j];i--)

       {

           matrix[i][j] = 1;

       }

   //Completam matricea astefl incat sa ramana  = 0 doar cantitatea de apa.

   for(int i =0; i<maxColumnLength;i++)

   {

       for(int j =0; j<n && matrix[i][j] != 1;j++)

       {

           if(matrix[i][j] == 0)

               matrix[i][j] = 2;

       }

       for(int j =n-1; j>=0  && matrix[i][j] != 1;j--)

       {

           if(matrix[i][j] == 0)

               matrix[i][j] = 2;

       }

   }

   //Verificam cantitatea maxima de apa si o salvam in variabila count

   int count = 0;

   for(int i =0; i<maxColumnLength;i++)

   {

       for(int j =0; j<n;j++)

           if(matrix[i][j] == 0)

               count++;

   }  

   

   cout<<"Cantitatea maxima de apa retinuta este: "<<count;

  return 0;

}