Obi 2007 Nível1 Fase2 - Uiqui

Autor da análise: jvcolettojvcoletto

http://olimpiada.ic.unicamp.br/passadas/OBI2007/res_fase2_prog/programacao_n1/pdf/provas/ProvaOBI2007_prog_f2n1.pdf

Resumo

Podemos resumir o problema em:

Dado um grafo G=(V, A) direcionado e com uma função de valoração f: A -> {0; 1}, determinar o comprimento do menor caminho entre dois vértices u, v pertencentes a V.

Acrescenta-se à isso o problema de tratar a entrada de forma que seja gerardo o grafo correspondente à instância de teste.
Os vértices do grafo representam strings de carecters compostas apenas por '_', 'A' à 'Z' e 'a' à 'z', dessa maneira precisamos de uma função que associe cada string com um valor inteiro.

A entrada nos passa todos os vértices e alguma arestas que compoem o grafo, nela são passadas N linhas da forma:

X Y

Em que, X é a string correspondente ao vértice de saída e Y a string correspondete ao vértice de entrada.
Além disso, devemos ordernar as strings que representam os vértices de forma que '_' precede 'A'…'Z' que precede 'a'…'z', pois existe uma conexão bidirecional entre dois vértices consecutivos, após a ordenação.

Solução

Para resolver o problema da manipulação da entrada, usei o container Map da STL, basicamente ele armazena um par <chave, informação>, assim você atribui um valor a uma chave "key" e pode acessá-lo com o operador [], além disso, o container mantém-se ordenado, o que é útil para o segundo problema no tratamento da entrada.

No caso da chave ser do tipo string, o Map faz a ordenação lexicográfica, o que não funciona nesse problema, porque ela não possui o mesmo tipo de precendência do exigido por ele. Para que a ordenação seja feita da maneira correta é necessário que se altere o procedimento de ordenação ou manipule a string de forma que a ordenação padrão ordene corretamente.

Para encontrar o menor caminho entre os dois vértices dados, utilizei uma BFS. Isso resolve o problema!

Na minha opinião foi mais difícil tratar a entrada do que usar um algoritmo para resolver o problema.

Testes

Entrada

A entrada abaixo, pode causar o erro devido a ordenação incorreta:

4
_ABCD AB_CD
_aBCd A_bcd
B_Dca b_acd
b_Acd _ABC_

_ABC_ b_acd

Saída

A ordenação correta seria:

_ABC_
_ABCD
_aBCd
A_bcd
AB_CD
B_Dca
b_Acd
b_acd

E a resposta:

4

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License