Editing 1224 - Restaurare

<code>restaurare.in</code>
 5
 4 3 2 4 2
 3
 1 4 3
<code>restaurare.out</code>
 0
 4
 2
După descoperirea ruinelor unei cetăți medievale, arheologii au hotărât restaurarea acesteia, începând cu zidul principal. Acesta este format din <code>N</code> piloni, fiecare cu lățimea de <code>1</code> metru, așezați unul lângă altul (lipiți). Se cunoaște înălțimea, în metri, a fiecărui pilon dar, din păcate, nu toți mai sunt acum la același nivel.

Pentru restaurarea zidului, arheologii dispun de cărămizi care au lățimea de câte <code>1</code> metru și lungimi variabile, exprimate în metri. Sunt disponibile oricâte cărămizi, de oricare lungime. Considerăm că toate cărămizile disponibile și toți pilonii care alcătuiesc zidul au aceeași grosime, de <code>1</code> metru.

Restaurarea constă în două etape:

* în prima etapă, toți pilonii cu înălțimea mai mare sau egală cu <code>H</code> se retează, aducându-se astfel la înălțimea <code>H</code>, ceilalți, mai scunzi, păstrându-și înălțimea inițială;
* în a doua etapă se aduc toți pilonii la aceeași înălțime, umplându-se golurile dintre ei cu cărămizi, astfel încât  zidul să devină compact; din motive neînțelese, arheologii vor așeza cărămizile “culcate”, fiecare dintre acestea ocupând, eventual, spațiul aflat deasupra mai multor piloni.

Arheologii au analizat situația, independent, pentru <code>Q</code> valori posibile ale lui <code>H</code>.

= Cerința =
Pentru fiecare dintre cele <code>Q</code> valori alese pentru înălțimea <code>H</code>, se cere să se determine numărul minim de cărămizi necesare restaurării zidului, independent, pornind de la înălțimile inițiale ale pilonilor.

= Date de intrare =
Fișierul de intrare <code>restaurare.in</code> conține:

* pe prima linie, numărul <code>N</code> de piloni;
* pe a doua linie, <code>N</code> numere naturale, separate prin câte un spațiu, reprezentând înălțimile inițiale ale pilonilor, în ordine, de la stânga la dreapta;
* pe linia a treia, numărul natural <code>Q</code>, reprezentând numărul de valori posibile pentru înălțimea <code>H</code>;
* pe a patra linie, <code>Q</code> numere naturale, separate prin câte un spațiu, reprezentând valorile posibile ale lui <code>H</code>.

= Date de ieșire =
Fișierul de ieșire <code>restaurare.out</code> va conține <code>Q</code> numere, câte unul pe linie, reprezentând numărul minim de cărămizi necesare restaurării pentru fiecare dintre înălțimile <code>H</code>, în ordinea în care acestea apar în fișierul de intrare.

= Restricții și precizări =

* <code>1 ≤ N ≤ 100000</code>;
* înălțimea fiecărui pilon este un număr natural din intervalul <code>[1 , 100000]</code>;
* <code>1 ≤ Q ≤ 100000</code>;
* <code>1 ≤ H ≤</code> valoarea maximă dintre înălțimile inițiale ale pilonilor;
* pentru 35% dintre teste <code>N ≤ 1000</code>, iar pentru alte 40% dintre teste <code>Q = 1</code>.

= Exemplu: =
<code>restaurare.in</code>
 5
 4 3 2 4 2
 3
 1 4 3
<code>restaurare.out</code>
 0
 4
 2

= Explicație =
Forma inițială  a zidului este:

Pentru <code>H=1</code> toți pilonii au aceeași înălțime, deci nu mai este necesară nicio cărămidă, pentru <code>H=4</code>, sunt necesare <code>4</code> cărămizi, zidul având, după restaurare structura din fig. a, iar pentru <code>H=3</code>, sunt necesare <code>2</code> cărămizi, zidul având, după restaurare structura din fig. b.

<syntaxhighlight lang="python" line="1">
def min_bricks_for_heights(piloni, H):
    total_bricks = 0
    current_height = 0
    
    for height in piloni:
        if height > H:
            height = H
        
        if height > current_height:
            total_bricks += 1
            current_height = height
        elif height < current_height:
            current_height = height
    
    return total_bricks

def bricks_needed_for_restoration(piloni, H_values):
    results = []
    for H in H_values:
        results.append(min_bricks_for_heights(piloni, H))
    return results

# Exemplu de utilizare
N = 5
piloni = [3, 1, 4, 1, 5]
Q = 3
H_values = [2, 3, 5]

print(bricks_needed_for_restoration(piloni, H_values))
</syntaxhighlight>