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.|

MCAIRO - Mercado do Cairo

 

A sua equipe já está fazendo planos para a visita ao Egito. Um dos locais que querem conhecer é o famoso mercado do Cairo. Para economizar tempo, vocês decidiram que vão entrar pela porta no canto sudoeste do mercado e sair pela porta no canto nordeste. Além disso, vocês vão caminhar sempre em direção à saída, ou seja, só vão se deslocar para o norte ou para o leste.
Os vendedores egípcios tem uma regra peculiar. Se você comprar algo de um deles, só poderá comprar novamente de um outro vendedor que seja mais velho. A punição por desrespeitar essa regra é perder uma mão. É claro que isso pode prejudicar sua equipe na final do ICPC. Por este motivo, você acha melhor seguir as tradições locais. Como não é nada elegante dar o mesmo tipo de lembrança para todos seus amigos, você decidiu que, além de seguir as regras do mercado, vai comprar no máximo uma lembrança de cada vendedor. Isto lhe ajudará a ter uma boa variedade de presentes.
O mercado é bem organizado. Os vãos onde as barracas podem ser colocadas possuem a mesma altura e largura. Cada vão é identificado por uma coordenada (x,y) que indica a coluna e linha do mercado que ele se encontra. De uma vista aérea é possível perceber que todos os vãos estão organizados como um quadriculado. As barracas do mercado foram montadas apenas em vãos válidos (e respeitam rigorosamente as medidas do vão). Estando em uma barraca é possível ir para as barracas que ficam estritamente ao norte, ao leste e a nordeste.
Sabendo a idade dos vendedores e a posição da barraca onde cada um trabalha, determine o número máximo de itens que você pode comprar.

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.
A primeira linha de cada instância contém um inteiro N (1 ≤ N ≤ 100 000), indicando o número de vendedores no mercado. Cada uma das próximas N linhas contém dois inteiros cada, xi e yi (1 ≤ xi,yi ≤ 1 000), indicando as coordenadas da barraca em que o i-ésimo vendedor trabalha. Os vendedores estão listados em ordem de idade, do mais novo para o mais velho. Dois ou mais vendedores podem dividir uma mesma barraca. Nesse caso você pode negociar (ou deixar de negociar) com eles em qualquer ordem.
Ir para o norte significa aumentar o valor de y e ir para o leste significa aumentar o valor de x. Todas as barracas se encontram dentro do mercado.

Saída

Para cada instância imprima uma linha contendo um único inteiro, o número máximo de itens que você pode comprar.

Exemplo

Entrada:
5
1
1 1
2
1 1
1 2
2
2 1
1 1
3
1 1
1 2
2 1
4
1 1
1 2
2 1
2 2

Saída:
1
2
1
2
3

Adicionado por:Wanderley Guimarăes
Data:2011-02-20
Tempo limite:0.310s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Seletiva para Maratona de Programacao IME-USP - 2010

hide comments
2015-07-08 20:33:19
Esse problema deve estar bugado, não aceita de jeito nenhum.
2015-05-06 21:35:50
Tem algo muito errado com esse problema, dois códigos com o mesmo resultado e nenhum sendo aceito.
2014-12-11 18:02:51 Leandro Poloni Dantas
Esse é o primeiro problema que tento resolver e năo sei ao certo como devo submeter a soluçăo do problema. Seria uma funçăo? Se for, neste caso qual o formato/tipo da entrada e saída?
Agradeço por qualquer ajuda.
2013-03-25 13:53:50 Ricardo Lopes
Tem algo errado nesse problema.
2012-10-14 02:55:53 Jose Luis Rodrigues Terceiro [UFPI]
ou o SPOJ ta bugado, ou tem uma galera muito obcecada com esse problema, é só olhar em todas as submissőes pra ele.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.