Autor: Lawrence Melo

Para este problema vamos usar uma ideia parecida com o algoritmo de Dijsktra (Menor caminho). Podemos considerar que o mapa da prisão é um grafo, onde cada aresta liga apenas elementos ao norte, sul, leste ou oeste, e o peso de cada aresta é $$0$$ ou $$1$$. $$0$$ quando $$map[x_1][y_1] = map[x_2][y_2]$$ e $$1$$ caso…

Para esse problema usaremos o algoritmo de troco. Defina $$dp[m]$$ como o número mínimo de tacadas para se chegar à distância $$m$$ e $$taco[i]$$ como a distância do i-ésimo taco. Então, $$dp[m] = \begin{cases} 0 & ,\mbox{se m = 0} \\ \min\limits_{0 \leq i < N}( dp[m – taco[i]] + 1) & , \mbox{caso m…

Note que se $$gcd(a, b) \neq 1$$ então $$a$$ e $$b$$ possuem algum fator primo em comum. Usando o fato de que entre $$1$$ e $$N$$ um número $$p$$ divide exatamente $$\frac{N}{p}$$ (divisão inteira) números. Então, podemos calcular o conjunto $$P$$ de primos que dividem $$N$$ e depois somamos todas as divisões inteiras para cada…

Para esse problema usaremos a ideia de soma de prefixos, ou soma acumulada, do vetor $$v$$. A ideia é, guardamos um vetor $$pref[N]$$, onde $$pref[i]$$ significa a soma de todas as posições de $$v$$ de $$1$$ até $$i$$. Por exemplo, se $$v = {1, 2, 3, 4, 5}$$ então $$pref[3] = 1 + 2 +…

A Árvore Seja uma árvore um grafo conexo sem ciclos que contém $$n$$ vértices. Você ganha de presente uma árvore especial. Nesta árvore, as $$n-1$$ arestas estão coloridas ou em preto ou em vermelho. Você ainda recebeu um inteiro $$k$$ de presente! Considere todas as sequências de $$k$$ vértices. Vamos chamar uma sequência $$[a_1, a_2,…