Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VARETAS - Jogo de Varetas

Há muitos jogos divertidos que usam pequenas varetas coloridas. A variante usada neste pro- blema 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 ≤ N ≤ 1.000) no conjunto. Cada uma das N linhas seguintes contém dois números inteiros Ci e Vi, representando respectivamente um comprimento (1 ≤ Ci ≤ 10.000) e o número de varetas com esse comprimento (1 ≤ Vi ≤ 1.000). Cada comprimento de vareta aparece no máximo uma vez em um conjunto de teste (ou seja, os valores Ci são distintos). O final da entrada é indicado por N = 0.

A entrada deve ser lida da entrada padrão.

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.

A saída deve ser escrita na saída padrão.

Exemplo

Entrada:
1
10 7
4
50 2
40 2
30 4
60 4
5
15 3
6 3
12 3
70 5
71 1
0

Saída:
1
3
2

Adicionado por:Wanderley Guimarăes
Data:2007-10-11
Tempo limite:0.805s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Primeira fase da Maratona de Programação - 2007

hide comments
2013-11-24 17:08:52 nameless::chris
Como assim quadrados sao considerados ? Isso soh faz sentisdo pra mim quando n = 1, pois dai so há uma variedade de varetas.
"Mesmo se puder formar um retângulo com mais de 4 varetas, năo deve se considerar."
Se ninguem fala eu ia demorar horas, pensando numa soluçăo, estava pensando que poderia formar um retangulo com quatro vretas e a partir dele unir maistres varetas e formar outro retangulo, pois so assim faria sentido o primeiro caso de teste 1 10 7.

Last edit: 2013-11-25 21:20:37
2013-11-11 16:42:19 Washington
Cada retângulo tem apenas 4 varetas.
Mesmo se puder formar um retângulo com mais de 4 varetas, năo deve se considerar.
Retângulo por definiçăo deve ter os quatro ângulos de 90 graus, entăo quadrados devem ser contados.
2013-03-09 11:37:10 Emerson Leonardo Lucena


Last edit: 2013-03-09 11:37:31
2012-09-11 20:00:09 Cristhian Bonilha
quadrados também săo considerados
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.