quarta-feira, 14 de dezembro de 2011

[Programação] Jogo de Varetas - Primeira fase da Maratona de Programação 2007

Olá pessoal, nesse post vamos discutir um problema chamado Jogo de Varetas. Esse problema é da Primeira fase da Maratona de Programação 2007.

Link do problema no SPOJ: http://br.spoj.pl/problems/VARETAS/

As entradas do problema são as seguintes: número de diferentes comprimentos de varetas (N); para cada uma das N linhas temos C e V (comprimento e número de varetas com esse comprimento respectivamente).

A saída é determinar a quantidade máxima de retângulos que podem ser formados com o conjunto de varetas dado. Lembrando que cada comprimento de vareta aparece no máximo uma vez em um conjunto de teste!

O programa é finalizado quando N for igual a 0.

Vamos pegar o seguinte caso de teste para entendermos melhor:

4
50 2
40 2
30 4
60 4

Entendendo as entradas...

4 -> esse é o N (número de diferentes comprimentos de varetas, se N = 4 então temos 4 linhas, cada linha com o comprimento e o número de varetas com esse comprimento).
50 2 -> 2 varetas de comprimento 50
40 2 -> 2 varetas de comprimento 40
30 4 -> 4 varetas de comprimento 30
60 4 -> 4 varetas de comprimento 60

Nós sabemos que um retângulo é um quadrilátero que possui 4 lados que podem ou não ser iguais. O que iremos fazer é pegar a quantidade de cada conjunto de varetas e dividi-la por 2, pois o que importa é pegarmos os pares (2 em 2) para formar os lados do retângulo. Então vamos só adicionando a uma varável a (quantidade de varetas)/2 de cada conjunto.

Temos 2 varetas de comprimento 50, então adicionamos 1 à nossa variável de contagem.
Temos 2 varetas de comprimento 40, então adicionamos 1 á nossa variável de contagem.
Temos 4 varetas de comprimento 30, então adicionamos 2 à nossa variável de contagem.
Temos 4 varetas de comprimento 60, então adicionamos 2 à nossa variável de contagem.

Note que o que eu fiz foi pegar 1 par de varetas de comprimento 50, 1 par de varetas de comprimento 40, 2 pares de varetas de comprimento 30 e 2 pares de varetas de comprimento 60.

A nossa variável de contagem possui a quantidade 6, ou seja, 6 pares de lados para formar retângulos. Qual o máximo de retângulos que podemos formar? É só dividir a quantidade de pares por 2 novamente, dá 3, essa é a reposta do nosso caso de teste!

Código



Nenhum comentário: