Roteiro 10

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

< Voltar para: Roteiros | Roteiro 9

Introdução

Este roteiro é uma introdução a Teoria dos Números e a Análise Combinatória. Estes temas não são tão comuns em competições mas geralmente caem. Saber identificar o problema, e conseguir reduzir este problema a algum algoritmo conhecido em Teoria dos Números ou em combinatória é um ponto forte para um bom competidor.

Materiais de Apoio

O primeiro artigo é uma introdução modesta ao universo da Teoria dos Números. Os artigos referentes a aritmética modular, algoritmo euclidiano estendido, os teoremas (Fermat e Euler) e o Teorema Chinês do Resto são de grande importância em Teoria dos Números. O último artigo faz um apanho geral em introdução a análise combinatória, o que basta para o ponto que estamos.

Problemas

Lista de problemas para serem resolvidos. A solução está disponível, mas recomendamos que não a consulte antes de muito esforço. os problemas de aquecimento (rosa) não necessariamente são de teoria dos números mas servem para um bom aquecimento.

Roteiro 10
# Problema Link Online Judge Nível Observações
1 BICHO Jogo do bicho SPOJ-BR 1
2 COMCAMEL Comércio de Camelos SPOJ-BR 2
3 CALCADMG Caminhando pela calçada SPOJ-BR 2
4 FATORIAL Fatorial SPOJ-BR 2
5 UVa 10079 Pizza Cutting UVa 1
6 MIOJO Miojo SPOJ-BR 2
7 UVa 756 Biorhythms UVa 3 Teorema chinês do resto
8 UVa 10090 Marbles UVa 2
9 DIOFANTO Equações diofantinas SPOJ-BR 3
10 UVa 12493 Stars UVa 3
11 URI1022 TDA Racional URI 1 MDC
12 URI1028 Figurinhas URI 1 MDC
13 ONZE ONZE SPOJ-BR 1 Critério de divisibilidade
14 UVa 1480 Almost Prime Numbers UVa 2 Números primos
15 PRIME1 Prime Generator SPOJ 2 Números primos

Próximo Roteiro

O próximo roteiro de treinamento tratará de problemas que utilizam estruturas de dados mais complicadas, como a Árvore de Segmentos. Recomendamos que você avance apenas depois de ler todo o material de apoio e ter feito, pelo menos, 6 problemas incluindo os 2 em negrito.

Link para o Roteiro 11

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas