0748-navalha-batal

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: '1.0' id: 748 name: Navalha Batal origin: mineira-2019 slug: navalha-batal authorSlugEditorial: alessio authorSlugProblem: alessio description: Dado um tabuleiro N × N com Q células inicialmente ocupadas, calcule quantos bavios de tamanho 1×T ou T×1 ainda podem ser inseridos sem sair do tabuleiro e sem sobreposição com as células já preenchidas, considerando todas as posições possíveis diferentes. editorial: A solução típica consiste em varrer linhas e colunas, considerando os segmentos contíguos de células livres entre posições ocupadas, e somar para cada segmento o número de posições válidas em que um bavio 1×T ou T×1 pode ser encaixado. Como N pode chegar a 10^6 e Q a 10^5, é necessário representar as casas ocupadas de forma esparsa, ordenando por linha e por coluna e tratando os intervalos entre ocupadas e as bordas do tabuleiro. successmsg: Parabéns! Você ajudou a Bibika a calcular corretamente todas as posições possíveis dos bavios em um tabuleiro gigante. difficultyLevelId: C timeComplexity: O(N) spaceComplexity: O(1) timeLimitSegs: 2 memoryLimitMb: 256 defaultStatement: b_pt_navalha-batal skills: - io - lacos - matrizes - vetores statements: - id: a-navalha-batal testScenarioLevel: A thematicSkills: - points: 1 skill: jogos - id: a-estacionamento-espacial testScenarioLevel: A thematicSkills: - points: 1 skill: sci-fi - points: 1 skill: matematica testScenarios: - id: a-matriz-gigante-tle name: Congestionamento Abissal description: Limite de complexidade pura. N em 1 milhão e Q no extremo 100 mil obstáculos dispostos caoticamente. Inviabiliza alocação de tabela N*N. helpTip: Alocar uma grade N x N causará instabilidades críticas e lentidão da sua memória. Como extrair o espaço inerte saltando dinamicamente coordenadas listadas? level: A testType: TDD skills: - points: 1 skill: complexity-analysis - points: 1 skill: ordenacao - id: a-padroes-alinhados name: Destroços em Fileiras description: Traz detritos que compartilham o mesmo eixo longitudinal (uma só linha densa). Desmistifica complexidade algoritmica acidental do competidor. helpTip: Como a fórmula deve se comportar num eixo cujos limites sequenciais foram cortados por detritos da ponte à popa na mesma exata travessia? level: A testType: TDD skills: - points: 1 skill: advanced-data-structures - points: 1 skill: basic-logic - id: b-tabuleiro-denso name: Fatias densamente populosas description: Validar a capacidade de separar os espaços livres contíguos de maneira lógica quando obstáculos formam estreitas frestas independentes. helpTip: Itere cuidadosamente nas listas contendo as coordenadas. Sua pontuação se deve subtrair a fragmentação correta dos espaços vizinhos. level: B testType: TDD skills: - points: 1 skill: vetores - points: 1 skill: lacos - id: c-pequenos-depuracao name: Depuração de Casos Pequenos description: Conjunto de testes manuais e extremamente pequenos para facilitar a depuração lógica sem a complexidade de grandes volumes de dados. helpTip: Use estes casos para verificar se a sua lógica de contagem de peças 1x1 está correta e se não há sobreposição indevida. level: C testType: TDD skills: - points: 1 skill: basic-logic - id: c-tabuleiro-vazio-overflow name: Galáxia Fantasma Deserta description: Limite diametral oposto; testar tabuleiro nas medidas máximas sem absolutamente NENHUM obstáculo Q. Provoca Integer Overflow facilmente. helpTip: Se os espaços chegam na dimensão astronômica e todos esvaziados, seu totalizador numérico cabe num primitivo 'int'? É hora de estender o tamanho dos bits em suas varíaveis. level: C testType: TDD skills: - points: 1 skill: variaveis - points: 1 skill: abstracao-matematica - id: d-sample name: Exemplos do Tutorial Base description: Validar a lógica fundamental e a consistência basilar usando os exemplos ilustrativos descritos no enunciado. helpTip: Verifique os seus cálculos manuais com o enunciado. Você garantiu que naves bloqueadas ou peças cruzadas de área unitária (1x1) não constem no cálculo duplicadamente? level: D testType: TDD skills: - points: 1 skill: entrada-saida - points: 1 skill: basic-logic solutions: - id: a-optimal name: Solução Ótima (C++/Java) description: Implementação eficiente utilizando representação esparsa com mapas e conjuntos, garantindo complexidade O(N + Q log Q). level: A implementations: - filenames: - solution.cpp language: cpp paradigm: Imperative main: main - filenames: - Solution.java language: java paradigm: Imperative main: main - id: b-tle name: Solução Ingênua (Python) description: Implementação utilizando matriz densa O(N²). Funciona para entradas pequenas, mas excede limite de tempo e memória nos casos de teste maiores. level: B implementations: - filenames: - batal.py language: py paradigm: Imperative main: main - id: d-incorrect name: Solução Incorreta (Java) description: Implementação incompleta que utiliza matriz densa e falha ao contar bavios de tamanho maior que 2. level: D implementations: - filenames: - Navalha.java language: java paradigm: Imperative main: main