Publicado por: hugolt | março 28, 2009

OBI 2009, fase 1

Relato da OBI 2009, fase 1

Acabei de fazer a primeira fase da OBI 2009, modalidade Programação nível 2.
Achei a prova desse ano um pouco mais fácil que a do ano passado.
A primeira questão, Notas da Prova
Era a mais fácil de toda a prova. A questão consistia em pegar um número e dizer a correspondência em caractere.
N = 0 -> E
1 <= N <= 35 -> D
36 <= N <= 60 -> C
61 <= N <= 85 -> B
80 <= N <= 100 -> A

Bastava isso pra resolver a questão!

código em C++:  http://hugo.pastebin.com/f73cf46e5

Segunda questão, Caçadores de Mitos
Um pouco mais bem elaborada, mas também muito simples de resolver.
Era dada uma matriz, que representava uma cidade dividida em “blocos” de 1×1 metro. O ponto chave da questão era saber se um raio havia caído mais de uma vez no mesmo lugar, ou seja, no mesmo “bloco”.
Se usarmos a representação da cidade como uma matriz n*n, e colocarmos valor 0 em cada célula, basta incrementar quando um raio cair no bloco (x,y).
Assim fica fácil resolver o problema, pois se M[x][y] > 1, já caiu mais de um raio no mesmo lugar.

código em C++:  http://hugo.pastebin.com/f42c40523


Terceira questão, Caminho das Pontes

A questão mais difícil da prova. Não consegui enxergar o problema de primeira, mas relendo a questão consegui ver que se tratava de um caminho mais curto em um grafo simples.
A interpretação foi o ponto chave pra essa questão e pra ver como era, fiz o desenho.
Como era um grafo simples e havia algumas restrições no enunciado, daria pra usar Dijkstra, Bellman Ford ou qualquer outro de complexidade menor que O(n^3) fácilmente, bastava lembrar o algoritmo.
Eu não conseguia lembrar de jeito maneira Dijkstra, que era o que eu achei mais adequado pra usar. Pensei em usar Floyd-Warshall pra fazer a questão, mas a complexidade ia me tirar bastante ponto na prova, pois demoraria muito mais e eu não precisava de saber todos os caminhos mais curtos entre pares.
Então fui para o papel desenhar meu grafo e lembrar da idéia do algoritmo de Dijkstra.
O algoritmo de Dijkstra usa a mesma idéia do algoritmo de Prim, porém, ele é usado pra saber caminhos mais curtos – diferente do de Prim que calcula árvore geradora mínima.
Porém, há uma imensa semelhança nos dois, pois eles são “gulosos” (greedy) e sempre pegam a melhor solução.
Lembrando dos conceitos dos dois, consegui formar o meu algoritmo de Dijkstra, porém a resposta estava dando errada. Usei o GDB pra “debugar” o código e vi que não era um Dijkstra genérico, havia algumas restrições que eu tinha que fazer. No fim, precisei apenas trocar 3 linhas pra ficar ideal para o problema.
Voi-là! Fiz a questão.

código em C++: http://hugo.pastebin.com/f4adb57c0

Quarta e útlima questão, O Fugitivo
Questão simples pra quem conseguiu enxergar o plano cartesiano.
Era passado na questão coordenadas de um fugitivo, podendo ser para o norte, sul, leste ou oeste, e ele não poderia ficar M metros de distancia do ponto inicial, que era uma delegacia.
Parando pra analisar, a questão diz que a distância considerada é a distância euleriana, ou seja, nada de fazer triângulos, só somar os módulos de vertical com horizontal.
Ou seja, ABS(norte – sul) + ABS(leste-oeste) tinha que ser menor que M.

código em C++:  http://hugo.pastebin.com/f32a89267

Acho que fui muito bem na prova, inclusive terminei a prova com 2 horas e alguns minutos (o tempo dado foi de 5 horas pra fazer a prova).
Vou esperar o resultado e torcer pra dar tudo certo pra ir pra segunda-fase!


