2788-aula

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.5" id: 2788 name: "Aula" slug: "aula" timelimit: 1.0 memlimit: 200 difficultyLevelId: D author: "Gabriel Poesia, Brazil" origin: "Beecrowd" description: 'Encontre o menor múltiplo numérico adicionando até 6 dígitos nas extremidades de um número usando busca.' editorial: | Para encontrar o menor número que seja múltiplo de M (com M <= 200.000), podemos adicionar dígitos à esquerda e/ou direita de N. A sacada matemática é que como M <= 200.000, 10^6 = 1.000.000 > M. Isso garante que ao adicionar no máximo 6 dígitos apenas à direita, sempre será possível cobrir qualquer resto módulo M (pois 10^6 > M). Logo, sabemos que o número total de dígitos adicionados K será no máximo 6. Basta iterar o tamanho total adicionado K de 0 a 6. Para cada K, iterar o número de dígitos r adicionados à direita (de 0 a K), sendo l = K - r os adicionados à esquerda. Iterando o valor do prefixo L, podemos calcular em O(1) se há um sufixo R que zere a expressão módulo M. A primeira combinação encontrada (com menor K, e menor prefixo/sufixo) será o menor múltiplo procurado. successmsg: 'Incrível dedução! Perceber que o limite de M limita a quantidade máxima de dígitos a 6 e transformar numa busca em espaço de estados é coisa de Mestre!' timeComplexity: O(\min(10^K, 10^6)) skills: - math-computing - brute-force statements: - id: a-aula testScenarioLevel: A thematicSkills: - skill: math-computing points: 2 testScenarios: - id: a-performance name: Casos no Limite description: "Valores máximos de M (200.000) e N grandes." helpTip: "Você não conseguirá se usar BFS no espaço de strings infinitamente. Use a limitação matemática dos K <= 6 dígitos." level: A testType: PERFORMANCE skills: - skill: math-computing points: 1 - id: b-fuzzing name: Fuzzing description: "Casos variados de valores." helpTip: "Seu programa lida com todas as permutações de left/right?" level: B testType: TDD skills: - skill: brute-force points: 1 - id: c-edge name: Casos Edge description: "N já é múltiplo, ou adições apenas à esquerda." helpTip: "Você verificou K=0 primeiro?" level: C testType: TDD skills: - skill: math-computing points: 1 - id: d-sample name: Exemplos do Enunciado description: "Casos base do problema." helpTip: "N=1, M=2 resulta em 10." level: D testType: TDD skills: - skill: basic-io points: 1 solutions: - id: a-otima-basica name: Busca Limitada por K description: O(10^6) com K <= 6. level: A implementations: - language: cpp paradigm: Imperative main: aula.cpp filenames: - aula.cpp - language: py paradigm: Imperative main: aula.py filenames: - aula.py - language: java paradigm: OO main: Aula filenames: - Aula.java authorSlugProblem: Unknown defaultStatement: a-aula