Blog Novo!

Resolvi mudar o meu blog, levá-lo um pouco mais a sério, e dispor de um pouco mais de recursos.

O novo endereço do meu blog é este:
http://crbonilha.com

Layout novo, host novo e até domínio novo!

Os posts que eu julgava mais interessantes foram e alguns ainda serão transferidos para lá.
Não farei mais nenhum post aqui, apenas lá.

Considerem este blog aposentado.
Não vou excluí-lo, porém, pois há bastante conteúdo bacana aqui ainda.

Vejo vocês lá.

#87 Exercício - Fazenda

Nome: Fazenda
Link: http://br.spoj.pl/problems/FAZENDMG/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 3.30
Memória usada: 12M
Colocação alcançada: 32
Tentativas: 4

Comentário:
Tinha até esquecido a sensação de receber um "aceito".

Dicas:
- Pensem em uma matriz grande. Agora preencham. Agora pensem em um modo de verificar quando há ou não uma cerca em determinado lado de determinada posição. Pronto.
- Prestem atenção para não verificar se a posição que você está verificando se há cerca não está fora da própria matriz. Se sim, há cerca.

#86 Exercício - TV da Vovó

Nome: TV da Vovó
Link: http://br.spoj.pl/problems/TV/
Dificuldade: 5/10
Linguagem: C++
Tempo atingido: 1.14
Memória usada: 6.5M
Colocação alcançada: 100+
Tentativas: 2

Dicas:
- O que seria mais eficaz, mudar cada valor da matriz, ou mudar a ordem com que cada valor da matriz será impressa? Imaginem o seguinte: Será impressa a linha 1, e após a linha 2. E se você mudasse, em vez do valores, apenas a ordem: seria impressa a linha 2, e depois a linha 1.
- Notem que o valor que indica quantas posições uma linha/coluna será movida pode ser maior que a própria matriz. Se eu mover 10 colunas a direita, numa matriz com 3 colunas, quantas posições as colunas moveriam de fato?

#85 Exercício - Companheiros de Exército

Nome: Companheiros de Exército
Link: http://br.spoj.pl/problems/ARMY11/
Dificuldade: 5/10
Linguagem: C++
Tempo atingido: 1.12
Memória usada: 4.1M
Colocação alcançada: 20
Tentativas: 1

Dicas:
- Pensem em quem está a esquerda e a direita de cada soldado. Quem ficará a direita do soldado que estava a esquerda de quem foi morto? E quem ficará a esquerda do soldado que estava a direita de quem foi morto? Só isso.

#83 Exercício - Fusões

Nome: Fusões
Link: http://br.spoj.pl/problems/JOAOMG/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 1.47
Memória usada: 4.2M
Colocação alcançada: 83
Tentativas: 2

Comentário:
Union-Find, é isso que foi preciso estudar.
Não é tão difícil, existem alguns métodos bons na internet, basta pesquisar.

Dicas:
- Estudem Union-Find.

#82 Exercício - João e o pé de feijão

Nome: João e o pé de feijão
Link: http://br.spoj.pl/problems/JOAOMG/
Dificuldade: 6/10
Linguagem: C++
Tempo atingido: 0.15
Memória usada: 2.6M
Colocação alcançada: 65
Tentativas: 2

Comentário:
Bem bolado esse exercício.
Pra resolver basta ter uma noção de manipulação de strings.

Dicas:
- Estudem algo sobre manipulação de strings.
- Vale notar que o quadrado de n pode ser um valor alto.

#76 Exercício - Engarrafamento

Nome: Engarrafamento
Link: http://br.spoj.pl/problems/ENGARRAF/
Dificuldade: 6/10
Linguagem: C++
Tempo atingido: 0.05
Memória usada: 4.7M
Colocação alcançada: 100+
Tentativas: 6

Comentário:
Faz um tempo que eu ouvia falar do algoritmo de Dijkstra (segundo o que eu li, se lê "dêcstra"), sobre como encontrar o caminho de menor custo, e finalmente consegui implementar.
Requer um conhecimento sobre grafos, e um pouco sobre ordenação, portanto recomendo para os mais experientes.
Aliás, um abraço pro meu nome amigo José, que me deu umas dicas sobre esse exercício.

Dicas:
- Estude algum algoritmo sobre encontrar o caminho de menor custo. Recomendo o Dijkstra para os mais experientes. Não tenho certeza se força bruta passa no tempo desse exercício, mas da pra tentar também.

#75 Exercício - Batalha naval

Nome: Batalha naval
Link: http://br.spoj.pl/problems/BATALHA2/
Dificuldade: 5/10
Linguagem: C++
Tempo atingido: 0.06
Memória usada: 2.9M
Colocação alcançada: 57
Tentativas: 5

Comentário:
Exercício de um joguinho que todo mundo conhece, batalha naval.
Não chega a ser difícil, basta ir marcando as jogadas e depois verificar se todas as partes de cada navio foi atingida.

