Befektetés
Van M forintunk, és ismerjük egy árucikk árára vonatkozó előrejelzéseket a következő 12 hónapra. Szeretnénk a lehető legtöbb profitot elérni pénzünk befektetésével, ezért ki kell számolnunk, hogy melyik hónapban érdemes vásárolni, és melyik hónapban érdemes eladni
az árucikket. A termék nem osztható kisebb részekre, csak egész darabszámot vásárolhatunk. Feltételezhetjük, hogy a termék ára minden hónapban különböző. Ha két különböző stratégia azonos profitot eredményez, akkor azt kell választani, ahol alacsonyabb egységáron vásárolunk. Egyetlen hónapban vásárolhatunk, és egyetlen későbbi hónapban adhatjuk el a teljes készletet.
Feladat
Határozzuk meg, hogy melyik hónapban érdemes vásárolni, mikor kell eladni, és mennyi profit érhető el. Ha az adott feltételek mellett nem szerezhető profit, akkor az "IMPOSSIBLE" szöveget kell kiírni.
Bemenet
Az első sor a tesztesetek számát adja meg.
Minden teszteset két sorból áll. Az első a rendelkezésre álló pénzmennyiséget adja meg, a következő pedig 12 számot, az árucikk árára vonatkozó előrejelzéseket a következő 12 hónapra.
Kimenet
Ha szerezhető profit, akkor három számot kell kiírni, a vásárlás és az eladás hónapjának sorszámát, majd az elérhető profitot. Különben az "IMPOSSIBLE" szöveg jelzi, hogy nem érhető el haszon. A hónapok 1-től vannak sorszámozva.
Példa
Bemenet
3 100 1 2 3 4 5 6 7 8 9 10 11 12 100 52 50 25 100 61 63 70 51 71 55 10 5 100 200 150 250 132 125 110 210 220 180 176 108 113
Kimenet
Case #1: 1 12 1100 Case #2: 3 4 300 Case #3: IMPOSSIBLE