1086-o-salao-do-clube

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "1.0" id: 1086 name: O Salão do Clube slug: o-salao-do-clube timelimit: 1.0 memlimit: 200 difficultyLevelId: C author: Ricardo Anido Brasil origin: Beecrowd description: 'O Clube Recreativo de Tinguá quer saber o menor número de tábuas de madeira necessárias para cobrir perfeitamente o piso retangular de seu novo salão, sem sobreposições ou sobras. As tábuas possuem a mesma largura, mas comprimentos diferentes, e podem ser emendadas no máximo uma vez para atingir a largura ou o comprimento do salão.' editorial: | Problema clássico de geometria discreta e algoritmos gulosos. Excelente para treinar o aluno a dividir o problema em casos independentes (orientação horizontal vs vertical) e parear elementos de forma eficiente usando Two Pointers. Estratégia: O salão deve ser coberto ou na horizontal ou na vertical. O número de fileiras necessárias será a dimensão do salão dividida pela largura da tábua. Para cada fileira, precisamos de uma tábua do tamanho exato ou duas tábuas que somem o tamanho exato. Use uma abordagem gulosa ordenando as tábuas e usando Two Pointers para tentar parear a maior tábua restante com a menor que a complete. Para detalhes completos de implementação, consulte o enunciado nível D. successmsg: 'Parabéns! Você pavimentou seu caminho com sucesso neste desafio!' timeComplexity: O(N logN) skills: - greedy-algorithms - arrays statements: - id: a-o-salao-do-clube testScenarioLevel: A thematicSkills: - skill: infrastructure points: 1 testScenarios: - id: a-performance name: Teste de Carga Máxima description: Validação do limite de tempo com as maiores restrições possíveis. helpTip: 'Para limites de 10^5 elementos, algoritmos O(N^2) darão "Time Limit Exceeded". Certifique-se de usar O(N log N).' level: A testType: PERFORMANCE skills: - skill: greedy-algorithms points: 2 - skill: arrays points: 1 - id: b-edge-impossible name: Casos Impossíveis description: Cenários onde a largura das fileiras não é divisível pela largura da tábua L. helpTip: 'O que acontece se a largura de L não encaixar perfeitamente nas dimensões M ou N do salão? Lembre-se que as tábuas não podem ser serradas longitudinalmente.' level: B testType: TDD skills: - skill: greedy-algorithms points: 1 - id: c-exact-boards name: Encaixes Perfeitos description: Tábuas fornecidas já têm o tamanho exato necessário para cobrir o salão. helpTip: 'Priorize as tábuas que sozinhas já possuem o tamanho da fileira.' level: C testType: TDD skills: - skill: arrays points: 1 - id: d-sample name: Exemplos do Enunciado description: Casos de teste presentes na descrição do problema. helpTip: 'Lembre-se de testar as duas orientações de piso possíveis (fileiras horizontais e fileiras verticais).' level: D testType: TDD skills: - skill: greedy-algorithms points: 1 solutions: - id: a-otima-basica name: Solução Ótima (Greedy / Two Pointers) description: Algoritmo guloso de complexidade O(K log K) que testa as duas orientações possíveis da sala. level: A implementations: - language: cpp paradigm: Imperative main: o-salao-do-clube.cpp filenames: - o-salao-do-clube.cpp - language: py paradigm: Imperative main: o_salao_do_clube.py filenames: - o_salao_do_clube.py - language: java paradigm: Imperative main: OSalaoDoClube filenames: - OSalaoDoClube.java - id: b-subotima-tle name: Solução Força Bruta O(K²) description: Algoritmo para testar TLE usando duplo loop ao invés de Two Pointers. level: B implementations: - language: cpp paradigm: Imperative main: o-salao-do-clube.cpp filenames: - o-salao-do-clube.cpp