problem14.f

      PROGRAM PROBLEM14
      INTEGER I, RES, WAYS
      DO 10 I=1,15
      RES = WAYS(I)
      PRINT *, I, RES
10    CONTINUE
      END

      INTEGER FUNCTION MIN(A, B)
      INTEGER A, B
      MIN = A
      IF (B .LT. A) MIN=B
      RETURN
      END

C CALCULATE THE NUMBER OF WAYS OF MAKING THE TARGET AS A SUM OF 
C NUMBERS WITH NO SUMMAND APPEARING MORE THAN TWICE
      INTEGER FUNCTION WAYS(TARGET) 
      INTEGER TARGET, MAXNUM
      INTEGER NUMBRS(TARGET), COEFFS(TARGET), MAXES(TARGET)
      INTEGER HNUM, I, J, SUM, T
      INTEGER MIN
      LOGICAL ISDONE, DIVIDP
      MAXNUM=0
      DO 20 I=TARGET,1,-1
      MAXNUM = MAXNUM + 1
      NUMBRS(MAXNUM) = I
20    CONTINUE
C NOW MAXNUM IS THE NUMBER OF POSSIBLE NUMBERS TO CONSIDER 
      WAYS = 0
      DO 55 J=1,MAXNUM
      HNUM = NUMBRS(J)
      T = TARGET - HNUM
C      PRINT *, "HNUM", HNUM, "REDUCED TARGET", T, "CURRENT WAYS", WAYS
      IF (T .EQ. 0) WAYS = 1
C NEED TO MAKE T USING NUMBERS SMALLER THAN OR EQUAL TO HNUM
      DO 29 I=1,MAXNUM
C FOR ALL POWERS SMALLER THAN THE MAXIMUM WE'RE CONSIDERING, WORK
C OUT THE MAXIMUM NUMBER OF EACH THAT COULD PLAUSIBLY BE NEEDED IN THE
C SUM. SET ALL COEFFICIENTS TO ZERO
      IF (NUMBRS(I) .GT. HNUM) GOTO 25
      IF (NUMBRS(I) .EQ. HNUM) GOTO 26
      MAXES(I) = MIN(2, T / NUMBRS(I))
      GOTO 28
26    MAXES(I) = MIN(1, T / NUMBRS(I))
      GOTO 28
25    MAXES(I) = 0
28    COEFFS(I) = 0
29    CONTINUE
      ISDONE = .FALSE.
30    CALL CNTL(COEFFS, MAXES, MAXNUM, ISDONE)
      IF (ISDONE) GOTO 55
      SUM = 0
      DO 40, I=1,MAXNUM
      SUM = SUM + COEFFS(I) * NUMBRS(I)
C      PRINT *, "I", I, "COEFFS(I)", COEFFS(I), "NUMBRS(I)", NUMBRS(I)
40    CONTINUE
      IF (SUM .NE. T) GOTO 50
C      PRINT *, "SUCCESS FOR T=", T
      WAYS = WAYS + 1
50    GOTO 30
C55    PRINT *,"NOW WAYS=", WAYS
55    CONTINUE
60    END