Jump to content

ONI - Problema C


Recommended Posts

Ok.

Agora tenho mais uma dúvida. Não sei se te lembras do problema C da final das ONI..

Eu podia nesse problema considerar aquele mapa como um grafo, mais propriamente como um grafo pesado em que consideraria os vértices como os nenúfares e os arcos como as ligações entre os mesmos. Criava uma matriz de adjacência em que em cada elemento (i,j) teria a distância entre os vértices que estou a relacionar. A partir daí eu podia decidir qual era o caminho mais curto entre as duas margens?

Btw, também podia ter em (i,j) o custo do salto, ou a vida com que ficaria após o salto, não?

Edit:

enunciado: http://www.dcc.fc.up.pt/oni/problemas/2010/final/probC.html

here since 2009

Link to comment
Share on other sites

Nessa lista de adjacência teria um campo com o vértice e com os seus vértices adjacentes mais a distância entre cada um, certo?

E depois disso como é que faria para descobrir o caminho mais curto?

E como é que não construiria em n^2?

here since 2009

Link to comment
Share on other sites

Esses problemas não têm limites de tempo apertados? Não seria necessário implementar uma pesquisa com heurística? (não li o problema com atenção, posso estar a dizer disparates)

❝The idea that I can be presented with a problem, set out to logically solve it with the tools at hand, and wind up with a program that could not be legally used because someone else followed the same logical steps some years ago and filed for a patent on it is horrifying.❞- John Carmack on software patents

A list  of command line apps

Link to comment
Share on other sites

Adicionei o enunciado ao primeiro post.

Não é necessária nenhuma heurística, até porque queremos a solução óptima e heurísticas são perigosas.

Localhost: construir sem ser em O(N^2) não é trivial, concentra-te em resolver o resto do problema por agora. Assim que o tiveres feito, podemos discutir como optimizar esta parte.

Link to comment
Share on other sites

A análise aos problemas não chegou a ser posta online xD  temos de tratar disso

Construir em O(N log N) era um subproblema interessante, uma técnica semelhante está relacionada com o problema de 2008 http://www.dcc.fc.up.pt/oni/problemas/2008/final/probA.html

Mas como o Warrior disse, para já, o mais importante é resolveres o problema assumindo que construiste o grafo de forma eficiente e depois tratas dessa parte.

"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.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.