Portuguese Logic Programming Contest CeNPL'2003

University of Évora

9--11 May 2003


Salinas

Nas Salinas do Samouco o sr.Silva vende cristais de Sal aos visitantes, como iniciou o negócio há pouco tempo não tem balança e usa duas caixas de madeira, uma, a caixa 1 têm capacidade para 500 gramas e a outra, a caixa 2, tem capacidade para 200 gramas. Sempre que um cliente lhe pede uma determinada quantidade o Sr. Silva fornece-lha ou explica que não lha consegue vender. O Sr. Silva obtêm as quantidades pedidas com as seguintes operações sobre as caixas: encher até à capacidade total, despejando totalmente, despejando uma caixa na outra até que a outra esteja totalmente cheia ou que a que está a ser despejada esteja vazia, ou despejando a uma caixa no saco do cliente.

Por exemplo, para vender 100 gramas de cristais de Sal o Sr. Silva faz as seguintes acções: enche a caixa 2 e a seguir despeja-a na caixa 1; enche a caixa 2, outra vez, e despeja-a na caixa 1; volta a encher a caixa 2 e despeja-a na caixa 1 até a caixa 1 estar cheia; fica com as 100 gramas na caixa 2 e despeja-a no saco do cliente.

Problema

Faça um programa para ajudar o Sr. Silva a decidir se pode ou não vender o peso de sal que lhe pedem e se puder quais são os movimentos que ele deve fazer (deve indicar a melhor solução, i.e. a solução com o menor número de movimentos). Para que o Sr. Silva continue a poder usar o seu programa caso alguma caixa se parte e ele a tenha que substituir por outra de capacidade diferente, deve receber as capacidades máximas das caixas como parâmetro.

Inicialmente as caixas estão vazias.

Data

Input: 3 inteiros -- O primeiro inteiro representa o número de gramas pretendido. -- O segundo inteiro representa a capacidade máxima da caixa 1 em gramas. -- E o terceiro representa a capacidade máxima da caixa 2 em gramas.

Output: uma lista de acções - 
e(c1) - enche caixa 1
e(c2) - enche caixa 2
d(c1) - despeja caixa 1
d(c2) - despeja caixa 2
d(c1,c2)- despeja a caixa 1 sobre a 2 até encher a 2 ou vazar a 1
d(c2,c1)- despeja a caixa 2 sobre a 1 até encher a 1 ou vazar a 2
d_saco(c1) - despeja a caixa 1 no saco do cliente.
d_saco(c2) - despeja a caixa 2 no saco do cliente.

Results

input: (100,500,200).
output: [e(c1),d(c1,c2),d(c2),d(c1,c2),d_saco(c1)]

-----------
input: (50,500,200).
output: no

-----------
input:(200,250,550).
output: [e(c1),d(c1,c2),e(c1),d(c1,c2),e(c1),d(c1,c2),d_saco(c1)]
 
-----------

input:(100,250,550).
output: [e(c2),d(c2,c1),d(c1),d(c2,c1),d(c1),d(c2,c1),e(c2),d(c2,c1),
d(c1),d(c2,c1),d_saco(c2)]
ou qq uma das seguintes (que têm o mesmo número de movimentos), só precisa de devolver uma solução. 
[e(c2),d(c2,c1),d(c1),d(c2,c1),d(c1),d_saco(c2),e(c2),d(c2,c1),d(c1),
d(c2,c1),d_saco(c2)]
ou
[e(c2),d(c2,c1),d(c1),d(c2,c1),d_saco(c2),e(c2),d(c1),d(c2,c1),d(c1),
d(c2,c1),d_saco(c2)]
ou
[e(c2),d(c2,c1),d(c1),d(c2,c1),d_saco(c2),d(c1),e(c2),d(c2,c1),d(c1),
d(c2,c1),d_saco(c2)]
ou
[e(c2),d(c2,c1),d(c1),d(c2,c1),d_saco(c2),d(c1,c2),e(c2),d(c2,c1),d(c1),
d(c2,c1),d_saco(c2)]
This document was translated from LATEX by HEVEA.