Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

pikax

Olimpiadas 2010 questão

Mensagens Recomendadas

pikax

Boas

Será que alguém pode-me dar uma ajuda nos programas de qualificação para as olimpíadas?

Por exemplo o exercício A da fase de qualificação para as finais, tive 40% da nota,  o meu programa estava a fazer os exemplos correctamente mas eu sei que os júris depois avaliam os programas por uma boa programação.

O que eu gostava de saber, as característica necessárias para que o programa seja melhor cotado.

Não quero que digam-me o código, só desejava que dessem-me umas dicas, se for necessário posto o meu código.

Obrigado


Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Strabush

Não sei lá mto disso, mas na experiência que tenho penso ser:

- Estruturação/Organização

- Optimização

- Simplicidade

- Comentários

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Cynary

Não sei lá mto disso, mas na experiência que tenho penso ser:

- Estruturação/Organização

- Optimização

- Simplicidade

- Comentários

Isso são boas práticas de programação, mas apenas uma conta para a cotação por parte do Júri.

- Optimização

O júri avalia o programa desta forma: testam o teu programa em vários casos de teste. Por cada caso de teste testado dentro dos limites, e com resolução correcta, ganhas pontos. Se o caso de teste ultrapassar os limites (mais de 1s a executar no computador do júri ou acima do limite de memória), ou der uma resposta errada, não te dá pontos nenhuns.

Portanto, interessa-te apenas que uses um algoritmo correcto e rápido, que fique dentro dos limites de memória.

Um conselho, no entanto: certo > rápido. Se nos problemas da qualificação tivesses a pontuação que eles dão com casos de teste pequenos, ficarias muito bem cotado, e passarias à final. 40 para o primeiro, 50 para o segundo e 60 para o terceiro.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

Em concursos de programação é usado um sistema o mais objectivo possível, de modo que o único critério de desempate entre as soluções é o seu desempenho.

No entanto, não enveredem por optimizações pequeninas (como usar registers ou utilizar somente apontadores) porque o mais importante é o algoritmo. Pensem em como resolver o problema, e pensem como podem tornar a resolução do problema mais rápida.

Para isso dá jeito bases de complexidade de algoritmos.

Acho importante que depois de terminarem os vossos conseguirem dizer "estou a competir para os X pontos".

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pikax

Como é o meu primeiro ano a programar e também nas olimpíadas, acho que é normal ter este tipo de duvidas.

Tou a ver que terei que estudar as melhores maneiras para criar algoritmos rápidos e eficientes, pelo o menos para a final.

Muito obrigado pelo o esclarecimento da minha duvida.


Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mogers

volto a recomendar o treino da usaco para aprenderes novas técnicas e algoritmos. é o melhor site que conheço.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Aqua Costa

pikax, por exemplo para o meu programa passar nos limites de memória utilizo ponteiros, acho que desta forma os meus programas não tiveram problemas relacionados com memória. O único problema nos problemas A e B acho que foi relacionado com o tempo de execução, pois não encontrei mais nenhum problema...

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mogers

ponteiros, como assim? não vejo utilizade nenhuma nisso. porque não declarar as estruturas de dados grandes como globais?


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Cynary

ponteiros, como assim? não vejo utilizade nenhuma nisso. porque não declarar as estruturas de dados grandes como globais?

Depende do caso em que se usa ponteiros :)

Costumo usá-los muito em soluções de programação dinâmica para poupar espaço e tempo (já que normalmente nas tabelas usadas, apenas utilizamos duas linhas de cada vez -- uma com os resultados anteriores, e uma que vai ter os novos resultados -- e em vez de guardar a tabela inteira em memória, apenas guardo duas linhas, e depois para trocá-los, é só usar três ponteiros. Podia em vez disso copiar o conteúdo de uma linha para a outra, mas não seria o melhor :P). Posso é estar a fazer mal, se tiveres sugestões melhores, estou aberto a elas ;)

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mogers

Ponteiros dão cá um jeito. Mas precisa perceber bem como usa-los antes.

É óbvio que sim. O meu comentário referiu-se à sua utilização para não ter problemas de memória. (parece que ele usa isto recorrentemente). Se ele prefere declarar um vector/matriz dinamicamente em vez de estaticamente, acho mal porque só está a complicar (na esmagadora maioria dos casos).

Depende do caso em que se usa ponteiros :)

Costumo usá-los muito em soluções de programação dinâmica para poupar espaço e tempo (já que normalmente nas tabelas usadas, apenas utilizamos duas linhas de cada vez -- uma com os resultados anteriores, e uma que vai ter os novos resultados -- e em vez de guardar a tabela inteira em memória, apenas guardo duas linhas, e depois para trocá-los, é só usar três ponteiros. Podia em vez disso copiar o conteúdo de uma linha para a outra, mas não seria o melhor :P). Posso é estar a fazer mal, se tiveres sugestões melhores, estou aberto a elas ;)

Penso que nesse caso é mesmo a melhor forma, também uso esse método.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Aqua Costa

ponteiros, como assim? não vejo utilizade nenhuma nisso. porque não declarar as estruturas de dados grandes como globais?

char *letras;

letras = new char[nLetras];

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mogers

Acho que coisas desse género são um bocado perda de tempo. A alocação dinâmica de memória pode ser necessária para certas estruturas de dados ou problemas específicos. Mas caso geral, parece-me perfeitamente desnecessário.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

@AquaCosta eu acho que podes perfeitamente declarar uma constante ou fazer um #define para os limites que te dão visto que (acho) que esse limites nunca ultrapassarão o espaço limite que também te dão.

O que eu costumo fazer é:

#define MAX 1000
int array[MAX];

ou em C++:

const int MAX = 1000;
int array[MAX];

MAX, neste caso, será o máximo de alguma coisa que te dão. É muito melhor do que andares a trabalhar com ponteiros, visto que se o teu programa crescer depois para debug é muito mais difícil e pode até ser diferente de caso para caso (o erro).

Foi só uma sugestão. ;) 


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Aqua Costa

@AquaCosta eu acho que podes perfeitamente declarar uma constante ou fazer um #define para os limites que te dão visto que (acho) que esse limites nunca ultrapassarão o espaço limite que também te dão.

O que eu costumo fazer é:

#define MAX 1000
int array[MAX];

ou em C++:

const int MAX = 1000;
int array[MAX];

MAX, neste caso, será o máximo de alguma coisa que te dão. É muito melhor do que andares a trabalhar com ponteiros, visto que se o teu programa crescer depois para debug é muito mais difícil e pode até ser diferente de caso para caso (o erro).

Foi só uma sugestão. :) 

Eu prefiro alocação dinâmica porque já estou muito habituado a usar quando estou a programar jogos em DirectX 10, por exemplo, não sei quantos vertices tem um objecto por isso alocação dinâmica é mais eficiente.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.