Do it for the kids, Chuck! P25738


Statement
 

pdf   zip

html

A gang of n vicious drug dealers is surrounding Walker, the world’s favourite Texas ranger. But do not worry! This would be a critical situation for most people, but not for Walker. He can hit all of them with just a single of his “spinning kicks”.

However, as this is a TV series, the co-guionist Aaron Norris has reminded his brother (the great actor Chuck Norris starring as Walker) that he should take care of several restrictions:

  • Drug dealers can only be hitted increasingly, from drug dealer 1 to drug dealer n. (This is because of the location of the camera.)
  • Walker can only hit each drug dealer i at some specific time ti known in advance. (This is due to the insurance that any actor working with Chuck has to take.) Therefore, Walker cannot hit two drug dealers i < j such that ti > tj with the same spinning kick.
  • The time between two hits should be at least 10 ms. (Even a slow motion camera cannot properly film Chuck’s kicks if they are too quick.) This implies that Walker cannot hit with the same kick two drug dealers i < j such that tjti < 10 ms.

– “We must follow these rules, Chuck”, Aaron says. “I’m sure it’s not hard for you to find the maximum number of guys you can hit with a single spinning kick under these restrictions.”


– “Indeed, it is not”, Chuck replies after thinking for a couple of microseconds.


– “Then, Chuck, please, follow these rules. Do it for the kids, Chuck!”


– “Alright.”

Can you write a program to compute the maximum number of drug dealers that Chuck can hit with a single spinning kick under the given restrictions?

Input

Input begins with a number t ≥ 0. Follow t test cases, each with the number 0 < n ≤ 2000 of drug dealers, followed by t1, …, tn in ms. Each ti satisfies 0 ≤ ti ≤ 109. (Chuck can really give such loooong spinning kicks. Indeed, he is a 6-time Karate World Champion!)

Output

Print t lines with the answers.

Observation

Due to his Cherokee upbringing, Chuck can solve this problem in Θ(n logn) time. But you may be not as good a programmer as Chuck, so the Judge will accept quadratic solutions.

Public test cases
  • Input

    6
    2 2000 2010
    3 7000 7009 7018
    4 8000 7000 6000 5000
    1 100
    10 0 11 45 23 30 48 19 11 60 73
    13 84 85 94 105 45 107 32 68 45 109 67 77 120
    

    Output

    2
    2
    1
    1
    6
    5
    
  • Information
    Author
    Omer Gimémez
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Cinquè Concurs de Programació de la UPC - SemiFinal
    Date
    2007-09-19