1385-recuperacao-de-relatorio

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.5" id: 1385 name: "Recuperação de Relatório" slug: "recuperacao-de-relatorio" author: "Rodrigo Cardoso, Brasil" origin: "Beecrowd 1385" timelimit: 1.0 memlimit: 200 difficultyLevelId: C description: "Recuperação de relatório tabular através de Backtracking e particionamento de strings." editorial: | Este problema exige uma busca combinatória (Backtracking). O objetivo é inserir espaços em strings coladas para recuperar N colunas mais o Total. A primeira parte consiste em gerar todas as partições válidas de (N+1) números para cada vendedor, onde a soma dos N primeiros seja igual ao (N+1)-ésimo, sem zeros à esquerda e garantindo que os produtos sejam < 1000. Em seguida, uma segunda fase de DFS (ou Backtracking Global) cruza as possíveis escolhas de cada vendedor e verifica se os somatórios verticais geram exatamente a string `TP` lida. successmsg: "Brilhante! O uso de Backtracking aninhado com validação por Parsing String é de nível sênior em competições." timeComplexity: O(K \cdot 3^{N+1}) skills: - backtracking - strings - simulation statements: - id: a-recuperacao testScenarioLevel: A thematicSkills: - skill: strings points: 1 - skill: backtracking points: 2 testScenarios: - id: a-performance name: DFS Completa description: "Multiplos vendedores com múltiplas sub-partições." helpTip: "Você limitou a busca em 3 digitos para os produtos N?" level: A testType: PERFORMANCE skills: - skill: backtracking points: 1 - id: b-fuzzing name: Casos Diversos description: "Strings com zeros consecutivos." helpTip: "Atenção: '00' é inválido, '0' é válido." level: B testType: TDD skills: - skill: strings points: 1 - id: c-edge name: Extremidades description: "Único vendedor ou zeros em massa." helpTip: "O que acontece se um vendedor tem o total como 0?" level: C testType: TDD skills: - skill: logic points: 1 - id: d-sample name: Exemplo description: "Casos base do problema." helpTip: "Passe." level: D testType: TDD skills: - skill: strings points: 1 solutions: - id: a-otima-basica name: Backtracking Duplo (Vendedores e Global) description: Algoritmo resolvendo particionamento primeiro por linha e depois globalmente. level: A implementations: - language: cpp paradigm: Imperative main: recuperacao.cpp filenames: - recuperacao.cpp - language: py paradigm: Imperative main: recuperacao.py filenames: - recuperacao.py - language: java paradigm: OO main: Recuperacao filenames: - Recuperacao.java authorSlugProblem: Unknown defaultStatement: a-recuperacao