Avançado Informática - Semana 21

0 Flares Facebook 0 0 Flares ×

Remendo

Carlão é muito preocupado com o meio ambiente. Sempre que possível, ele tenta utilizar meios de transporte menos poluentes. Recentemente ele conseguiu um emprego próximo de casa e agora está utilizando sua bicicleta para ir ao trabalho.

Infelizmente, no caminho entre sua casa e seu emprego, há uma fábrica de pregos, que frequentemente deixa alguns pregos caírem de seus caminhões que acabam furando os pneus de da bicicleta de Carlão. Por isso, ele acaba tendo que fazer diversos remendos nos pneus de sua bicicleta.

Para fazer os consertos, Carlão usa dois tipos diferentes de remendos. Ambos os tipos têm a largura do pneu da bicicleta, mas diferem no comprimento. Como o valor do remendo é proporcional ao seu comprimento, Carlão está tentando encontrar uma maneira de economizar, gastando o menor comprimento total possível de remendos para fazer os consertos, mas sem precisar cortá-los.

O primeiro passo para efetuar o conserto é fazer uma marca com giz em uma posição do pneu e depois anotar as distâncias, medidas no sentido horário, de cada um dos furos em relação à marca de giz. Todos os furos devem ser cobertos por um remendo. Carlão gostaria de sua ajuda para determinar, a partir das posições dos furos, a forma mais econômica de efetuar o conserto.

Entrada

A entrada contém vários casos de teste. Cada caso de teste consiste de duas linhas. A primeira linha contém quatro inteiros (1 ≤ N ≤ 1000), C (1 ≤ C ≤ 106), (1 ≤ T1) e T2 (T2 ≤ C). O inteiro N corresponde ao número de furos no pneu e C corresponde ao comprimento da circunferência do pneu, em centímetros. Os comprimentos dos remendos, em centímetros, são dados pelos inteiros T1 e T2. A segunda linha da entrada contém N inteiros Fi (0 ≤ F≤ C-1), um para cada furo, descrevendo a distância no sentido horário da marca de giz até o furo i (1 ≤ i ≤ N), em centímetros. O Final da entrada é determinado por EOF (fim de arquivo).

Obs: Se a distância entre dois furos é exatamente k centímetros, um remendo de comprimento k centímetros é suficiente para cobrir ambos os furos.

Saída

Para cada caso de teste, seu programa deve imprimir uma única linha contendo um inteiro indicando o menor comprimento total de remendos que é suficiente para consertar todos os furos do pneu.

Exemplo de Entrada Exemplo de Saída
5 20 2 3
2 5 8 11 15
4 20 12 9
1 2 3 13
8
12
0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: