2973-maratona-de-pipoca

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: '1.0' id: 2973 idBeecrowd: 2973 name: Maratona de Pipoca origin: sbc-2019 slug: maratona-de-pipoca authorSlugEditorial: alessio authorSlugProblem: sbc description: Neste problema, você precisará organizar uma equipe na Maratona Brasileira de Comedores de Pipoca. Dada uma sequência de sacos de pipoca e uma quantidade de competidores, o objetivo é descobrir o tempo mínimo possível para devorar todas as pipocas, sabendo que cada competidor consome uma quantidade limitada por segundo e só pode comer de sacos contíguos. editorial: "Este problema é excelente para introduzir ou consolidar os conceitos de Busca Binária aplicada na resposta e algoritmos\ \ gulosos. É necessário que o aluno já compreenda a mecânica da busca binária clássica e saiba iterar sobre vetores com\ \ simulações simples. O problema possui um nível intermediário (C) e encaixa-se muito bem em módulos de Paradigmas ou Algoritmos\ \ Eficientes.\r\n\r\nA grande sacada é inverter a pergunta: em vez de calcular diretamente o tempo, fixamos um tempo máximo\ \ X e verificamos de forma gulosa se a equipe consegue terminar o desafio. Dado X, um competidor come no máximo X * T pipocas.\ \ Iteramos sobre os sacos de pipoca agrupando-os até estourar esse limite, momento em que passamos para o próximo competidor.\ \ Se o número de competidores for no máximo C, o tempo X é possível. Por causa dessa monotonicidade (se X é possível, X+1\ \ também será), podemos usar uma Busca Binária na resposta entre o tempo 1 e a soma de todas as pipocas. Para a implementação\ \ completa e detalhes lógicos estruturados, consulte o enunciado de nível D. A complexidade final será O(N log S).\r\n" successmsg: Parabéns! Você provou que domina a estratégia ideal para maratonar pipocas com eficiência máxima! difficultyLevelId: C timeComplexity: O(N logN) timeLimitSegs: 1 defaultStatement: b_pt_maratona-de-pipoca.pdf skills: - binary-search - greedy-algorithms - logica statements: - id: a-maratona-de-pipoca testScenarioLevel: A thematicSkills: - skill: sports-leisure points: 1 testScenarios: - id: a-performance-load name: Desempenho e Carga Máxima description: Casos extremos com N=10^5 para forçar TLE em soluções não ótimas O(N^2). helpTip: Sua solução parece estar demorando muito. Verifique se você está usando Busca Binária na Resposta. level: A testType: PERFORMANCE skills: - skill: binary-search points: 1 - skill: greedy-algorithms points: 1 - id: b-fuzzing name: Testes Aleatórios Massivos description: Vários casos de teste gerados aleatoriamente para quebrar heurísticas fixas ou gulosos incorretos. helpTip: Seu código falhou em casos genéricos. Certifique-se de que a lógica gulosa na verificação da busca binária está correta. level: B testType: TDD skills: - skill: binary-search points: 1 - skill: greedy-algorithms points: 1 - id: c-edge-cases name: Casos Extremos e Limiares description: Casos com N=1, ou C >= N (onde o número de competidores é maior ou igual ao de sacos). helpTip: O que acontece quando há mais competidores do que sacos de pipoca? Verifique se seu limite inferior está configurado corretamente. level: C testType: TDD skills: - skill: binary-search points: 1 - skill: logica points: 1 - id: d-sample name: Exemplos do Enunciado description: Exemplos extraídos do enunciado do problema. helpTip: Você falhou nos exemplos fornecidos. Releia o enunciado. level: D testType: TDD skills: - skill: binary-search points: 1 - skill: greedy-algorithms points: 1 solutions: - id: a-otima-busca-binaria name: Solução Ótima com Busca Binária description: Algoritmo guloso acoplado com busca binária na resposta para complexidade O(N log S). level: A implementations: - filenames: - solucao.py language: py paradigm: Imperative - filenames: - solucao.cpp language: cpp paradigm: Imperative - filenames: - Solucao.java language: java paradigm: Imperative main: Solucao - id: b-busca-linear name: Solução Sub-ótima (Busca Linear) description: Algoritmo guloso com busca linear iterando de 1 até a soma total. Causa TLE devido à complexidade O(N * S). level: B implementations: - filenames: - busca_linear.cpp language: cpp paradigm: Imperative