2487-do-lado-escuro-do-codigo

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.5" id: 2487 name: "Do Lado Escuro do Código" slug: "do-lado-escuro-do-codigo" timelimit: 1.0 memlimit: 200 difficultyLevelId: B author: "Enzo M. G. Vespe" origin: "Beecrowd" description: 'Aloque potências de 2 para priorizar tarefas dadas as restrições rigorosas de Matemática Gulosa.' editorial: | Dado um tempo T e A atividades em ordem decrescente de importância, o objetivo é alocar potências de 2 para as atividades com uma priorização gulosa (greedy), garantindo que toda atividade receba pelo menos 1 minuto e que a soma das alocações atinja T exato. O resto vai para a Atividade 1. A estratégia gulosa ótima consiste em iterar das atividades `i` = 1 até A. Para cada atividade, calculamos o máximo de tempo "livre" que a atividade atual pode gastar, assegurando que sobrem pelo menos (A - i) minutos para as (A - i) atividades que faltam (pois cada uma exige pelo menos 1 min). O tempo livre será `T_livre = T - (A - i)`. O ideal para esta atividade é a MAIOR potência de 2 que seja <= T_livre. Nós decrescemos T pela potência atribuída e prosseguimos. Ao fim de iterar todas, se ainda houver sobrado tempo em T, o resto inteiro é inteiramente transferido de volta para a Atividade 1. Essa lógica preenche as atividades validamente e garante a distribuição correta. successmsg: 'Isso é Matemática Gulosa (Greedy) pura! Encontrar a máxima potência de 2 factível para garantir o melhor proveito e respeitar restrições globais é o coração de dezenas de algoritmos gulosos incríveis.' timeComplexity: O(A) skills: - greedy - math-computing statements: - id: a-escuro testScenarioLevel: A thematicSkills: - skill: greedy points: 1 - skill: math-computing points: 1 testScenarios: - id: a-performance name: Carga Long Limit description: "T chegando a 10^18. Impede complexidades exponenciais e tipos de inteiros menores." helpTip: "Você usou inteiro 64-bits (`long long` / `long`) para as potências de 2 e o limite de tempo?" level: A testType: PERFORMANCE skills: - skill: math-computing points: 1 - id: b-fuzzing name: Resto Variado description: "Casos em que resta 0, resta grande quantidade." helpTip: "O tempo de resto que sobrava ao fim de todas as atribuições foi somado integralmente à atividade 1?" level: B testType: TDD skills: - skill: greedy points: 1 - id: c-edge name: Casos Limite description: "T = A, ativando limite de 1 para cada." helpTip: "Você garantiu que nenhuma das A atividades levasse tempo 0?" level: C testType: TDD skills: - skill: logic points: 1 - id: d-sample name: Exemplo do Enunciado description: "Casos de teste base." helpTip: "Passe o exemplo." level: D testType: TDD skills: - skill: basic-io points: 1 solutions: - id: a-otima-basica name: Atribuição Gulosa de Potências description: Distribui maiores potências possíveis subtraindo espaço das seguintes em O(A). level: A implementations: - language: cpp paradigm: Imperative main: escuro.cpp filenames: - escuro.cpp - language: py paradigm: Imperative main: escuro.py filenames: - escuro.py - language: java paradigm: OO main: Escuro filenames: - Escuro.java authorSlugProblem: Unknown defaultStatement: a-escuro