Iniciante Informática - Semana 1

0 Flares Facebook 0 0 Flares ×

Jogo de Varetas

Há muitos jogos divertidos que usam pequenas varetas coloridas. A variante usada neste problema envolve a construção de retângulos. O jogo consiste em, dado um conjunto de varetas de comprimentos variados, desenhar retângulos no chão, utilizando as varetas como lados dos retângulos, sendo que cada vareta pode ser utilizada em apenas um retângulo, e cada lado de um retângulo é formado por uma única vareta. Nesse jogo, duas crianças recebem dois conjuntos iguais de varetas. Ganha o jogo a criança que desenhar o maior número de retângulos com o conjunto de varetas.

Dado um conjunto de varetas de comprimentos inteiros, você deve escrever um programa para determinar o maior número de retângulos que é possível desenhar.

Entrada

A entrada contém vários casos de teste. A primeira linha de um caso de teste contém um inteiro N que indica o número de diferentes comprimentos de varetas (1 \leq N \leq 1000) no conjunto. Cada uma das N linhas seguintes contém dois números inteiros C_i e V_i , representando respectivamente um comprimento (1 \leq C_i \leq 10.000) e o número de varetas com esse comprimento (1 \leq V_i \leq 1.000). Cada comprimento de vareta aparece no máximo uma vez em um conjunto de teste (ou seja, os valores C_i são distintos). O final da entrada é indicado por N=0.

Saída

Para cada caso de teste da entrada seu programa deve produzir uma única linha na saída, contendo um número inteiro, indicando o número máximo de retângulos que podem ser formados com o conjunto de varetas dado.

Exemplo de Entrada Exemplo de Saída
1
10 7
4
50 2
40 2
30 4
60 4
5
15 3
6 3
12 3
70 5
71 1
0
1
3
2

 Para ver a solução, clique aqui

 

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: