Analysistreino030312

Treino de Implementação (aquecimento para um longo ano!)

Status desse analysis: 100% completo, uhu!

Quick-ref link para os problemas:

Parte dos Calouros

3n+1 (UVa 100)

Problema tradicional para todos os iniciantes. Iterar sobre o range, usando o pseudo-código dado para checar o tamanho da sequência é suficiente para passar, mas deve-se tomar cuidado, porque, como ele não garante que i<j, ele pode trocar a ordem e isso acaba com códigos tipo:
for (int k=i; k<=j; k++)
No exemplo i=10, j=1, por exemplo, ele não entra no for mas, pelo sample, sabemos que a resposta é 20. Esse é o único ponto que deve-se tomar cuidado.
Minha solução: http://pastebin.com/C9z2AGec

Ecological Premium (UVa 10300)

Nesse problema, é uma boa simplificar a conta para poder usar inteiros. Fora isso, é um acumulador relativamente simples. Na minha solução usei long longs (porque, se o input for (10^5)*(10^5) ==10^10, que não cabe num int, mas acho que não precisava)
Minha solução: http://pastebin.com/sjf9XjG1

Hashmat the brave warrior (UVa 10055)

O catch nesse problema é que o maior número que ele pode dar é 2^32, que é suficiente para estourar o unsigned int. Logo, é preciso usar long long para pegar a entrada. Além disso, não se deve usar a função da stdlib.h, abs(), porque ela recebe um inteiro, então no type cast, a variável estoura. Basicamente é isso: use long longs e escreva sua função de módulo usando que recebe um long long (ou use defines, ifs, o que você achar melhor, só tome cuidado com os type casts)
Minha solução: http://pastebin.com/GT7b22H1

Back to High School Physics (UVa 10071)

Mesmo com aceleração constante, você não precisa da aceleração pra resolver esse problema – se ele te dá a velocidade no meio do trajeto, ela também corresponde à velocidade do trajeto. Então para saber o espaço percorrido, basta fazer 2*v*t
Minha solução: http://pastebin.com/xccDbyN3

To and Fro (SPOJ TOANDFRO)

Esse problema é pura implementação, então leia cuidadosamente o enunciado: ele escreve a string dividindo elas nas colunas da matriz e depois alterna o sentido que ele lê as linhas para gerar a string encodada. Para conseguir a string original, basta reverter o processo. Lembre-se que, como a string não tem espaços em branco, você pode usar scanf(" %s", str) para evitar que ela pegue o \n da linha anterior. Para quem não sabia disso, recomendo ler Apostila de entradas exóticas
Minha solução: http://pastebin.com/4GVC4Rx5

TEX Quotes (UVa 272)

Como não existe nesting nesse problema, por exemplo, (()((()))), você pode ler caractere a caractere (sem ignorar os espaços), guardar se você já está com aspas aberta ou não e, dependendo disso, você trocar por aspas abertas ou fechadas
Minha solução: http://pastebin.com/GF1JqkvB

Parte dos veteranos

Minesweeper (UVa 10189)

Esse problema pode parecer muito chato, mas fica bem melhor se você indicar os 8 vizinhos num vetor e fazer um for por ele (tomando cuidado para não acessar memória inválida, claro). Fora isso, não tem muitos truques, só a linha ENTRE casos e não após cada caso que necessita atenção e a formatação do output certinha, para não tomar WAs desnecessários.
Minha solução: http://pastebin.com/ZJGpPwK5

List of Conquests (UVa 10420)

Eu fiz um tremendo de um overkill quando eu codei esse problema, por usar um map. Como ele fala que são no máximo 2000 linhas, você pode só guardar os países num vector, fazer uma busca linear para ver se o país já existe (se não, adicionar ele à lista) e usar um vetor auxiliar para contar quantas vezes ele apareceu. Mas, bom, um map é uma opção tremendamente curta, então não é de todo mal.
Minha solução: http://pastebin.com/4U7rtvW8

The Blocks Problem (UVa 101)

Esse problema já foi fonte de frustrações para muitos colegas meus de maratona (inclusive pra mim, eu tentei ele n vezes antes de passá-lo), porque é um problema muito claro que precisa ser bem implementado e testado até o talo para passar – nenhum segredo além disso, só teste cada função que você fizer e veja cada movimentação de blocos. Se sim, existe grande probabilidade que você vai ganhar um AC de cara.
Um truque que eu usei na minha implementação para evitar código repetido (lembre-se: quando mais código, mais chances de ter bugs!) foi reparar que as operações são de dois tipos: guardar os blocos em sua posição original ou colocar uma pilha de blocos em uma posição. Então, você pode implementar essas duas funções e usá-las para compor cada comando (aliás, é o ideal, pela regra que eu citei acima). Enfim, eu vejo esse problema como uma boa lição de programação =), então tentem fazê-lo!
Minha solução: http://pastebin.com/ryfvNWHx

Queen (UVa 11494)

Coloquei esse problema aqui só de combo breaker. Ele não é realmente um problema de implementação, é mais um problema de pensar um pouco. Ele é dividido em três casos muito fáceis de ver: as duas peças estão na mesma posição; elas estão na mesma linha, coluna ou diagonal; nenhuma das anteriores – é fácil ver que para essa, só dois movimentos são necessários (um pra chegar na mesma linha, outro na mesma coluna).
A parte mais chata desse problema é checar as diagonais, mas isso é resolvido se você lembrar que diagonais são da forma (x+k,x) ou (x,x+k), que foi o que gerou minha função checkDiag().
Minha solução: http://pastebin.com/7tWtZWdf

Number Steps (SPOJ NSTEPS)

A observação que deve ser feita nesse problema é que as coordenadas mudam de forma periódica e que nenhum número vai exceder 10^5, porque como as coordenadas vão até 10^4 e é possível concluir que um número sempre vai ser até o dobro de suas coordenadas, o maior número teoricamente seria 2*10^4, o que torna 10^5 um limite superior até exagerado. Fora isso, basta simular até seu limite superior de escolha e responder as queries depois (eu usei um map pra isso, mas devem ter outros jeitos).
Minha solução: http://pastebin.com/gjirBUjB

Puzzle (UVa 227)

Esse problema é uma implementação fácil, mas ele tem UMA coisa que faz ele ser um inferno, que é a possibilidade de existir um espaço no começo da string, impossibilitando de usar " %[^\n]" (ou, pelo menos, requerendo mais cuidado ao fazê-lo). Se você contornar o caso de uma linha qualquer do puzzle começar com um espaço, o problema fica uma implementação tranquila.
Minha solução: http://pastebin.com/Vg1BChH6

Triangle Wave (UVa 488)

Treino de formatação de output, esse problema – e só. Tenha atenção com os espaços no meio (e NÃO no final) e você está feito. Ah, e a versão em PDF desse problema está um tanto incompleta, então recorra à HTML.
Minha solução: http://pastebin.com/WmHSeU5U

Sticker Collector Robot (UVa 11831)

Um problema de regional bacaninha pra fechar. Esse problema é muito legal: o output dele é fácil e ele está bem especificado, então é só ter atenção na hora de ler o textinho e implementar com cuidado a movimentação do robô. Ah, e de novo, é uma boa usar o truque dos vizinhos, reduz bastante a implementação.
Minha solução: http://pastebin.com/xK8uHCFY

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License