2880-enigma

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.5" id: 2880 name: "Enigma" slug: "enigma" timelimit: 1.0 memlimit: 1024 difficultyLevelId: B author: "Maratona de Programação da SBC 2018 Brazil" origin: "Beecrowd" description: 'Encontre o número de posições possíveis para um crib em uma mensagem cifrada da máquina Enigma.' editorial: | A vulnerabilidade da máquina Enigma era que uma letra nunca era substituída por ela mesma. Para resolver o problema, basta iterarmos por todas as posições possíveis de encaixe da palavra (crib) na mensagem cifrada. Uma posição `i` é válida se, para todo `j` de 0 até o tamanho do crib - 1, a letra da mensagem na posição `i + j` for diferente da letra do crib na posição `j`. O tamanho máximo da mensagem é 10^4. O número máximo de operações é no pior caso (10^4) * (10^4) = 10^8, o que roda confortavelmente dentro de 1 segundo em linguagens compiladas, caracterizando uma solução O(N * M) baseada em simulação/strings. successmsg: 'Força bruta simples e eficiente! A vulnerabilidade da Enigma que Alan Turing usou na Segunda Guerra recriada com sucesso.' timeComplexity: O(|M| \times |C|) skills: - strings - brute-force statements: - id: a-enigma testScenarioLevel: A thematicSkills: - skill: strings points: 2 testScenarios: - id: a-performance name: Carga Máxima O(N^2) description: "Strings de 10.000 caracteres de As e um crib longo de As e Bs." helpTip: "Você manteve seus laços o mais simples possível para não tomar TLE no Python?" level: A testType: PERFORMANCE skills: - skill: strings points: 1 - id: b-fuzzing name: Casos Aleatórios description: "Mensagens e cribs aleatórios." helpTip: "Casamento de padrão sem matching exato." level: B testType: TDD skills: - skill: brute-force points: 1 - id: c-edge name: Casos Extremos description: "Crib do tamanho exato da mensagem." helpTip: "Você iterou até o final exato do limite?" level: C testType: TDD skills: - skill: strings points: 1 - id: d-sample name: Exemplo description: "Exemplo clássico do enunciado." helpTip: "Passe o exemplo." level: D testType: TDD skills: - skill: basic-io points: 1 solutions: - id: a-otima-basica name: Busca Linear de Padrão description: Testa todos os alinhamentos sem match de mesmos caracteres. level: A implementations: - language: cpp paradigm: Imperative main: enigma.cpp filenames: - enigma.cpp - language: py paradigm: Imperative main: enigma.py filenames: - enigma.py - language: java paradigm: OO main: Enigma filenames: - Enigma.java authorSlugProblem: Unknown defaultStatement: a-enigma