Programozás‎ > ‎Feladatok‎ > ‎

Számösszegzés

Adott a1, ..., aN N pozitív egész szám. Kiszámítandó, hogy a b1, ..., bM egész számok közül melyek állíthatók elő az a1, ..., aN számok közül vett számok összegeként (egy szám akárhányszor szerepelhet az összegben). 

Feladat

Írj programot, amely megoldja a feladatot!

Bemenet

A szamok.be szöveges állomány első sora két egész számot tartalmaz, az összegként való előállításban szerepeltethető számok N számát (1 <= N <= 100) és az előállítandó számok M számát (1 <= M <= 10000). A második sor pontosan N egész számot tartalmaz növekvő sorrendben (egy-egy szóközzel elválasztva), az előállításban szerepeltethető számokat, amelyek mindegyikének értéke legalább 1, legfeljebb 30000. A harmadik sor pontosan M egész számot tartalmaz növekvő sorrendben, (egy-egy szóközzel elválasztva), az előállítandó számokat, amelyek mindegyikének értéke legalább 1, legfeljebb 2000000000.

Kimenet

A szamok.ki szöveges állomány első és egyetlen sora pontosan M egész számot tartalmazzon egy-egy szóközzel elválasztva! Az i-edik szám értéke 1 legyen, ha a bemenet harmadik sorában az i-edik szám előállítható a bemenet második sorában megadott számok összegeként, egyébként pedig a 0 szám legyen!

Példa

Bemenet  Kimenet
4 12
3 7 13 32
2 5 7 8 9 10 11 12 13 14 15 1234567890
0 0 1 0 1 1 0 1 1 1 1 1


Tesztadatok

Címkék

A feladat forrása: NTOITV 2013 2. forduló, 11-13. évfolyam
Algoritmusok: dinamikus programozás