Fișierul intrare/ieșire | restaurare.in, restaurare.out | Sursă | ONI 2015 clasa a 8-a |
---|---|---|---|
Autor | Marius Nicoli | Adăugată de | 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 |
Vezi soluțiile trimise | Statistici
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.
|