1205-cerco-a-leningrado

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.2" id: 1205 name: Cerco a Leningrado slug: cerco-a-leningrado idBeecrowd: 1205 timeLimitSegs: 3.0 difficultyLevelId: D author: Marcio T. I. Oshiro, USP Brasil origin: Beecrowd description: | Durante a Segunda Guerra Mundial, a cidade de Leningrado sofreu um cerco brutal das tropas alemãs. Atiradores de elite foram espalhados por pontos estratégicos da cidade, e um soldado soviético deseja cruzar a cidade partindo de um ponto de origem até um ponto de destino. Ele possui uma quantidade limitada de balas e uma probabilidade fixa de acertar cada tiro. O soldado deve abater todos os atiradores no caminho que escolher, sem errar nenhum disparo. Sua missão é determinar qual rota maximiza a probabilidade de o soldado completar a travessia com sucesso. editorial: | **Briefing para o Professor:** Este problema exige que o aluno domine o algoritmo de Dijkstra aplicado a grafos com custos nos vértices (e não nas arestas), além de compreender a composição de probabilidades independentes. É um excelente exercício para cursos de Teoria dos Grafos em nível intermediário-avançado, pois obriga o aluno a reformular o conceito clássico de "menor caminho" de uma soma de pesos para um produto de probabilidades. Recomendado como problema de fechamento do módulo de Dijkstra, após o aluno já ter resolvido instâncias canônicas com custos nas arestas. **Estratégia de Resolução:** A sacada central é perceber que maximizar P^T (onde T é o total de atiradores no caminho) equivale a minimizar T, já que P está em [0,1]. Assim, o problema se reduz a um Dijkstra clássico onde o "peso" de cada vértice é a quantidade de atiradores nele posicionados. Constrói-se o grafo com N nós e M arestas bidirecionais, conta-se os atiradores por nó, e executa-se Dijkstra com custo nos vértices (dist[origem] = snipers[origem], relaxamento: dist[v] = dist[u] + snipers[v]). Se a distância mínima T até o destino exceder K balas ou o destino for inalcançável, a resposta é 0.000. Caso contrário, a resposta é P^T formatada com 3 casas decimais. Complexidade: O((N+M) log N). Para detalhes completos de implementação, consulte o enunciado nível D. successmsg: 'Vitória! Você cruzou Leningrado com maestria — minimizar atiradores para maximizar a sobrevivência é puro Dijkstra aplicado!' timeComplexity: O((N+M) log N) skills: - dijkstra - shortest-path - math-computing statements: - id: a-cerco-a-leningrado testScenarioLevel: A thematicSkills: - skill: military points: 1 - skill: history points: 1 testScenarios: - id: a-performance name: Carga Pesada (N=1000, M grande) description: "Grafo denso com muitos atiradores espalhados." helpTip: "Sua fila de prioridade (min-heap) está processando eficientemente? Custo deve estar nos vértices, não nas arestas." level: A testType: PERFORMANCE skills: - skill: dijkstra points: 1 - id: b-edge-cases name: Casos Limites description: "Origem e destino iguais, K=0, P=0 ou P=1, grafos desconexos." helpTip: "Lembre-se: se origem == destino, o soldado ainda precisa abater os atiradores no próprio nó. E se P=0 com atiradores, a resposta é 0.000." level: B testType: TDD skills: - skill: shortest-path points: 1 - id: c-probabilidade name: Cálculo de Probabilidade description: "Verificação da exponenciação P^T e formatação com 3 casas decimais." helpTip: "Você está usando pow(P, T) corretamente? Cuidado com a formatação: printf('%.3f', ans)." level: C testType: TDD skills: - skill: math-computing points: 1 - id: d-sample name: Exemplo do Enunciado description: "Exemplos base fornecidos no problema." helpTip: "Passe os exemplos básicos do enunciado." level: D testType: TDD skills: - skill: dijkstra points: 1 solutions: [] authorSlugProblem: Unknown defaultStatement: a-cerco-a-leningrado