Fișierul intrare/ieșire restaurare.in, restaurare.out Sursă ONI 2015 clasa a 8-a
Autor Marius Nicoli Adăugată de avatar Isabela_coman Coman Isabela Patricia Isabela_coman
Timp de execuție pe test 1.1 sec Limită de memorie 8192 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Restaurare (clasa a 8-a)

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ță

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

Date de ieșire

Fișierul restaurare.out 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

  • 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

table(example). |_. restaurare.in |_. restaurare.out |_. Explicație | | 5
4 3 2 4 2
3
1 4 3 | 0
4
2 | Forma inițială a zidului:

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.

|

Trebuie să te autentifici pentru a trimite soluții. Click aici