Dicas:
- Certifiquem-se de verificar se todas as partes do navio em questão foram atingidas.

#73 Exercício - Você pode dizer 11

Nome: Você pode dizer 11
Link: http://br.spoj.pl/problems/ONZE/
Dificuldade: 4/10
Linguagem: C++
Tempo atingido: 0.07
Memória usada: 2.6M
Colocação alcançada: 100+
Tentativas: 3

Comentário:
Esse exercício pode parecer fácil no começo, porém ao se deparar com um número de até 1000 dígitos é preciso pensar duas vezes antes de resolvê-lo.
O interessante é que nem foi tão difícil. Eu dei uma olhada nos comentários, como sempre, e me deparei com esses "Critérios de divisibilidade", que o Cleber Adriani mostrou, que eu nunca imaginei que existiam.
Deem uma olhada: http://pt.wikipedia.org/wiki/Crit%C3%A9rios_de_divisibilidade
Com isso fica mais fácil resolver o exercício.

Dicas:
- Estudem critérios de divisibilidade.
- Notem que a entrada deverá ser uma cadeia de caracteres, e, independente do método escolhido, será necessário converter os valores para inteiros. Eu sempre uso a tabela ASCII (http://www.asciitable.com/) para converter.

#72 Exercício - Mesa da Sra Montagny!

Nome: Mesa da Sra Montagny!
Link: http://br.spoj.pl/problems/MESA/
Dificuldade: 5/10
Linguagem: C++
Tempo atingido: 1.76
Memória usada: 2.7M
Colocação alcançada: 100+
Tentativas: 3

Comentário:
Mais um exercício de grafo disfarçado ai.
Se trata de verificar se o grafo é bipartido.
Pesquisem algo sobre.

Dicas:
- Pesquise algo sobre grafo e como verificar se ele é bipartido.

Clique abaixo para alguns casos de teste úteis.

#70 Exercício - Tesouro

Nome: Tesouro
Link: http://br.spoj.pl/problems/TESOURO2/
Dificuldade: 6/10
Linguagem: C++
Tempo atingido: 2.65
Memória usada: 6.5M
Colocação alcançada: 23
Tentativas: 1

Comentário:
Pois é, 70 exercícios resolvidos no SPOJ! Pode não ser muito, mas pra mim já é bastante.
Sem falar na minha colocação na classificação, estou quase no top 200.
Agora vem a parte difícil, é preciso mutos pontos pra subir, mas vou continuar, devagar e sempre.
Voltando ao exercício, foi um pouquinho difícil, mas não muito.

Dicas:
- Façam uma DFS com listas de adjacências.
- Para cada sala visitada, é recomendável salvar um valor máximo que ela pode alcançar, assim não é preciso verificar sempre.
- Caso não entendam de grafos, pesquisem algo na internet, tem bastante conteúdo por aí.

#69 Exercício - Galou está de volta

Nome: Galou está de volta
Link: http://br.spoj.pl/problems/GALOUVOL/
Dificuldade: 6/10
Linguagem: C++
Tempo atingido: 0.12
Memória usada: 2.6M
Colocação alcançada: 65
Tentativas: 1

Comentário:
Deu um pouquinho de trabalho, mas a lógica não é tão difícil assim.
Basta que vocês usem um DFS na grade, e imprimam a coisa certa.

Dicas:
- Notem que a entrada está em um retângulo reto, ao contrário do exemplo anterior onde o retângulo estava inclinado. A zona de contato de cada engrenagem continua a mesma do exemplo, isso é importante.
- Façam uma busca DFS na grade e vá marcando as direções. Caso alguma direção emperre, faça com que todos sejam bloqueados.

#61 Exercício - Dengue

Nome: Dengue
Link: http://br.spoj.pl/problems/DENGUE/
Dificuldade: 4/10
Linguagem: C++
Tempo atingido: 0.13
Memória usada: 2.7M
Colocação alcançada: 100+
Tentativas: 1

Comentário:
Este exercício envolve uma lógica simples de grafos, recomendo para quem esteja estudando tal.
Eu o fiz usando uma forma um tanto quanto trivial, um BFS, mas imagino que haja outras maneiras de resolvê-lo.

Dicas:
- Pesquise algo sobre BFS em grafos, e então verifique cada cidade.

#52 Exercício - Rouba-Monte

Nome: Rouba-Monte
Link: http://br.spoj.pl/problems/ROUBA/
Dificuldade: 4/10
Linguagem: C++
Tempo atingido: 0.02
Memória usada: 2.6M
Colocação alcançada: 90
Tentativas: 1

Comentário:
Exercício simples, porém pode confundir um pouco.
Bom para treinar a perícia com vetores.

Dicas:
- Preste atenção na hora de passar a vez de jogar.
- Não importa a ordem de checagem, entre pilha de descarte e topo da pilha do adversário, visto que a carta não pode estar nos dois lugares.

#48 Exercício - Vivo ou morto

Nome: Vivo ou morto
Link: http://br.spoj.pl/problems/VIVO/
Dificuldade: 5/10
Linguagem: C++
Tempo atingido: 0.93
Memória usada: 2.6M
Colocação alcançada: 100+
Tentativas: 1

Comentário:
Pode parecer complicado, mas é até simples.
Basta tomar cuidado com os detalhes e implementar da maneira correta.

Dicas:
- Note que a fila é refeita sempre que alguém é eliminado.
- Alguém é eliminado sempre que seu movimento é diferente da ordem dada pelo professor.

#47 Exercício - Poker do rei

Nome: Poker do rei
Link: http://br.spoj.pl/problems/KING11/
Dificuldade: 4/10
Linguagem: C++
Tempo atingido: 0.01
Memória usada: 2.6M
Colocação alcançada: 38
Tentativas: 1

Comentário:
Parece simples, mas me deu uma bela de uma dor de cabeça.

Dicas:
- Repare que a saída deve ser ordenada.
- Preste atenção nos casos de teste, eles são suficientes para se resolver o problema.
- Ordenar a entrada pode lhe garantir menos trabalho mais tarde.

#46 Exercício - Caça ao tesouro

Nome: Caça ao tesouro
Link: http://br.spoj.pl/problems/TESOUR11/
Dificuldade: 6/10
Linguagem: C++
Tempo atingido: 0.04
Memória usada: 2.6M
Colocação alcançada: 19
Tentativas: 1

Comentário:
Foi até divertido resolver este exercício, eu recomendo.

Dicas:
- Note que um tesouro é encontrado se todas as dicas apontarem para ele. Portanto, verifique as posições onde no mínimo uma dica aponta, e verifique se todas as outras também indicam essa posição.
- Não é preciso nem montar uma matriz ou algo do tipo. Basta localizar as posições e fazer suposições.

#44 Exercício - Colorindo

Nome: Colorindo
Link: http://br.spoj.pl/problems/COLOR11/
Dificuldade: 4/10
Linguagem: C++
Tempo atingido: 0.38
Memória usada: 4.3M
Colocação alcançada: 48
Tentativas: 1

Comentário:
Agora que eu descobri o poder das funções recursivas tudo ficou mais fácil haha.
Este exercício também é bem simples, basta verificar as casas adjacentes da matriz e ir pulando de uma em uma.

Dicas:
- Tome cuidado pra não verificar uma casa que esteja fora dos limites da matriz.

#43 Exercício - Mário

Nome: Mário
Link: http://br.spoj.pl/problems/MARIO/
Dificuldade: 6/10
Linguagem: C++
Tempo atingido: 0.90
Memória usada: 4.1M
Colocação alcançada: 100+
Tentativas: 5

Comentário:
Parece besteira, mas eu levei um tempão pra resolver graças a um detalhe que foi pura preguiça minha de ler o enunciado e consertar.
Esse exercício pode parecer complexo, porém eu acabei encontrando uma solução bem simples, inclusive parecida com um exercício que eu resolvi esses dias, o Bolo de apostas.
Acontece que eu usei algo parecido com o max interval sum, e acabei resolvendo o problema. Recomendo que estudem para ter uma ideia do que estou falando.
Aliás, usem a criatividade. As vezes dá pra fazer muito com pouco...

Dicas:
- Estudem o algoritmo max interval sum e adaptem-o a este problema.
- Tomem cuidado com o tamanho das entradas, que podem ser de até 1 bilhão, por mais que sejam somente 100 mil armários.

Casos de teste úteis

#33 Exercício - Brincadeira das tentativas

Nome: Brincadeira das tentativas
Link: http://br.spoj.pl/problems/TENTA/
Dificuldade: 5/10
Linguagem: C++
Tempo atingido: 1.54
Memória usada: 2.6M
Colocação alcançada: 100+
Tentativas: 1

Comentário:
Essa me deu uma dor de cabeça, mas no final foi até divertida.
Vale a pena quebrar a cabeça pra tenta resolver, é interessante.
Eu usei um método de funções recursivas, ou seja, funções que chamam a si mesmo quantas vezes forem necessárias.

Dicas:
- É bom ter em mente que a ordem deve estar em ordem sempre que possível. Digamos que você faça uma troca entre o primeiro e o terceiro valor, agora faça questão de que entre o segundo e o último eles estejam em ordem antes que você comece a fazer as trocas do segundo número em diante.
- Digamos que a ordem que você terá que fazer tudo é mais ou menos essa: primeiro você troca os últimos números, depois um número antes desses, e então os últimos de novo, então você troca um número antes desses, e por aí vai.
- Treine escrever em um caderno a ordem correta até que você compreenda a lógica.