ZOJ Problem Set - 2799
As you may already know, different countries in Europe use different railroad systems. Not only do they use different voltages for their trains, but also the distance between the two rails (gauge) differs. The following table shows some railway gauges used:
A museum has trains from several countries. It needs tracks for every train type in order to show visitors the trains in use. However, since only one train is used at a time, a rail can be used by trains of different types. It follows that for n trains, each requiring a different railway gauge, n + 1 rails are sufficient (each train uses the leftmost rail and a rail that has exactly the required distance to it). But sometimes it is possible to save even more rails.Given the required railway gauges, your task is to construct a railway track that can be used by every train and requires the least number of rails. Note that a train can use any two rails, provided the distance between them is right.
The first line of the input file contains a number representing the
number of test cases to follow. Each test case starts with an integer n
(the number of different railway gauges required).
The next line contains n integers between 1000 and 5000,
each defining one required railway gauge.
The output for each test case consists of three lines:
Source: University of Ulm Local Contest 2005