1288-canhao-de-destruicao

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "1.0" id: 1288 name: Canhão de Destruição slug: canhao-de-destruicao idBeecrowd: 1288 authorSlugProblem: Rafael A., Lucas D. e Marlon T. origin: beecrowd difficultyLevelId: C description: Neste problema ambientado em um cenário de guerra medieval, sua missão é destruir um castelo inimigo que possui uma resistência R. Você comandará um canhão e terá à disposição um conjunto de projéteis, cada um com peso e poder de destruição específicos. Seu objetivo é selecionar a melhor combinação de projéteis para colocar no canhão, respeitando o limite máximo de carga, a fim de causar o maior dano possível e verificar se é suficiente para destruir a fortaleza. editorial: |- Este problema é uma aplicação clássica e pura do problema da Mochila 0/1 (Knapsack 0/1). O aluno precisa ter conhecimentos prévios sobre otimização combinatória e a técnica de Programação Dinâmica. Pedagogicamente, é excelente para introduzir a modelagem de problemas de minimização/maximização com restrições e a relação de recorrência unidimensional. É classificado com dificuldade intermediária, sendo ideal para cursos de Projeto e Análise de Algoritmos quando se inicia o tópico de PD. A intuição principal é perceber que uma abordagem gulosa falharia, pois não é possível fracionar os projéteis. A resolução exige Programação Dinâmica para explorar implicitamente as combinações viáveis. O estado ótimo dp[w] armazena o dano máximo atingível com peso w. Iterando sobre cada projétil e descendo o peso a partir da capacidade do canhão até o peso do item em questão, garante-se que cada projétil seja utilizado no máximo uma vez. A complexidade de tempo será O(N * K) e o espaço otimizado será O(K). Casos isolados ou capacidades insuficientes ficam automaticamente cobertos pela inicialização com zeros. For full implementation details, refer to the level-D statement. successmsg: Castelo destruído com sucesso! Excelente domínio na técnica de otimização de recursos! timeComplexity: O(N × M) timeLimitSegs: 1 memoryLimitMb: 256 defaultStatement: b_pt_canhao-de-destruicao.pdf skills: - dynamic-programming - knapsack-01 - dp-space-optimization statements: - id: a-canhao-de-destruicao testScenarioLevel: A thematicSkills: - skill: military points: 1 - skill: rpg-medieval points: 1 solutions: - id: a-otima-dinamica name: Ótima Dinâmica description: Solução utilizando Programação Dinâmica (Mochila 0/1) com complexidade O(N*K). level: A implementations: - language: py paradigm: Imperative filenames: - solucao.py - language: cpp paradigm: Imperative filenames: - solu.cpp - id: c-wrong-sliding-window name: Optimal Sliding Window (Incorreta) description: Solução legada incorreta usando sliding window (interval coverage). Falha em Knapsack 0/1. level: C implementations: - language: cpp paradigm: Imperative filenames: - a_optimal_sliding_window.cpp - language: java paradigm: Imperative filenames: - a_optimal_sliding_window.java - language: py paradigm: Imperative filenames: - a_optimal_sliding_window.py - id: c-wrong-brute-force name: Brute Force description: Solução legada em força bruta. Pode dar TLE e possui lógicas herdadas do problema antigo. level: C implementations: - language: py paradigm: Imperative filenames: - b_brute_force_cannon.py - id: c-wrong-greedy name: Estratégia Gulosa (Falha) description: Solução gulosa que ordena por densidade (Poder/Peso). Implementada propositalmente para validar o cenário c-greedy-fail. level: C implementations: - language: py paradigm: Imperative filenames: - solucao_gulosa.py testScenarios: - id: d-sample name: Amostras description: Exemplos do enunciado. level: D testType: TDD helpTip: "Verifique se a sua solução para o caso de exemplo considera a otimização exata em vez de gulosa." skills: - skill: dynamic-programming points: 1 - skill: knapsack-01 points: 1 - id: c-greedy-fail name: Falha Gulosa description: Casos onde a estratégia gulosa (maior valor ou maior densidade) falha. level: C testType: TDD_FALSE_GREEN helpTip: "Você ordenou os itens por custo-benefício? Cuidado, isso é um erro na mochila 0/1." skills: - skill: knapsack-01 points: 1 - id: b-edge-cases name: Casos de Borda description: Castelo muito forte, canhão com pouca capacidade ou apenas um item pesado. level: B testType: TDD helpTip: "O que acontece se a capacidade for muito baixa ou se nenhum item puder ser carregado?" skills: - skill: dynamic-programming points: 1 - id: b-fuzzing name: Testes Aleatórios description: Muitos testes curtos aleatórios para buscar heuristics hardcoded e falhas pontuais. level: B testType: TDD helpTip: "Sua lógica trata adequadamente quaisquer valores e reinicializa variáveis entre testes?" skills: - skill: dynamic-programming points: 1 - id: a-performance-load name: Teste de Carga Total description: Casos de teste com os limites máximos repetidos múltiplas vezes. level: A testType: PERFORMANCE helpTip: "Certifique-se de que a sua PD é O(N*K) e o espaço otimizado O(K)." skills: - skill: dynamic-programming points: 1 - skill: knapsack-01 points: 1 - skill: dp-space-optimization points: 1 thematicSkills: - military - rpg-medieval