Aceasta este arhiva vechiului site al Colegiului Național „Emanuil Gojdu”. Informațiile de aici nu mai sunt actualizate. Mergi la site-ul actual: cnego.ro
Clasa a X-a
Ziua 2
Problema 4

 Numere

Se considera un numar natural n, un sir de numere naturale x1,x2,...,xn (x1<x2<...<xn) si un interval inchis avand capetele numere naturale. Sa se verifice daca orice numar natural din intervalul dat, poate sa fie scris ca o suma cu acelasi numar minim de termeni xi (1<=i<=n) in urmatoarele doua moduri:
- folosind obligatoriu cel putin o data termenul xn;
- folosind oricare dintre valorile din sir.
Se va afisa numarul valorilor din interval care nu indeplinesc conditia si valorile respective.
Observatie:
In cazul in care un numar nu se poate descompune într-unul din cele doua moduri, se considera numarul minim de termeni din descompunere ca fiind egal cu 0.

Date de intrare:
Fisierul NUMERE.IN are urmatoarea structura:
n  - numarul de elemente din sir (1<=n<=100)
a  b  :- capetele intervalului (2<=a<b<=10000)
x1 x2 ...xn  - sirul de numere x1<x2<...<xn<=a si xn<1000
Observatie:
Datele de intrare sunt corecte, nu necesita validare.

Date de iesire:
Pe prima linie a fisierului de iesire NUMERE.OUT se va scrie numarul valorilor din interval care nu indeplinesc conditia, iar daca acesta este nenul, pe linia urmatoare se vor afisa valorile respective despartite printr-un spatiu.

Exemplu 1:
 NUMERE.IN
3
7 13
1 4 5
NUMERE.OUT
2
8 12
Explicatie rezultate:
8=5+1+1 +1 (4 termeni)     8=4+4 (2 termeni)
12=5+5+1+1 (4 termeni)     12=4+4+4 (3 termeni)

Exemplu 2:
NUMERE.IN
3
7 10
2 4 6
NUMERE.OUT
0
Explicatie rezultate:
Toate numerele indeplinesc conditia ceruta (de exemplu, 7 nu poate fi reprezentat in cele doua moduri, deci ambele numere minime sunt 0, iar 8 se reprezinta in ambele moduri cu acelasi numar minim de termeni (2), etc.)

Timp maxim de executare/test: 2 secunde
Punctaj maxim posibil: 50 puncte