0644-desmascarando-o-empregado-do-sultao

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.4" id: 644 name: Desmascarando o Empregado do Sultão slug: desmascarando-o-empregado-do-sultao timeLimitSegs: 2.0 difficultyLevelId: H author: Unknown origin: Desconhecida description: | Dado um conjunto de relatórios contendo o horário de início, horário de término e a quantidade de cada tarefa realizada, descubra a duração única de cada tarefa se possível, ou acuse se o empregado mentiu. editorial: | **Briefing para o Professor:** Este é um problema de Álgebra Linear sobre Corpos Finitos (F_p), muito comum em níveis avançados de maratona (ICPC). Cada relatório pode ser modelado como uma equação linear modular. A duração informada num relatório, pelo enunciado de "Jornadas de P horas", equivale a `D = (T_i - S_i + 1) mod P`. Com N relatórios para N tarefas, forma-se um sistema `M * X = D (mod P)`. **Estratégia de Resolução:** A solução se baseia no algoritmo de Eliminação de Gauss (Gaussian Elimination) operando em aritmética modular (módulo $P$, que é garantidamente primo). - Construímos uma matriz `N x (N + 1)` onde os coeficientes são `A_{i,j} mod P`. - Escalonamos a matriz utilizando o Inverso Modular (Fermat's Little Theorem: `X^{P-2} mod P`) ao invés de divisões float. - Após o escalonamento, se alguma linha for `0 = K` (K != 0), o sistema tem contradição (-1). - Se o Posto (Rank) do sistema for menor que N, há múltiplas soluções (-2). - Caso contrário, resolvemos com Back-Substitution (Retro-substituição). Se alguma variável der `0`, como o domínio da duração é `1..P`, sabemos que ela equivale a `P`. successmsg: 'Sherlock dos números! Você desmascarou o sultão com perfeição algébrica.' timeComplexity: O(N^3) skills: - math-algebra - arrays statements: - id: a-desmascarando-o-empregado-do-sultao testScenarioLevel: A thematicSkills: - skill: history points: 1 testScenarios: - id: a-performance name: Sistemas Aleatórios Grandes description: "Sistemas lineares de N=20 variáveis gerados e calculados." helpTip: "Você usou Inverso Modular pelo Pequeno Teorema de Fermat nas divisões do Escalonamento?" level: A testType: PERFORMANCE skills: - skill: math-algebra points: 2 - id: b-edge-cases name: Contradições Óbvias description: "Relatórios impossíveis que forçam a inconsistência matricial (-1)." helpTip: "Seu escalonamento detectou linhas nulas com termo independente não-nulo?" level: B testType: TDD skills: - skill: math-algebra points: 1 - id: c-basic name: Múltiplas Soluções description: "Sistema linear dependente (posto menor que N), resultando em -2." helpTip: "O que acontece se uma linha for o dobro da outra?" level: C testType: TDD skills: - skill: math-algebra points: 1 - id: d-sample name: Exemplos do Enunciado description: "Os 3 exemplos exatos da descrição do problema." helpTip: "Você está lidando corretamente com os tempos S_i e T_i? A duração D = (T_i - S_i + 1) mod P." level: D testType: TDD skills: - skill: math-algebra points: 1 solutions: [] authorSlugProblem: desconhecida defaultStatement: a-desmascarando-o-empregado-do-sultao