% CCC 2007
% J5: Keep on Truckin'
%
%  Arrays and dynamic programming :-)
%
% Step 1: sort the motels
% Step 2: find the first motels you can get to on day one.
% step 3: (the hard step)
%         The idea is to find all the ways to
%         EVERY motel, not just the last.
%         For each motel:
%             find out which motels to can get to from there
%                     (subtract the distances)
%             The key thing is:
%                  suppose you can get to motel D in 2 ways.
%                  suppose you can get to motel K in 3 ways,
%                      (without going thru D first, maybe thru A, B and C).
%                  then if you can get from D to K,
%                    the numbers of ways to K is 2 + 3 = 5 ways!
%

var motel : array 1 .. 50 of int
var ways : array 1 .. 50 of int
var minn, maax, size, n : int

% insertion sort to get the motels in order after input
procedure sortMotels
    var j, hold : int
    for i : 2 .. size
        hold := motel (i)
        j := i - 1
        loop
            exit when j < 1 or motel (j) < hold
            motel (j + 1) := motel (j)
            j := j - 1
        end loop
        motel (j + 1) := hold
    end for
end sortMotels

function between (a, b, c : int) : boolean
    result a <= b and b <= c
end between


size := 13
motel (1) := 990
motel (2) := 1010
motel (3) := 1970
motel (4) := 2030
motel (5) := 2940
motel (6) := 3060
motel (7) := 3930
motel (8) := 4060
motel (9) := 4970
motel (10) := 5030
motel (11) := 5990
motel (12) := 6010
motel (13) := 7000

% get input
get minn
get maax
get n
for i : 1 .. n
    get motel (i + size)
end for
size := size + n
sortMotels

% load the ways for the first motels
for i : 1 .. size
    if between (minn, motel (i), maax) then
        ways (i) := 1
    else
        ways (i) := 0
    end if
end for

% work thruough all the motels and all the ways
% answering "can you get to the next motel?"
for i : 1 .. size - 1

    % can you get to i?
    if ways (i) > 0 then

        for j : i + 1 .. size

            % can you get from i to j?
            if between (minn, motel (j) - motel (i), maax) then
                ways (j) := ways (j) + ways (i)
            end if
        end for
    end if
end for

put ways (size)