Problem F
Frimärksproblemet
Källkod: frim.pas, frim.p, frim.c eller frim.cc

   Skotten McSnik sitter med en kaffekopp (surrogat) vid sitt skrivbord en sen kväll. Framför sig har han en hög med frimärken (begagnade, men utan att stämpeln syns), en portotabell och en massa brev som han ska skicka. Eftersom McSnik är extremt snål så kan han inte tänka sig att frankera ett brev med mer än vad som krävs enligt portotabellen. Lyckas han frankera samtliga brev med minimiporto blir han glad. Tvingas han överfrankera något brev eller får han inte iväg alla breven blir han ledsen.

   Eftersom McSnik har funnit det ganska jobbigt att sitta och kombinera frimärken på brev så vill han ha ett datorprogram för det ändamålet. Eftersom denna uppgift ingår i en tävling så kostar utvecklandet av programmet inte McSnik någonting, vilket gör att han anser sig ha råd med det.
   Skriv ett program som avgör om McSnik kan frankera alla brev utan att överfrankera något. Klarar han det blir han glad, måste han överfrankera något blir han ledsen. I sin strävan att spara kombinerar naturligtvis McSnik frimärken med liten valör på ett och samma brev om detta är lämpligt.
   Portotabellen fungerar i Skottland precis som i Sverige, det vill säga de i portotabellen angivna vikterna är för brev upp till den angivna vikten. Har portotabellen tre steg, 10, 20, 30 gram så betyder det att brev mellan 0 och 10 gram får lägst porto, 11-20 det högre, och 21-30 gram det högsta. Eftersom skotten McSnik är så extremt snål så fyller han på med sand i breven till dess att de precis når den översta vikten i brevets korrekta intervall. Det vill säga att om McSnik har ett brev som väger 14 gram, vilket i portotabellen ovan skulle passa in i intervallet 11-20 så fyller McSnik på med 6 gram sand så att brevet kommer upp till precis 20 gram. "Har man betalt för ett brev på 20 gram så skall man minsan skicka ett som väger 20 gram också!"

   INDATA: Består av heltalet n på rad 1 och därefter n bekrivningar av frimärkshög (pund ()), portotabell (vikt i gram -> ), brevhög (vikt i gram). En frimärkshög beskrivs som en rad med belopp(valör) åtskiljda med komma (,). Beloppen är decimaltal med 2 decimaler, decimalpunkt (.) används. Varje rad i portotabellen består av ett tal, en pil (-> ("minus större än")) och ett belopp. Portotabellen har flera rader, men i filen kommer hela tabellen att skrivas på en enda rad, varför komma(,) kommer att användas som skiljetecken mellan raderna i portotabellen. En brevhög beskrivs som en rad med vikter (heltal) åtskiljda med komma (,). En frimärkshög kan högst bestå av 10 frimärken, en portotabell kan högst bestå av 10 rader och en brevhög kan högst bestå av 10 brev.

   UTDATA: Ska för varje beskrivning vara en rad med de fyra bokstäverna GLAD om McSnik, lyckades frankera alla breven utan att överfrankera något brev, och annars de sex bokstäverna LEDSEN.

Exempel på indatafilen:
Filen Kommentarer
2 Antalet deluppgifter
0.05,2.00,0.10,0.10,1.00,8.00 frimärkshögen
10->1.00,20->2.00,30->3.00 portotabellen
10,20,10 brevhögen
0.50,1.00,0.50,1.00,1.00 frimärkshögen
20->0.50,40->1.50,60->2.00 portotabellen
20,60,40 brevhögen
Vilket skall resultera i en utdatafil som ser ut så här:
LEDSEN
GLAD





The translation was made by Andreas Nilsson on Mon Sep 29 15:30:00 MET DST 1997