Publicado por: hugolt | março 31, 2008

Olimpíada Brasileira de Informática (OBI)

OBI 2008, fase 1

Preparacao

Ontem foi o tão esperado dia da OBI pra mim, 29 de Março de 2008.
Estava pouco preparado, pelo menos é o que eu acho.

Fui pra Campos na sexta à noite, pois eu queria dormir bem, afinal,
pra cinco horas de prova deve ser cansativo e teno que estar bem descansado.
O Akamaru (André) me recomendou levar algo pra comer e beber durante a prova, recomendou levar carboidratos.

Sábado acordei, animado e ansioso, fiz meu almoço e coloquei 2 pacotes de biscoito
de chocolate e um pacote de biscoito de maizena na mochila, junto de uma garrafinha de água gelada e fui pro CEFET.


A Prova

Quando peguei a prova deu uma aflição, li atentamente a capa e fui pro primeiro problema.

#1 OBI:
O nome do problema era OBI, simples demais.
Acho que todos devem ter conseguido resolver.

O objetivo do programa era somar dois valores obtidos por N competidores e verificar quantos eram igual ou maior à pontuação mínima.
código-fonte obi.c

#2 Telefone:
O problema tinha como objetivo pegar uma string e
substituir as letras pelos correspondentes números em um teclado de telefone.

Havia a correspondência de teclas e números na folha. (ABC = 1, DEF= 2, …, PQRS = 7,…)
A entrada era um número de telefone, incluindo hífens opcionais e cada caractere fora o hífen poderia ser um dígito ou uma letra.
A saída era a entrada somente com hífens e dígitos.

código-fonte telefone.c

#3 Avião:

O problema que tinha que pensar um pouco, pois a solução era matemática.

O avião era marcado por fileiras e colunas, existiam F fileiras e cada fileira possuía C colunas/assentos. Era dado um valor E, que era a fileira onde começava a classe econômica e um número B que era o número de bilhete de Su Zuki (protagonista do problema). A tarefa era verificar se por ordem de chegada Su Zuki teria lugar reservado na classe econômica. Por exemplo, se houvesse 10 fileiras, cada uma com 3 colunas/assentos, a classe econômica começasse na fileira 3 e Su Zuki tivesse o bilhete 10, ele ficaria na posição 6 A (sexta fileira e primeira coluna).
Caso Su Zuki possuísse o bilhete 2 ficaria em 3 B (terceira fileira e coluna 2),
e assim por diante.

Problema matemático.

A fileira de Su Zuki seria o quociente da divisão de seu bilhete pelo número de colunas, e a posição seria o resto da divisão.

Se o quociente fosse 2, a fileira dele seria 2 + E (onde começava a classe econômica).
Portanto era necessário verificar se esse acento estava disponível, pois havia F fileiras.

se (b/c) + E <= F é possível embarcar, caso contrário não.

Aí o problema está morto e enterrado e é só seguir o procedimento de saída.

código-fonte aviao.c

#4 Lanche na empresa:

O problema mais difícil da prova.
Envolvia caminhos curtos, no mesmo estilo de um problema chamado Dengue que tem na parte de tarefas da OBI, porém havia valores para distâncias, que eram os pesos (o que não há no problema Dengue).

O objetivo era escolher uma sala pra ser a cozinha. A cozinha deveria ser posicionada em uma das salas de tal forma que a distância entre a cozinha e a sala mais distante da cozinha seja a menor possível.

Eu usei o algoritmo de Bellman-Ford pra resolver o problema.

código-fonte lanche.c

#5 Ogros:

O problema dessa tarefa era armazenar os valores em vetores/tabelas, para serem comparados depois. Nada de outro mundo.

… Numa feira de circo marciano, ogros são chamados para bater um martelo
num aparelho que mede sua força.
O ogro ganha um determinado prêmio dependendo da faixa de força que alcançou
(por exemplo, se a força alcançada foi entre 0 e 5, ganha 10 pontos.
Se for entre 6 e 10, ganha 30).
São possíveis N premiaçõe, para N faixas de força alcançadas.

Você deve escrever um programa que recebe quais são as faixas de forças
e suas respectivas premiações.
Em seguida, o programa recebe a força alcançada por M ogros,
e deve calcular quanto cada ogro recebeu de premiação.

O problema da tarefa não estava em local nenhum senão no armazenamento e na ordem para pegar os valores das faixas.

código-fonte ogros.c


Essa foi a fase 1 da OBI nível 2 de programação, não garanto a veracidade de nada.
Tudo foi tirado por conclusões minhas.


Responses

  1. Fala ai cara seus exerc estão bacanas! vc nao tem eles em Pascal? soh em C mesmo? VLWWW

    • Valeu! Eu só fiz em C mesmo..


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: