Quem já está acompanhando aqui no blog os comentários sobre os problemas da lista de exercícios para a OBI já está sabendo, mas como a ideia é que todos possam treinar para a OBI com esses problemas, explicarei do que ela se trata.
A lista que está disponível aqui já está com os problemas da primeira semana de treinamento disponível, ela tem 3 níveis, P1, para aqueles que fizeram esse ano PJ e ano que vem farão a prova de P1; P2, para quem fez P1 esse ano; e P2++, problemas mais difíceis e voltados para aqueles interessados em se preparar para a seletiva para a IOI do ano que vem.
O objetivo não é competir para ver quem resolve mais problemas da lista, o intuito desse placar é apenas permitir que exista uma referência de comparação para saber como está seu andamento. Por favor, levem a lista a sério e não fiquem fazendo brincadeiras com os nomes dos colegas, e sejam honestos, marquem apenas os problemas que vocês realmente fizeram.
Mesmo que você não tenha participado da OBI esse ano ou então nem mesmo participe da OBI, você é bem vindo a resolver os problemas propostos, o foco principal é OBI, mas os problemas mais difíceis devem ser interessantes até para quem participa da Maratona de Programação.
A ideia é soltar também sempre comentários sobre os problemas propostos, com códigos da solução depois de um tempo, de forma a auxiliar aqueles que estão com mais dificuldades na resolução ou que querem apenas descobrir se existe outra maneira de resolver o problema. Contribuições de comentários e códigos são, é claro, sempre muito bem vindas.
Ainda não resolvi os problemas Garota Hiperativa (na verdade eu resolvi esse durante a própria prova da Maratona em 2010, mas preciso relembrar e pensar novamente) e Metrô Engenhoso, então, se alguém quiser contribuir com comentários ou soluções, por favor, é só me falar.
Passando a limpo os problemas propostos para a primeira semana:
P1:
Burning Midnight Oil - Comentários
Binary and octal - Comentários
Summation - Comentários
Aeroporto - Comentários
Plug-in - Comentários (outro)
P2:
Regular Bracket Sequence - Comentários
Investindo no mercado de ações 1 - Comentários
Matrizes - Comentários
Bitmap - Comentários
P2++:
Os doces da Candy - Comentários e solução
Cerca do jardim - Comentários e solução
Garota hiperativa
Metrô engenhoso - Resolução do Marcos
Espero colocar os códigos de todos problemas que já têm comentários em breve, mas sintam-se livres pra contribuir com códigos também. Os comentários e solução dos problemas Os doces da Candy e Cerca do Jardim estão em inglês pois eu tinha feito eles no começo do ano e a ideia era atingir o maior público possível com a solução.
Update: O Marcos Kawakami postou comentários da solução para o problema Metrô engenhoso, muito bem feitos por sinal, o link foi adicionado
Update2: Todos problemas das listas da P1 e P2 estão com códigos da solução já disponíveis, só falta agora o problema Garota Hiperativa, que eu espero postar em breve
Wednesday, July 11, 2012
Matrizes - OBI 2010 e Bitmap - Spoj
E para finalizar os comentários sobre os problemas selecionados para a primeira lista de treinos para OBI, vou falar em um mesmo post do problema Matrizes, da OBI 2010 e disponível no SpojBR (link) e do problema Bitmap, do Spoj (link).
Começando pelo problema Matrizes, o enunciado dá uma fórmula para gerar os valores das matrizes quadradas A e B e pede o valor de uma célula da matriz C = A x B. O tamanho máximo das matrizes é 105 e o valor máximo de cada célula é 104. Ou seja, cada matriz tem 105 x 105 elementos, o que já mostra que é inviável gerar as matrizes para calcular a matriz C resultante.
Pensando com calma em como é feita uma multiplicação de matrizes você consegue perceber que para calcular o valor de uma determinada célula apenas uma linha de A e uma coluna de B importam. Dessa forma basta fazer a soma das multiplicações da linha pela coluna e o valor da posição pedida na matriz C é obtido. É importante lembrar que a soma pode estourar um inteiro comum, já que 105 x 104 x 104 é maior do que 231.
Agora sobre o problema Bitmap, do Spoj (link). O enunciado começa definindo a distância entre dois pontos de uma imagem preto e branco como a distância de Manhattan delas (ou seja, a soma das diferenças absolutas entre x e y) e a partir daí ele pede a distância de cada ponto da imagem para o ponto branco mais próximo.
Observando como é feita a distância entre dois pontos (cada ponto fica a distância 1 de seus vizinhos que dividem um lado com eles) é possível pensar em uma BFS, já que ela é capaz de encontrar o menor caminho entre dois pontos em um grafo no qual as arestas têm todas o mesmo custo.
Mas essa BFS tem uma sacada, você não tem apenas um ponto de partida, pois você quer saber qual a distância mínima de um dos pontos brancos para cada um dos pontos pretos, dessa forma, é como se você estivesse começando sua busca em cada um dos pontos brancos existentes e a partir daí você vai marcando as células encontradas e ainda não visitadas com a distância mínima.
Códigos do Andrei para os problemas Matrizes: http://ideone.com/O5nVk e Bitmap: http://ideone.com/vdliv
Começando pelo problema Matrizes, o enunciado dá uma fórmula para gerar os valores das matrizes quadradas A e B e pede o valor de uma célula da matriz C = A x B. O tamanho máximo das matrizes é 105 e o valor máximo de cada célula é 104. Ou seja, cada matriz tem 105 x 105 elementos, o que já mostra que é inviável gerar as matrizes para calcular a matriz C resultante.
Pensando com calma em como é feita uma multiplicação de matrizes você consegue perceber que para calcular o valor de uma determinada célula apenas uma linha de A e uma coluna de B importam. Dessa forma basta fazer a soma das multiplicações da linha pela coluna e o valor da posição pedida na matriz C é obtido. É importante lembrar que a soma pode estourar um inteiro comum, já que 105 x 104 x 104 é maior do que 231.
Agora sobre o problema Bitmap, do Spoj (link). O enunciado começa definindo a distância entre dois pontos de uma imagem preto e branco como a distância de Manhattan delas (ou seja, a soma das diferenças absolutas entre x e y) e a partir daí ele pede a distância de cada ponto da imagem para o ponto branco mais próximo.
Observando como é feita a distância entre dois pontos (cada ponto fica a distância 1 de seus vizinhos que dividem um lado com eles) é possível pensar em uma BFS, já que ela é capaz de encontrar o menor caminho entre dois pontos em um grafo no qual as arestas têm todas o mesmo custo.
Mas essa BFS tem uma sacada, você não tem apenas um ponto de partida, pois você quer saber qual a distância mínima de um dos pontos brancos para cada um dos pontos pretos, dessa forma, é como se você estivesse começando sua busca em cada um dos pontos brancos existentes e a partir daí você vai marcando as células encontradas e ainda não visitadas com a distância mínima.
Códigos do Andrei para os problemas Matrizes: http://ideone.com/O5nVk e Bitmap: http://ideone.com/vdliv
Tuesday, July 10, 2012
Aeroporto - OBI 2002
Olá a todos, o post da vez será com comentários sobre o problema Aeroporto, que é da OBI 2002 e está disponível no SpojBR (link).
O problema pede o aeroporto mais congestionado dentre todos os A existentes. O congestionamento de um aeroporto é definido como a soma do número de vôos que chegam mais o número de vôos que saem dele.
Para a resolução do exercício então basta manter um vetor para cada aeroporto com o número de vôos que ele tem. Para cada vôo os contadores do aeroporto de partida e de destino são incrementados. Ao final basta ver qual o maior número de vôos que um aeroporto tem em uma passada pelo vetor e posteriormente percorrer o vetor imprimindo todos aeroportos com o mesmo número de vôos que o máximo.
Código do Andrei para o problema: http://codepad.org/8cPuTEnU
O problema pede o aeroporto mais congestionado dentre todos os A existentes. O congestionamento de um aeroporto é definido como a soma do número de vôos que chegam mais o número de vôos que saem dele.
Para a resolução do exercício então basta manter um vetor para cada aeroporto com o número de vôos que ele tem. Para cada vôo os contadores do aeroporto de partida e de destino são incrementados. Ao final basta ver qual o maior número de vôos que um aeroporto tem em uma passada pelo vetor e posteriormente percorrer o vetor imprimindo todos aeroportos com o mesmo número de vôos que o máximo.
Código do Andrei para o problema: http://codepad.org/8cPuTEnU
Subscribe to:
Posts (Atom)