ZOJ Problem Set - 1367
King ACM 2002 received some clear ground and some money through inheritance.
Terms of the will and testament require the heir to build n towns. He was also
required to build the least quantity of two-way roads between the towns such
that one could travel from any town to any other town even if one road was closed
under repair. Carefully, all such roads must be constructed as geometrically
straight lines. Further, the condition that a traveller be able to get from
one town to another (even with one road closed) needs to be satisfied by traversing
the roads as straight lines in their entirety --- not stopping partway along
one road to switch to another.
The first line of input contains the number of test cases. For each case there is a line containing a single integer n (1 <= n <= 32767). This represents the number of towns to be built.
For each n, print a line containing the maximum number of beer stands possible to build.
Source: Southeast Europe 2002