Roteiro 2

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

< Voltar para: Roteiros | Roteiro 1

Introdução

Estudaremos neste roteiro as estruturas de dados básicas, que são utilizadas com grande frequência nos mais diversos problemas. É necessário compreender as características e o comportamento de todas as estruturas básicas para então conseguir utilizá-las com eficácia. Introduzimos também a STL (Standard Template Library) de C++, que possui implementações dessas estruturas e facilita enormemente o trabalho de codificar a solução para um problema. A biblioteca padrão de Java também inclui estruturas equivalentes às que vamos citar da STL de C++.

Finalmente, visamos introduzir um paradigma simples e poderoso de Divisão e Conquista: a busca binária, inicialmente apenas usada para localizar elementos em um vetor ordenado. Os outros paradigmas serão melhor trabalhados no próximo roteiro. Futuramente, você verá também usos mais gerais do princípio da busca binária.

Materiais de apoio

Problemas

Lista de problemas para serem resolvidos. A única dificuldade de todos os problemas listados é encontrar a função/estrutura de dados certa implementada na STL que torna o problema fácil de ser implementado. Ainda assim, a solução está disponível, mas recomendamos que não a consulte antes de tentar o bastante. Dê uma olhada na referência passada nos materiais de apoio deste roteiro para encontrar o que você procura. Os problemas em negrito são os mais importantes deste roteiro. Recomendamos que resolva um total de, no mínimo, 7 dos problemas abaixo, incluindo os em negrito. O problema em rosa é aquecimento, seria muito bom que o fizesse primeiro.

Roteiro 2
# Problema Link Online Judge Nível Observações
1 PALAVRMG Palavras Ordenadas SPOJ-BR 0 tolower()
2 BRACELMG Braceletes Mágicos SPOJ-BR 1 Aquecimento - implementação simples com std::string
3 PKU_2388 Who's in the Middle PKU 1 use std::sort()
4 TENTA Brincadeira das Tentativas SPOJ-BR 1 use std::next_permutation
5 IMPEDIDO Ele está impedido SPOJ-BR 1 use std::sort()
6 PLACAR Quem vai ser reprovado SPOJ-BR 1 use std::sort() com função de ordenação
7 Live Archive 5060 Arm Wrestling Tournament SPOJ-BR 1 Use uma fila
8 BSEARCH1 Binary Search SPOJ 1 Busca binária
9 URI1228 Grid de Largada URI 1 Ordenação
10 ALIENSMG Alienígenas SPOJ-BR 1 -
11 SUMFOUR 4 values whose sum is 0 SPOJ 1 Lower/Upper bounds
12 URI1260 Espécies de Madeira URI 2 -
13 HAMSTER1 Hamster flight SPOJ 2 -
14 ELEICOES Eleições SPOJ-BR 2 -
15 JASPION O Fantástico Jaspion! SPOJ-BR 2 -
16 SENHA Proteja sua senha SPOJ-BR 2 resolva usando sets
17 TROCCARD Troca de Cartas SPOJ-BR 2 -
18 FUTEBOL Futebol SPOJ-BR 2 sim, output chato!
19 MARIO Mário SPOJ-BR 2 busca binária
20 Triangulos Triangulos URI 2 Busca binária

Próximo roteiro

O próximo roteiro de treinamento tratará dos paradigmas de resolução de problemas. Recomendamos que você avance apenas depois de ler o material de apoio e ter feito, pelo menos, 7 problemas incluindo os 2 em negrito.

Link para o Roteiro 3

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas