Você trabalha em uma transportadora que atende o interior do estado de Mato Grosso. A frota desta empresa é composta por caminhões com diferen- tes limites de pesos. As mercadorias a serem transportadas estão embaladas em grandes caixas que também possuem pesos diferentes. Estas caixas são tão grandes que cada caminhão pode transportar, no máximo, duas delas. Infeliz- mente, não há na empresa procedimentos que podem ser utilizados para definir quais caixas devem ser transportadas em cada caminhão.
Considerando isto, você decidiu escrever um programa para resolver este pro- blema. Depois de analisá-lo com calma, você conclui que o seu programa deve ler um número inteiro
que representa a quantidade de caixas e, subsequen- temente, ler e armazenar em um vetor
números representando o peso das caixas. Em seguida, seu programa deve ler o peso suportado por um determi- nado caminhão. Depois disto, deve-se verificar (crie uma função para isto) se existem duas caixas que podem ser transportadas neste caminhão. Caso seja possível transportar, seu programa imprimir os índices das caixas.
Considerando isto, você decidiu escrever um programa para resolver este pro- blema. Depois de analisá-lo com calma, você conclui que o seu programa deve ler um número inteiro
Passo 1
O que o enunciado pede e o que foi dado (peguei tudo do enunciado):
- Entrada:
- Um inteiro
que é a quantidade de caixas. - Um vetor de
números representando o peso das caixas: . - Um número que é o peso suportado pelo caminhão (capacidade) que vou chamar de
.
- Um inteiro
- Saída desejada:
- Verificar se existem duas caixas que, juntas, pesem no máximo
(ou seja, para algum par ). - Caso exista, o programa deve imprimir os índices dessas duas caixas.
- Verificar se existem duas caixas que, juntas, pesem no máximo
- Decisões/assunções que vou adotar (porque o enunciado não especificou detalhes mínimos):
- Os índices a imprimir serão no formato 1-based (ou seja, o primeiro elemento tem índice
). Essa é uma convenção comum em enunciados e evita confusão com o usuário. - Se existir mais de um par possível, o programa pode imprimir qualquer par válido.
- Se não existir nenhum par, o programa deve imprimir uma mensagem clara (vou usar a string sem acento:
NAO EXISTE).
- Os índices a imprimir serão no formato 1-based (ou seja, o primeiro elemento tem índice
- Observação importante: haverá pelo menos a leitura de
, depois os pesos (na mesma linha ou em linhas separadas) e depois . Se então já sabemos que não há par.
Passo 2
Primeira ideia (método ingênuo, que ajuda a entender o problema): testar todos os pares.
- Ideia: para cada
de a e para cada de a , verificar se . Se sim, imprimir e e terminar. - Pseudocódigo simples:
- Para
até : - Para
até : - Se
então retornar .
- Se
- Para
- Se sair dos laços sem achar, então não existe par.
- Para
- Complexidade: esse método faz cerca de
verificações no pior caso, ou seja, tempo . - Quando usar: é simples, direto e em provas pode ser aceitável se
for pequeno. Mas se for grande (por exemplo, dezenas de milhares), fica inviável.
Passo 3
Método eficiente e ainda simples de implementar: ordenar com índices e usar dois ponteiros.
- Intuição passo a passo:
- Conservo os pesos junto com os índices originais porque, após ordenar, preciso saber quais eram os índices originais das caixas. Então crio uma lista de pares
. - Ordeno essa lista por peso (do menor para o maior).
- Uso dois ponteiros:
apontando para o menor peso (início da lista) e apontando para o maior peso (fim da lista). - Enquanto
: - Calculo
. - Se
, então encontrei um par válido: retorno os índices originais associados a e . - Se
, então a caixa mais pesada (em ) impossibilita combinações com o peso atual em — diminuir pode ajudar, então faço .
- Calculo
- Conservo os pesos junto com os índices originais porque, após ordenar, preciso saber quais eram os índices originais das caixas. Então crio uma lista de pares
- Por que esse esquema encontra um par se existir?
- Se existe algum par de caixas com soma
, então, depois de ordenar, o menor peso combinado com o maior peso vai explorar combinações extremas. Sempre que , qualquer combinação envolvendo e um elemento maior ou igual a também será > , então reduzir é seguro. Por outro lado, se para algum existir um tal que , o laço vai encontrar quando o ponteiro estiver naquele valor (ou antes). Assim o procedimento termina com um par válido se houver algum.
- Se existe algum par de caixas com soma
- Complexidade:
- Ordenação custa
. - O laço de dois ponteiros anda no máximo
passos (cada iteração move ou ), ou seja . - Portanto complexidade total
. Espaço extra para armazenar pares.
- Ordenação custa
Passo 4
Exemplo concreto (para ver as contas passo a passo):
- Suponha
, pesos e . - Formo pares (peso, índice):
. - Ordenando por peso crescentemente obtenho
. - Inicializo
(valor ) e (valor ). - Iteração 1: soma
→ achei! Retorno índices originais . (Note que os índices originais vindos dos pares são e .)
- Iteração 1: soma
- Nesse exemplo o par encontrado foi o menor com o maior e já funcionou; em outros casos o laço pode reduzir
várias vezes até achar ou até que e se cruzem. - Resultado final que o programa deve imprimir:
3 2(ou2 3— qualquer ordem de indices valida).
Passo 5
Implementação prática (verdades que ajudam na prova e no laboratório):
- A função pedida pode ser exatamente a que descrevi: recebe um vetor de pesos e
, retorna um par de índices ou indicação de que não existe. - Vou mostrar uma implementação curta e clara em Python (pode ser facilmente traduzida para C/C++/Java). Explico linha a linha depois.
- Observações para a prova:
- Sempre cuide da correspondência entre índices após ordenar: guarde o índice original.
- Trate o caso
explicitamente (retorna “NAO EXISTE”). - Se a leitura da entrada vier em várias linhas, garanta que leia os
valores antes de usar. - No enunciado pedia “crie uma função para isto” — então isole a lógica em uma função, por exemplo
.
Explicação do código (linha a linha, em linguagem simples):
arr = [(w, i+1) for i, w in enumerate(weights)]— cria pares. arr.sort(key=lambda x: x[0])— ordena pelos pesos.l, r = 0, len(arr)-1— inicializa ponteiros à esquerda e direita.- No laço
while l < r:s = arr[l][0] + arr[r][0]— soma dos dois pesos atuais.- Se
s <= C, retornaarr[l][1], arr[r][1]— os dois índices originais. - Senão,
r -= 1para tentar uma caixa menos pesada.
- Se o laço terminar sem encontrar, retorna
None. - No corpo principal do programa: lê entradas, chama a função e imprime o resultado conforme o enunciado.
Passo 6
Mensagem de ânimo final e dicas rápidas de prova
- Você já tem duas abordagens: a quadrática (simples) e a de dois ponteiros (eficiente). Se na prova não houver limites grandes para
, a versão quadrática pode ser entregue rapidamente e funciona; se o examinador espera eficiência, apresente a versão com ordenação e dois ponteiros. - Não esqueça de especificar a convenção de índices (eu escolhi 1-based) e trate o caso
. - Confiança: a parte chata é manter os índices originais ao ordenar — o resto é só seguir os passos do laço. Vai dar certo!
Resposta
def find_two_boxes(weights, C):
arr = [(w, i+1) for i, w in enumerate(weights)]
arr.sort(key=lambda x: x[0])
l, r = 0, len(arr) - 1
while l < r:
s = arr[l][0] + arr[r][0]
if s <= C:
return arr[l][1], arr[r][1]
else:
r -= 1
return None
arr = [(w, i+1) for i, w in enumerate(weights)]
arr.sort(key=lambda x: x[0])
l, r = 0, len(arr) - 1
while l < r:
s = arr[l][0] + arr[r][0]
if s <= C:
return arr[l][1], arr[r][1]
else:
r -= 1
return None
leitura e saída (exemplo de integração)
n = int(input())
weights = list(map(int, input().split()))
C = int(input())
res = find_two_boxes(weights, C)
if res:
print(res[0], res[1])
else:
print(“NAO EXISTE”)
weights = list(map(int, input().split()))
C = int(input())
res = find_two_boxes(weights, C)
if res:
print(res[0], res[1])
else:
print(“NAO EXISTE”)