/* 

  Cashier change problem in Picat.

  From "Puzzle-based learning", page 86ff
  """
  A customer tried to change a dollar in a shop. The cashier said:
  "I am sorry, but I can not change it with the coins I have."
  The customer then asked for a change of half dollar, but the cashier
  replied "I am sorry, but I can not change it with the coins I have."
  The customer asked for a change of a quarter, then a dime, then 
  a nickel, but for all these requests the cashier kept replying
  "I am sorry, but I can not change it with the coins I have." Finally,
  the customer got upset and asked: "Do you have any coins at all?"
  The casher replied: "Yes ... I have $1.15 in coins." The question
  is: what coins where in the cash register?
  """

  Nomenclature:
  - half dollar: 50 cent
  - quarter    : 25 cent
  - dime       : 10 cent
  - nickel     :  5 cent
  -            :  1 cent

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


import cp.


main => go.


go =>
  
  Total = 115, % $1.15
  
  B = [1,5,10,25,50], % denominations
  B2 = B ++ [100],    % with a dollar
  N = B.length,

  % decision variables
  X = new_list(N),
  X :: 0..Total,

  Total #= sum([X[I]*B[I] : I in 1..N]),

  % for all the denominations (b[i]):
  foreach(I in 1..N)
    % and for all the denominations larger than b[i]:
    foreach(J in I+1..N+1)
      % there is no amount of b[i]*(1..x[i]) that can yield the amount of b2[j]
      sum([ K #<= X[I] #/\ B[I]*K #= B2[J] : K in 1..fd_max(X[I])]) #= 0
    end

  end, 

  solve(X),
  println(x=X),  
  nl,

  foreach(I in 1..N)
    printf("%2d cent: %d\n", B[I], X[I])
  end,

  nl.