Roteiro 3

De DCC UFMG - Maratona de Programação
Ir para: navegação, pesquisa

< Voltar para: Roteiros | Roteiro 2

Introdução

Neste roteiro, serão estudados três paradigmas de resolução de problemas. No primeiro, o da força-bruta, os problemas não possuem uma propriedade que torna fácil achar uma solução. Neste caso, uma possibilidade é enumerar todas as possíveis soluções e testá-las, uma a uma. Em outros casos, várias soluções com alguma semelhança podem ser descartadas em massa, o que faz surgir o segundo paradigma, o backtracking. O terceiro paradigma é o da Divisão e Conquista, aplicável em casos em que a solução para um problema pode ser construída a partir das soluções de dois ou mais problemas estritamente menores.

Em problemas de força-bruta, é comum que tenhamos que iterar por todos os subconjuntos de um determinado conjunto. Isto só pode ser feito, obviamente, quando o conjunto é pequeno. Tão pequeno que podemos representá-lo usando uma máscara de bits (bitmask). Esta técnica também será abordada nos problemas listados.

Materiais de apoio

Problemas

Lista de problemas para serem resolvidos. Os problemas em negrito são os mais importantes deste roteiro. Cada um precisa de um dos paradigmas sendo estudados. Recomendamos que resolva um total de, no mínimo, 6 dos problemas abaixo, incluindo os em negrito.

Roteiro 3
# Problema Link Online Judge Nível Observações
1 POPULAR Popularidade SPOJ-BR 1 Aquecimento
2 HEADSORTAILS Heads or Tails Codeforces 1
3 TRIANGLE Triangle Codeforces 1
4 Candy CANDY I SPOJ 1
5 CMIYC Catch Me If You Can SPOJ 1
6 UVa 639 Don't Get Rooked UVa 1
7 BANDA09 Banda SPOJ-BR 2 -
8 MEGADAMA MegaDamas SPOJ-BR 2 -
9 TESOUR11 Caça ao tesouro SPOJ-BR 2 -
10 ALLIZWEL ALL IZZ WELL SPOJ 2 -
11 DOMINO Dominó SPOJ-BR 2 -
12 ASSALTMG Assalto ao banco central SPOJ-BR 2 Bitmask
13 UVa 105 The Skyline Problem UVa 2 -
14 URI1522 Jogo das Pilhas URI 2
15 UVa 624 CD UVa 2
16 UVa 10344 23 Out of 5 UVa 2
17 JUNINA Festa Junina SPOJ-BR 3 -
18 INVCNT Inversion Count SPOJ 3 divisão e conquista
19 BALDES Baldes URI 3 Tente fazer em O(n).

Próximo roteiro

O próximo roteiro de treinamento tratará de outros dois paradigmas de resolução de problemas muito importantes: Programação Dinâmica e Algoritmos Gulosos. Recomendamos que você avance apenas depois de ler o material de apoio e ter feito, pelo menos, 6 problemas incluindo os 3 em negrito.

Link para o Roteiro 4

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas