Je hebt een rekening bij een bank die gevraagd heeft om anoniem te blijven.
Per dag kunnen op deze rekening meerdere transacties uitgevoerd worden.
Elke dag worden de transacties pas verwerkt om middernacht, m.a.w. je ziet het resulterende saldo pas de dag nadien. Een mogelijk dagoverzicht is:
De bank wil echter winst maken. Ze besluiten je extra kosten (€35) aan te rekenen telkens je rekeningsaldo na een transactie negatief is:
Je begint met €80. Je spendeert €50; je saldo is hierna €30. Gezien dit nog steeds positief is, wordt er geen extra kost aangerekend. Voor de volgende Overdraft Vlaamse Programmeerwedstrijd uitgave van €90 heb je echter onvoldoende op je rekening staan en ga je in het negatief. De bank rekent een extra €35 aan. Ook bij de volgende transactie van €5 wordt je weer een extra €35 afgetrokken.
Als je dacht dat dit al zeer klantonvriendelijk was: het gaat nog een stapje verder. De bank zal zo ver gaan als de transacties herordenen zodat je een maximaal aantal keer in het negatief eindigt. In het voorgaande voorbeeld, spendeerde je na elkaar €50, €90 en €5. Als deze volgorde gehandhaafd wordt, is de eindbalans €-135. Als we echter de volgorde veranderen naar €90, €5 en €50 krijgen we:
Zoals je ziet maakt de bank nu €35 extra winst.
Het zal jullie dan ook niet verbazen dat de bank de VPW jury gevraagd heeft jullie een optimisatiealgoritme te laten uitwerken. Gegeven een beginsaldo en een aantal dagtransacties moeten jullie nagaan hoe de transacties te ordenen om een zo laag mogelijk eindsaldo te bekomen.
Per dag kunnen op deze rekening meerdere transacties uitgevoerd worden.
- Een transactie kan positief zijn: je hebt bv. je wedde ontvangen. Daardoor stijgt het saldo op je rekening.
- Een transactie kan ook negatief zijn: je deed inkopen in de supermarkt met je bankkaart, en het saldo van je rekening daalt.
Elke dag worden de transacties pas verwerkt om middernacht, m.a.w. je ziet het resulterende saldo pas de dag nadien. Een mogelijk dagoverzicht is:
De bank wil echter winst maken. Ze besluiten je extra kosten (€35) aan te rekenen telkens je rekeningsaldo na een transactie negatief is:
Je begint met €80. Je spendeert €50; je saldo is hierna €30. Gezien dit nog steeds positief is, wordt er geen extra kost aangerekend. Voor de volgende Overdraft Vlaamse Programmeerwedstrijd uitgave van €90 heb je echter onvoldoende op je rekening staan en ga je in het negatief. De bank rekent een extra €35 aan. Ook bij de volgende transactie van €5 wordt je weer een extra €35 afgetrokken.
Als je dacht dat dit al zeer klantonvriendelijk was: het gaat nog een stapje verder. De bank zal zo ver gaan als de transacties herordenen zodat je een maximaal aantal keer in het negatief eindigt. In het voorgaande voorbeeld, spendeerde je na elkaar €50, €90 en €5. Als deze volgorde gehandhaafd wordt, is de eindbalans €-135. Als we echter de volgorde veranderen naar €90, €5 en €50 krijgen we:
Zoals je ziet maakt de bank nu €35 extra winst.
Het zal jullie dan ook niet verbazen dat de bank de VPW jury gevraagd heeft jullie een optimisatiealgoritme te laten uitwerken. Gegeven een beginsaldo en een aantal dagtransacties moeten jullie nagaan hoe de transacties te ordenen om een zo laag mogelijk eindsaldo te bekomen.
Invoer
De eerste regel van de invoer bevat het aantal testgevallen. Per testgeval volgt:
- Een eerste regel bevat met een geheel getal dat het beginsaldo voorstelt.
- Een tweede regel bevat door één spatie gescheiden gehele getallen. Het eerste getal geeft aan hoeveel er nog volgen. Elk van de volgende getallen geeft een transactie aan: een positief getal voor inkomsten, een negatief getal voor uitgaven.
Voorbeeldinvoer:
4
100
1 -150
1000
3 -250 -750 -1500
1000
2 2000 -2000
80
3 -50 -90 -5
Uitvoer
Per testgeval wordt één regel afgedrukt, met daarop het volgnummer van het testgeval, gevolgd door een spatie, gevolgd door het laagst mogelijke saldo dat bekomen kan worden door de transacties te herordenen. Het eerste testgeval heeft volgnummer 1.
Uitvoer:
1 -80
2 -1605
3 965
4 -170