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 n que representa a quantidade de caixas e, subsequen- temente, ler e armazenar em um vetor n 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.

Passo 1

O que o enunciado pede e o que foi dado (peguei tudo do enunciado):
  • Entrada:
    • Um inteiro n que é a quantidade de caixas.
    • Um vetor de n números representando o peso das caixas: w_1, w_2, \dots, w_n.
    • Um número que é o peso suportado pelo caminhão (capacidade) que vou chamar de C.
  • Saída desejada:
    • Verificar se existem duas caixas que, juntas, pesem no máximo C (ou seja, w_i + w_j \le C para algum par i\neq j).
    • Caso exista, o programa deve imprimir os índices dessas duas caixas.
  • 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 1). 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).
  • Observação importante: haverá pelo menos a leitura de n, depois os n pesos (na mesma linha ou em linhas separadas) e depois C. Se n<2 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 i de 1 a n-1 e para cada j de i+1 a n, verificar se w_i + w_j \le C. Se sim, imprimir i e j e terminar.
  • Pseudocódigo simples:
    • Para i=1 até n-1:
      • Para j=i+1 até n:
        • Se w_i + w_j \le C então retornar (i,j).
    • Se sair dos laços sem achar, então não existe par.
  • Complexidade: esse método faz cerca de \dfrac{n(n-1)}{2} verificações no pior caso, ou seja, tempo \mathcal{O}(n^2).
  • Quando usar: é simples, direto e em provas pode ser aceitável se n for pequeno. Mas se n for grande (por exemplo, dezenas de milhares), \mathcal{O}(n^2) 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:
    1. 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 (peso, índice)í.
    2. Ordeno essa lista por peso (do menor para o maior).
    3. Uso dois ponteiros: l apontando para o menor peso (início da lista) e r apontando para o maior peso (fim da lista).
    4. Enquanto l < r:
      • Calculo s = peso[l] + peso[r].
      • Se s \le C, então encontrei um par válido: retorno os índices originais associados a l e r.
      • Se s > C, então a caixa mais pesada (em r) impossibilita combinações com o peso atual em l — diminuir r pode ajudar, então faço r := r-1.
  • Por que esse esquema encontra um par se existir?
    • Se existe algum par de caixas com soma \le C, então, depois de ordenar, o menor peso combinado com o maior peso vai explorar combinações extremas. Sempre que peso[l] + peso[r] > C, qualquer combinação envolvendo peso[r] e um elemento maior ou igual a peso[l] também será > C, então reduzir r é seguro. Por outro lado, se para algum r existir um l tal que peso[l] + peso[r] \le C, o laço vai encontrar quando o ponteiro l estiver naquele valor (ou antes). Assim o procedimento termina com um par válido se houver algum.
  • Complexidade:
    • Ordenação custa \mathcal{O}(n \log n).
    • O laço de dois ponteiros anda no máximo n passos (cada iteração move l ou r), ou seja \mathcal{O}(n).
    • Portanto complexidade total \mathcal{O}(n \log n). Espaço extra \mathcal{O}(n) para armazenar pares.

Passo 4

Exemplo concreto (para ver as contas passo a passo):
  • Suponha n=6, pesos [4,8,1,3,5,7] e C=10.
  • Formo pares (peso, índice): [(4,1),(8,2),(1,3),(3,4),(5,5),(7,6)].
  • Ordenando por peso crescentemente obtenho [(1,3),(3,4),(4,1),(5,5),(7,6),(8,2)].
  • Inicializo l=0 (valor (1,3)) e r=5 (valor (8,2)).
    • Iteração 1: soma 1+8=9 \le 10 → achei! Retorno índices originais (3,2). (Note que os índices originais vindos dos pares são 3 e 2.)
  • Nesse exemplo o par encontrado foi o menor com o maior e já funcionou; em outros casos o laço pode reduzir r várias vezes até achar ou até que l e r se cruzem.
  • Resultado final que o programa deve imprimir: 3 2 (ou 2 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 C, 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 n<2 explicitamente (retorna “NAO EXISTE”).
    • Se a leitura da entrada vier em várias linhas, garanta que leia os n 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 \texttt{find\_two\_boxes}.
Explicação do código (linha a linha, em linguagem simples):
  • arr = [(w, i+1) for i, w in enumerate(weights)] — cria pares (peso, índice\_1based)í.
  • 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, retorna arr[l][1], arr[r][1] — os dois índices originais.
    • Senão, r -= 1 para 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 n, 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 n<2.
  • 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

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”)

Exercícios relacionados