program JAD_9514 ; {$R+}
{ Determine the number of ways of giving change for PTot pence,
  using the coins in Pence. }
{ $DEFINE DETAILS}
{$DEFINE CACHE}

const MaxTot = 1000 ; CMin = 0 ; CMax = 7 ;
type CSet = CMin..CMax ; Dat = array [CSet] of word ;
const
Pence : Dat = (500, 100, 50, 20, 10,  5,  2,  1) ;
Using : Dat = (  0,   0,  0,  0,  0,  0,  0,  0) ;

{$IFDEF CACHE}
var Cache : array [1..MaxTot, CSet] of longint ;
{$ENDIF}

function JAD
  (const Sum : word ; const Big, Wee : byte ; var Use : Dat) : longint ;
var Add : word ; B : byte ; TJ : longint ;
begin
  if Sum=0 then begin
    {$IFDEF DETAILS} Add := 0 ;
    for B := CMin to CMax do begin Inc(Add, Use[B]*Pence[B]) ;
      if Use[B]>0 then Write(Use[B]:4, '*', Pence[B]:2, 'p')
        else Write('':8) ;
      end {B} ;
    Writeln('=':5, Add, 'p') ; {$ENDIF}
    JAD := 1 ; EXIT end {Sum=0} ;
  {$IFDEF CACHE} TJ := Cache[Sum][Big] ;
  if TJ<>0 then begin JAD := TJ ; EXIT end ; {$ENDIF}
  TJ := 0 ;
  for B := Big to Wee do begin Add := Pence[B] ;
    if Add<=Sum then begin Inc(Use[B]) ;
      Inc(TJ, JAD(Sum-Add, B, Wee, Use)) ;
      Dec(Use[B]) end ;
    end ;
  {$IFDEF CACHE} Cache[Sum][Big] := TJ ; {$ENDIF}
  JAD := TJ end {JAD} ;

var PTot, BigC, WeeC, BigX, WeeX : word ; Ans : longint ;

BEGIN ;
Writeln('JAD Quiz 1995, #14') ;
repeat
  Write('Pence: Total, Big & Small coin ??? ') ;
  Readln(PTot, BigC, WeeC) ;
  BigX := Cmin ; while Pence[BigX]<>BigC do Inc(BigX) ;
  WeeX := Cmin ; while Pence[WeeX]<>WeeC do Inc(WeeX) ;
  {$IFDEF CACHE} FillChar(Cache, SizeOf(Cache), 0) ; {$ENDIF}
  Ans := JAD(PTot, BigX, WeeX, Using) ;
  Writeln(PTot:5, BigC:5, '..', WeeC, Ans:12, ' ways.') ;
  until PTot=0 ;
END.  www.merlyn.demon.co.uk

Note : Without CACHE, time for Total=500 is intolerable ;
       With    CACHE,                       imperceptible ;