| Fişierul intrare/ieşire: | pietre3.in, pietre3.out | Sursă | InfoOltenia 2018 - Clasele 7 - 8 |
| Autor | Sofia Vitelaru | Adăugată de |  Info-Oltenia 2018 •infooltenia |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Pietre3
Alinuţa a primit în dar n pietre preţioase provenind din mai multe şiraguri, destrămate. Fiecare piatră are asociat un număr natural, iar pietrele cu numere consecutive fac parte din acelaşi şirag original. Nu există două pietre preţioase cu acelaşi număr asociat. Alinuţa dispune şi de k pietre magice, fiecare dintre acestea având o anumită putere, exprimată printr-un număr natural. Puterea unei pietre magice constă în faptul că aceasta se poate transforma în exact p pietre preţioase cu valori consecutive oarecare. Folosind o piatră magică Alinuţa poate transforma două şiraguri în unul singur, bineînţeles dacă puterea acesteia permite acest lucru. Fiecare piatră magică poate fi utilizată o singură dată. Pentru a uni două şiraguri poate fi utilizată o singură piatră magică şi numai dacă puterea ei acoperă exact diferenţa între două şiraguri succesive.
Cunoscând valorile asociate celor n pietre preţioase şi puterea fiecărei pietre magice ajutaţi-o pe Alinuţa să determine:
- numărul de şiraguri pe care le are iniţial
- numărul minim de şiraguri pe care le poate obtine prin utilizarea obligatorie a tuturor pietrelor preţioase pe care le are şi a pietrelor magice.
- lungimea celui mai lung şirag obţinut prin utilizarea cel mult a unei singure pietre magice
Date de intrare
Fişierul de intrare pietre3.in conţine:
- pe prima linie: un număr natural n, reprezentând numărul de pietre preţioase;
- pe a doua linie: n numere naturale separate prin câte un spaţiu, reprezentând valorile asociate pietrelor preţioase;
- pe a treia linie: valoarea k, numărul pietrelor magice;
- pe ultima linie: k valori naturale separate prin câte un spaţiu, reprezentând puterile pietrelor magice.
Date de ieşire
Fişierul de ieşire pietre3.out va conţine:
- pe prima linie o valoare naturală d, reprezentând numărul de şiraguri pe care le are iniţial;
- pe a doua linie numărul minim de şiraguri ce se pot obţine prin utilizarea obligatorie a tuturor pietrelor preţioase şi a pietrelor magice;
- pe a treia linie o valoare naturală, reprezentând lungimea celui mai lung şirag obţinut prin utilizarea cel mult a unei singure pietre magice.
Restricţii
- 1 ≤ n ≤ 100.000
- 1 ≤ k ≤ 100.000
- Valorile asociate pietrelor preţioase sunt numere naturale mai mici sau egale cu 1.000.000
- Valorile ascociate pietrelor magice sunt numere naturale mai mici sau egale cu 1.000.000
- Se consideră că o singură piatră preţioasă formează un şirag
Exemplu
| pietre3.in | pietre3.out | Explicaţii |
|---|---|---|
| 9 1 2 3 6 11 8 7 14 9 3 2 1 2 | 4 1 9 | Există 4 şiraguri (1 2 3, 6 7 8 9, 11, 14) Piatra magică ce are puterea 2 se poate transforma în pietrele 4 5 ceea ce conduce la formarea şiragului 1 2 3 4 5 6 7 8 9 Piatra magică ce are puterea 1 se transformă în 10 unificând şiragurile 6 7 8 9 şi 11 iar piatra magică ce are puterea 2 în 12 13, unificând 11 cu 14 Cel mai lung subşir se poate obţine prin unirea şiragurilor 1 2 3 şi 6 7 8 9 |
| 9 1 2 3 6 11 8 7 13 9 3 2 1 2 | 4 2 9 | Există 4 şiraguri (1 2 3, 6 7 8 9, 11, 13) Piatra magică ce are puterea 2 se poate transforma în pietrele 4 5 ceea ce conduce la formarea şiragului 1 2 3 4 5 6 7 8 9 Piatra magică ce are puterea 1 se transformă în 10 unificând şiragurile 6 7 8 9 şi 11 sau se poate transforma în 12 unificând şiragurile 11 şi 13, iar cea de a doua piatra magică ce are puterea 2 rămâne neutilizată. Cel mai lung subsir se poate obtine prin unirea şiragurilor 1 2 3 şi 6 7 8 9 |
