Ádám tartozik Évának F forinttal. Ismerjük Ádám és Éva pénzjegyeit. Ádám meg szeretné adni a tartozását. Ha nem tudja pontosan megadni, akkor a tartozásból adhat többet úgy, hogy a többletet Éva visszaadja neki a saját pénzéből.
Feladat
Készíts programot, amely megadja, hogy hogyan tudja megadni Ádám a tartozását úgy, hogy Évának a lehető legkevesebb összeget kelljen visszaadni. Bemenet
A standard bemenet első sorában Ádám tartozása van (1 ≤ F ≤ 10 000). A második sorban Ádám pénzjegyei száma (1 ≤ N ≤ 100) található. A harmadik sorban Ádám N pénzjegye értéke szerepel (1≤P i ≤1000). A negyedik sorban Éva pénzjegyei száma (1 ≤ M ≤ 100) található. Az ötödik sorban Éva M pénzjegye értéke szerepel (1 ≤ Qi ≤ 1000). Kimenet
A standard kimenet első sorába azt a legkisebb összeget kell írni, amelyet Évának vissza kell fizetnie! Ha nincs megoldás, akkor az első és egyetlen sorba a -1 számot kell írni. A második sorba első számként a kifizetésben Ádám felhasznált pénzjegyei K számát kell írni, majd annak a K pénzjegynek a sorszámát (tetszőleges sorrendben), amelyekkel Ádám fizet. A harmadik sorba első számként Éva felhasznált pénzjegyei L számát kell írni, majd annak az L pénzjegynek a sorszámát (tetszőleges sorrendben), amelyekkel Éva visszafizet! Több megoldás esetén bármelyik megadható. Példa
| Bemenet |
Kimenet |
450
4
200 200 300 550
3
10 40 100 | 50
2 2 3
2 1 2
|
Tesztadatok
Csatolmányként
Címkék
A feladat forrása: Nemes Tihamér verseny, 2015-2016 2. forduló
Algoritmusok:
megoldás |
|
2004-2016 BDG algoritmus szakkör