Ir ao conteúdo
  • Cadastre-se
Entre para seguir isso  
Renata Medeiros

Calcular quantas fatias de pão é necessário para atender todos os clientes

Recommended Posts

Galera,quem puder ajudar a elaborar um algoritmo em C para resolver este problema,agradeceria.

 

Pão a metro é um tipo de sanduíche gigante que é uma excelente opção de lanche para torneios de programação, embora a experiência já tenha mostrado que o oferecimento de sanduiches pode gerar reclamação dos competidores. Outro grande problema é que algumas pessoas são mais gulosas que outras e, dessa maneira, acabam pegando pedaços maiores que os pedaços dos outros. Para a final da OBI, a coordenação estava pensando em providenciar pão a metro para os competidores, porém tais problemas os fizeram recuar na ideia.

Embora a ideia tenha sido momentaneamente abandonada, uma ideia simples surgiu: cortar previamente o pão em fatias de tamanho iguais e distribuí-las entre as pessoas. O único problema com tal ideia é que se o número de pessoas for muito grande, fica impraticável ter apenas um pão. Por exemplo, se quisermos que 1.000 pessoas recebam 20 centímetros de sanduíche, seria necessário um sanduíche de 20.000 centímetros, ou 200 metros!

Alguém levantou a seguinte hipótese: se houvessem N pessoas e fossem encomendados K sanduíches de empresas diferentes, cada qual com uma determinada metragem (tamanho) Mi (1 ≤ i ≤ K), seria possível retirar desses pães N fatias de mesmo tamanho, possivelmente sobrando partes nao utilizadas. A questão seria: qual o tamanho inteiro máximo que essas fatias poderão ter?

Por exemplo, se tivermos K = 4, com os tamanhos (em centímetros) M1 = 120, M2 = 89, M3 = 230 e M4 = 177 e N = 10, podemos retirar N fatias iguais de tamanho máximo 57, pois assim conseguimos 2 fatias no primeiro pão, 1 no segundo, 4 no terceiro e 3 no quarto, totalizando as 10 fatias necessárias. Se tentarmos cortar fatias de tamanho 58, só será possível obter 3 fatias do terceiro pão, totalizando 9 e, portanto, 57 é realmente o melhor que podemos obter. Note que não podemos usar duas ou mais fatias menores de diferentes pães para formarmos uma fatia do tamanho selecionado. (ficaria muito deselegante dar um lanche recortado `às pessoas).

 

Tarefa

Escreva um programa que, dados os tamanhos de pão disponíveis (em centímetros) e a quantidade de pessoas a serem atendidas, retorne o tamanho inteiro máximo (em centímetros) da fatia que pode ser cortada de maneira a atender todas as pessoas.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém um inteiro N que indica a quantidade pessoas (1 ≤ N ≤ 10.000). A segunda linha contém um inteiro K (1 ≤ K ≤ 10.000) que é a quantidade de sanduíches disponível. Na terceira linha há K inteiros M (1 ≤ M ≤ 10.000) separados por um espaço em branco representando o tamanho de cada pão.

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo o tamanho inteiro máximo da fatia que pode ser cortada.

Exemplos

Entrada: 10 4 120 89 230 177 Saída: 57

Entrada: 3 2 45 85 Saída: 42

Entrada: 7 7 100 98 99 505 102 97 101 Saída: 101

 

Link da questão:http://br.spoj.com/problems/PAO07/

Editado por dif
Por gentileza não apague o conteúdo.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Caro usuário,

 

Seja bem-vindo ao Fórum do Clube do Hardware.

 

No intuito de servir como fonte de pesquisa no caso de instituições de ensino, informamos que incorrer no resolvimento por completo de questões relacionadas a disciplinas escolares de cursos técnicos e faculdades podem ser revistas e removidas pela Equipe de Moderação do Clube do Hardware.

 

Para sanar dúvidas sobre esse tipo de problema, por gentileza, publique o passo a passo do desenvolvimento da questão, projeto, monografia ou conteúdo em dúvida para que possamos analisar se a sua resposta está certa ou não, ou para que possamos ajudá-lo com a sua dúvida no desenvolvimento do exercício.

 

Infelizmente, não temos como resolver seus trabalhos por você. O objetivo do Fórum do Clube do Hardware é auxiliar você a sanar suas dúvidas, e não de responde-las em seu lugar. Além disso, copiar e colar respostas que não são de sua autoria é considerado plágio, o que é ilegal.

 

 

Quanto à sua dúvida, para podermos lhe ajudar, nós precisamos de mais alguns detalhes, tais como:

 

  • parte do código que já foi feito;
  • caso não tenha um código feito, qual o algoritmo que você pretende usar para resolver o problema;
  • você tem experiência com esta linguagem de programação?

 

Por favor, não leve para o lado pessoal, mas o nosso objetivo principal aqui é ajudar você a resolver o problema, se simplesmente postássemos um código já pronto, você nunca aprenderia de fato... ;)

 

Esperamos que compreenda.

 

 

Atenciosamente,

Equipe Clube do Hardware

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora
Entre para seguir isso  





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×