1224 - Restaurare

restaurare.in

5
4 3 2 4 2
3
1 4 3

restaurare.out

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 N piloni, fiecare cu lățimea de 1 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 1 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 1 metru.

Restaurarea constă în două etape:

• în prima etapă, toți pilonii cu înălțimea mai mare sau egală cu H se retează, aducându-se astfel la înălțimea H, 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 Q valori posibile ale lui H.

Cerința

Pentru fiecare dintre cele Q valori alese pentru înălțimea H, 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 restaurare.in conține:

• pe prima linie, numărul N de piloni;
• pe a doua linie, N 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 Q, reprezentând numărul de valori posibile pentru înălțimea H;
• pe a patra linie, Q numere naturale, separate prin câte un spațiu, reprezentând valorile posibile ale lui H.

Date de ieșire

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

Restricții și precizări

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

Exemplu:

restaurare.in

5
4 3 2 4 2
3
1 4 3

restaurare.out

0
4
2

Explicație

Forma inițială a zidului este:

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

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