A versão em PDF foi corrigida, e os problemas estão disponíveis no SPOJ BRASIL.
| Problema | Nome | Nível | Método |
|---|---|---|---|
| A | Recuperação | Fácil | Leitura e impressão |
| B | Quem vai ser reprovado? | Fácil | Busca |
| C | Não é Mais um Joguinho Canadense! | Fácil-Médio | Contagem |
| D | Cardápio da Sra. Montagny! | Médio-Difícil | 2-Sat |
| E | Mesa da Sra. Montagny! | Fácil-Médio | Busca em grafos |
| F | Sistema Cipoviário | Médio | Árvore geradora mínima |
| G | Números de Dinostratus | Médio | Fatoração |
| H | Final Mundial de 2008 | Fácil-Médio | Caminhos mínimos com várias origens |
| I | Construtores de Totens | Médio-Difícil | Busca de padrões |
| J | A lei vai a Cavalo! | Difícil | Fluxo máximo |
| L | Fatorial | Médio | Fatoração |
| M | Demonstração de honestidade! | Difícil | Intersecção de matróides |
Para resolver este problema não era preciso nenhum conhecimento avançado. A tarefa consiste em pegar a seqüência de inteiros da entrada e ir somando até que um elemento lido seja igual a soma atual.
leia n soma = 0 para i = 0 até n leia k se soma = k e está é a primeira vez que soma = k entao imprima k
Nível: Fácil.
Pratique: https://br.spoj.pl/problems/RECUPERA
Este problema é fácil mas exige um pouco de conhecimento da linguagem de programação usada para resolvê-lo.
A solução mais comum foi: Ordenar uma estrutura de dados, criada com os dados dos alunos, e imprimir o primeiro elemento.
Entretanto existe um jeito mais simples de executar esta tarefa criando uma variável que guarda o nome do aluno com menor pontuação, e outra que guarda a pontuação. Para toda linha basta alterar as variáveis quando, ou a pontuação do aluno lido é menor, ou a pontuação é igual mas o nome vem depois na ordem alfabética.
Nível: Fácil.
Pratique: https://br.spoj.pl/problems/PLACAR
Para resolvermos este problema temos que encontrar uma função que mapeia uma palavra para um número, onde este número deve ser a soma dos custos dos passeios distintos que possuem o rótulo igual a palavra.
Vamos criar tal função. Seja w uma palavra de comprimento n. Sejam b1, b2, .., bk índices tais que w[bi] = b para i=1,2,..,k. Pelo grafo temos que existem k passeios distintos que iniciam no vértice p e terminam no vértice q, pois o número de passeios distintos é igual ao número de letras b na palavra (Verifique!). Considere o índice bi e suponha que usamos a transição (p, 1b) que vai de p para q usando w[bi]. O custo de w[1..bi] é 1 (Verifique!). A única transição que pode ser usada pelas letras de w[bi+1..n] é (q, 2a) com término em q e (q, 2b) também com término em q. Daí segue que o custo deste passeio é 1 * 2n-bi. Logo a soma dos pesos de todos os passeios é 2n-b1 + 2n-b2 + ... + 2n-bk.
Nível: Fácil-Médio.
Pratique: https://br.spoj.pl/problems/CONTAGEM
Cada convidado pode escolher duas comidas, vetar duas, ou escolher uma e vetar outra. O importante é que cada desejo (ou cláusula) tem duas variáveis e uma operação de ou. Neste problema, queremos satisfazer pelo menos um dos desejos de cada candidato.
Este é um problema clássico chamado 2-Sat que pode ser resolvido em tempo linear (no número de cláusulas). O ponto chave para resolver este problema é ver que: a OU b pode ser trocado por duas cláusulas: !a implica b e !b implica a. Como queremos garantir que pelo menos um dos desejos seja satisfeito, se !a acontece então temos que forçar a seleção do b e vice-versa. Vamos construir um grafo, onde o conjunto dos vértices é formado pelas literais e suas negações e o conjunto das arestas é formado pelas restrições de implica que podem ser obtida de cada cláusula da entrada. Caso exista um caminho que vai de uma literal, digamos a, a sua negação !a, e um caminho da negação para a respectiva literal então não é possível satisfazer as cláusulas pois o conjunto de cláusulas gera uma contradição. Então basta verificar se existe uma componente fortemente conexa que contém uma literal e sua negação, se houver tal componente então não é possível satisfazer as cláusulas da entrada, caso contrário é possível.
Nível: Médio-Difícil.
Pratique: https://br.spoj.pl/problems/CARDAPIO
Referências:
Este é outro problema clássico de Teoria de Grafos. Dado um grafo G, onde o conjunto de vértices é formado pelos convidados e o conjunto de arestas é formado pelas relações de amizade, determine se G é bipartido.
Nível: Fácil-Médio.
Pratique: https://br.spoj.pl/problems/MESA
Neste problema queremos encontrar uma árvore geradora mínima do grafo
formado pelos pontos e cipós. Como existe apenas 3 pesos distintos
então podemos facilmente escrever um algoritmo de ordenação que
consome tempo linear. Como era possível e fácil escrever tal
algoritmo, os copy and paste do Algoritmo de Kruskal que
utilizavam ordenação em tempo O(mlgm), onde m é o número de
arestas, recebeu "No - Time Limit".
Fica a lição, para aqueles que receberam "Time Limit" e não conseguiram arrumar suas soluções, de que não basta apenas saber digitar o algoritmo. Conhecer e saber fazer pequenas adaptações é fundamental.
Nível: Médio.
Pratique: https://br.spoj.pl/problems/CIPO
Referência:
Neste problema queremos preencher a matriz de dinostratus com 9 divisores do número n. Tome os fatores primos de n:
2a * 3b * 5c * 7d... onde 0 <= a, b, c, d, ...
Pense na matriz preenchida com eles. Por exemplo:
Para n = 36
| 20 * 30 = 1 | 21 * 30 = 2 | 22 * 30 = 4 |
| 20 * 31 = 3 | 21 * 31 = 6 | 22 * 31 = 12 |
| 20 * 32 = 9 | 21 * 32 = 18 | 22 * 32 = 36 |
Agora vamos pensar no caso geral. Se tivermos pelo menos dois fatores com expoentes maior igual a 2 é possível preencher a matriz? (Verifique!) Se tivermos 1, 2, 3, 4, 5 ... fatores distintos, precisamos que o maior expoente entre os fatores seja pelo menos? (Verifique!)
Pratique: https://br.spoj.pl/problems/DINOSTRA
Para resolver este problema basta implementar o Algoritmo de Floyd-Warshall. Leia a seção 25.2 em - O Algoritmo de Floyd-Warshall do livro do CLRS e atente-se para explicação de como o algoritmo de Floyd-Warshall funciona.
Ps. Não adianta apenas saber digitar um algoritmo.
Nível: Fácil-Médio
Pratique: https://br.spoj.pl/problems/MINIMO
Referência:
Neste problema queremos encontrar um padrão MxM em um texto NxN. Temos que M <= 60 e nos dois padrões usamos apenas duas letras '_' e '|'. Como as linguagens C, C++ e Java possuem um tipo primitivo (long ou long long) de inteiro de 64 bits. Podemos pensar em representar o padrão em um inteiro, onde '_' é 0 e '|' é 1, e as M colunas do texto NxN. Com isso reduzimos o problema em: Procurar um padrão dentro de um texto. Este problema sabemos resolver com o Algoritmo KMP.
Pratique: https://br.spoj.pl/problems/QUADRADO
Referência:
Este problema pode ser modelado como um problema de Fluxo Máximo. Pense e divirta-se! =)
Pratique: https://br.spoj.pl/problems/CAVALOS
Referência:
Matemática
Pratique: https://br.spoj.pl/problems/FATORIAL
Intersecção de matróides.
Pratique: https://br.spoj.pl/problems/HONESTID
Referência: