Avançado Informática – Semana 21 – Noic
Browse: Home / Problemas da Semana / Informática / Avançado Informática – Semana 21
Avançado Informática - Semana 21
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.
A entrada contém vários casos de teste. Cada caso de teste consiste de duas linhas. A primeira linha contém quatro inteiros N (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 ≤ Fi ≤ 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.
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.