Responses

  1. Olá, boa tarde. Tenho um comentário a fazer em relação à questão 4. Perdoe-me se eu estiver errado, mas a medida considerada na questão era a da distancia euclidiana.
    Abraços

    • Agora não me lembro, mas pode ser que seja isso mesmo e eu tenha errado a questão.

  2. Realmente a sua 4 questão está errada, você teria que usar pitágoras, e nao podia somar tudo e calcular no final, tinha que calcular minuto a minuto.

    • Obrigado por atentar a isso.

      Se eu só errar essa já dá pra ir pra segunda-fase, pelo menos.
      Não me atentei a questão como deveria, pelo visto.
      Mais uma vez, obrigado pela observação.

  3. Sua questão 3 você declarou INF um número muito pequeno, experimente isso:
    21 22
    0 1 1000
    1 2 1000
    2 3 1000
    3 4 1000
    4 5 1000
    5 6 1000
    6 7 1000
    7 8 1000
    8 9 1000
    9 10 1000
    10 11 1000
    11 12 1000
    12 13 1000
    13 14 1000
    14 15 1000
    15 16 1000
    16 17 1000
    17 18 1000
    18 19 1000
    19 20 1000
    20 21 1000
    21 22 1000

    • Eu tinha pensado em alguns valores pra INF pra não ter problema com limites de inteiro… Aff, falta de atenção nos limites da questão mesmo.

  4. Mas não se preocupe essa primeira etapa vale apenas 1/21 da prova, então é só treinar bem pra segunda etapa! Vamos concorrer!

    • 🙂
      Primeira fase é pra tirar os que sabem “alguma coisa” pra trolhar na segunda-fase.

      Phyllipe, você é de onde? Me envie um e-mail pra gente poder conversar.
      Abraços.

  5. Galera…

    Alguem pode me dizer como eh q vai ser o esquema de classificação desse ano

    vai ser pontuação minima????

    vlws

    • Não sei, mas todos anos tem sido…

  6. irei fazer a prova de programação nivel 1 sábado, acho que irá cair a primeira questão da de vocês, pois todos os anos a equipe da OBI colocam uma questão unversal!!!! hehehe

    atté

  7. alguém pode me passar a segunda questão em PASCAL!!!!

    VOU FAZER-LÁ SÁBADO!!!!!

  8. alguém pode me passar a questão 2 em PASCAL!!!?

    POR FAVOR!!!

  9. alguém pode me passar a questão 2 em PASCAL!!!?

    POR FAVOR!!!

    é urgente!!!

  10. por favor!!!!
    Galera!!!

    me passe a segunda questão em PASCAL!!!

    é urgente!!!

    • Cara, o legal da prova é você elaborar as questões por si só…
      Eu falei as maneiras como eu resolvi e algumas pessoas já até me corrigiram, aproveita isso e monta sua resolução.

  11. A primeira questão é a mais fácil realmente, mas só que minha estrutura não é com IF, a minha ficou muito mais pequena, fiz com CASE!!!

    VALEU!!!

    ATTÉ!!!

  12. a segunda esse (x,y)

    o x é localição da cidade?

    e o Y o raio?

    • (x,y) é o local onde caiu o raio.
      x refere-se à “linha” e y refere-se à “coluna”, se você representar ou visualizar a cidade como uma matriz, que é o mais fácil =)

  13. essa questão 2, tem que dar a posição da cidade, e depois a posição em que os raios cairam é?

    estou fazendo assim:

    (x,y) -> posição da cidade.

    (u,t)-> posição onde os raios cairam.

    se x=u e y=t então
    já caiu 1 raio
    fim

  14. eu fiz a prova da OBI fase 2…
    mas se eu ñ me engano fiz outra completamente diferente aqui…..
    de q serie vcs sao?…..
    bju..

    • Eu sou da 3a série.

  15. depoiiis me adicionem no meu blog…
    naty159.blogspot.com

  16. Eu queria saber como é a segunda fase da prova OBI porque acho que passei na primeira e quero passar na segunda
    Para o que eu estudo??
    bjxxxx

    • Depende do nível em que você participou, Gabriela.
      Caso tenha sido Programação Nível 2, assim como eu, a segunda-fase é bem mais complicada. O pessoal que organiza a prova sempre coloca questões que envolvem grafos e alguma que você tenha que usar programação dinâmica ou raciocinar muito pra resolver.
      Se você estudar bastante Grafos e Programação Dinâmica, talvez consiga ir pra final!
      Vou esperar sair o resultado da segunda-fase pra ver se eu estudo um cado.

      Boa sorte🙂

  17. Olá, fiz a prova tb, mas apenas sei programar em C (pouco)
    Bom ate agora, estou tentando resolver o exercicio 3, e naum consigo criar uma logica, e tb naum entendi seu programa em c++
    Gostaria q vc me explicasse como pensou para resolucionar o 3 exercicio, o que seria Dijkstra e Bellman Ford
    vlw cara, manda um email, e vou estar visitando o site para ver respostas diariamente vlw obrigado

    • Pra solucionar o problema 3 você precisa entender o que é um grafo e entender como achar o caminho mais curto num bicho desses.
      Dijkstra e Bellman-Ford são algoritmos pra achar caminhos mais curtos em grafos.

      A idéia do algoritmo que eu usei (Dijkstra) é você ir pegando sempre o menor caminho de uma aresta pra outra (que ainda não foi visitado), e sempre atualizando os caminhos, se forem menores.
      Vou tentar exemplificar.

      Digamos que existem cidades A, B, C e D.
      A distância de A pra B é 5, de B pra D é 10, de A pra C é 2 e de C pra D é 7.
      Ou seja, há caminhos entre A e B, B e D, A e C, e C e D.

      Qual a menor distância (ou seja, caminho mais curto) pra chegar em D, partindo de A?
      A resposta seria: 9 (de A pra C e de C pra D => 2 + 7).

      Vamos pensar no problema partindo de A e onde não há arestas (ligações entre as cidades), a distância será sempre infinito (INF).
      DISTANCIA[A] = 0,
      DISTANCIA[B] = INF,
      DISTANCIA[C] = INF,
      DISTANCIA[D] = INF.

      De A pra B há um caminho de custo 5, assim, o menor caminho até B (partindo de A), seria, então, 5 e esse é o menor caminho partindo de A, por enquanto.
      DISTANCIA[B] = DISTANCIA[A] + 5 = 5

      De A pra C há um caminho de custo 2, e é o menor caminho partindo de A.
      DISTANCIA[C] = DISTANCIA[A] + 2 = 2

      De A pra D não existe nenhum caminho, então DISTANCIA[D] continua sendo INF.

      Partiremos de B.
      De B para A já calculamos o caminho, tem valor 5, no momento é o nosso menor, porém visitado.
      De B para C não há caminho, portando é INF.
      De B para D há um caminho, que é 10, porém não é o menor, o menor é 5. Mas é o menor que não foi visitado.
      DISTANCIA[D] = DISTANCIA[B] + 10 = 15

      Partiremos de D, então.
      De D para A não há caminho.
      De D para B há um caminho, que vale 10 e já calculamos.
      De D para C há um caminho, que vale 7, é o menor caminho e não foi visitado.
      DISTANCIA[D] = DISTANCIA[C] + 7 = 9 (esse é menor que o anterior, que era 15 – de B pra D)

      Agora vamos pegar o vértice do nosso menor caminho, que foi o C e partiremos dele.
      De C para A a distância é 2, porém, DISTANCIA[A] é 0, então não vamos mudar, pois nos interessa somente as menores distâncias.
      De C pra B a distância é INF – não há caminho.
      De C pra D a distância é 7, porém, D já foi visitado e não há mais ninguém pra visitar.

      NESSE PONTO TEMOS TODAS AS CIDADES VISITADAS!

      Já que todos foram visitados, temos todas as menores distâncias, partindo de A.
      DISTANCIA[A] = 0,
      DISTANCIA[B] = 5,
      DISTANCIA[C] = 2,
      DISTANCIA[D] = 9.

      Nós queremos ir para D, partindo de A, então o nosso caminho mais curto é 9.

      Qualquer dúvida procure no Google sobre caminhos mais curtos e há vários livros que tratam esses problemas.
      Eu gosto muito do “Introduction to Algorithms” e do “Programming Challenges”, são excelentes.

      Espero ter ajudado.

  18. vlw a ajuda amigo,
    fiz o programa das pontes em c, soh q ainda naum funciona 100%,
    vou estuda oq vc mandou
    ^^ vlw amigo abrç

  19. a detalhe, nun entendi qse nada doke tu falo mano, desconheço coisas como grafo e etc
    mas vo estuda ate amanha ^^

  20. eu copiei seu codigo das pontes, mas ai entro com os dados e do enter, so q ai o programa da o resultado e fecha, em c eu colocaria um getch(); , mas como eu faço p mim pode ver o resultado dele ??

    vlw carinha ^^

  21. Tente rodar o programa do seu terminal, ele foi feito pra rodar sob terminal, como todos os outros da OBI! Caso você não tenha notado, no site da OBI tem um exemplo de tarefa em C, mostrando como resolver um problema da maneira deles. Não deve-se pensar em janelas, interatividade, mensagens e etc. Apenas entrada e saída de dados.

    Se estiver no MS Windows vá ao seu Prompt-DOS e rode o programa. Verá que não precisa de getch()s e etc.

    PS.: getch é uma função da Borland e não é nenhum padrão! Portanto, não é portável, evite usá-la nos seus códigos. E se for fazer na OBI, NUNCA use-a.
    Tem como usar getch com C++, basta incluir o conio (que é uma biblioteca da Borland).
    Tente fazer isso no código:
    // código c++
    #include
    int main() {
    getch();
    }

  22. Olá Hugo, bom dia…
    Você tem alguma informação sobre o resultado da primeira fase?

  23. Passeeeeeeeei!!!!

    • Parabéns!

      Fui mal, mas passei também.

  24. Olá,por favo gostaria de saber se nós devemos corrigi aqui e olha na prova?

    Obrigado Me respondem

    • Desculpe Matheus, mas não entendi sua pergunta/proposta. Poderia reformular?

  25. Qual foi a nota de corte de 2009?


Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

Categorias

%d blogueiros gostam disto: