2262. Citystar

单点时限: 2.0 sec

内存限制: 256 MB

On planet Citystar the cities look somewhat like stars. There’s a small round city center from which straight line streets come out. People in one street feel related and between different streets there’s some sportive rivalry. They have programming contests in which each street participates with one team. The organizers want to suggest good team members to the streets and to be unbiased, they ask an alien (you) to help them.

Each street has houses only on one side of the street (numbered 1, 2, 3, … starting at the city center), each house has the same size and in each house there’s at most one programmer (they just can’t live together). For each street you’ll get the house numbers of its programmers. Now the idea is that a team is better the more often it practices, and that the closer the members live to each other, the more often they meet to practice. To be precise, we’ll want to have the smallest range of houses that covers five programmers (three regular members, one substitute, one coach). For example if you choose house numbers 65, 71, 64, 61 and 81 then their range is 21 houses (81-61+1). If there are several possible teams with the same smallest size range, pick the one that lives closest to the city center (where the contest takes place), i. e. with the smaller house numbers.


The first line contains the number of scenarios. Each scenario describes one street and is given on a single line. The first number tells you the number of programmers in the street (from 5 to 100 000), then follows one house number for each programmer (from 1 to 10 000 000).


The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print one line describing the chosen team members in the format shown below. First print the range, then the house numbers in sorted order (with a space before each number). Terminate each scenario with a blank line.


10 65 2 71 123 7 45 64 4 61 81
16 111 103 117 105 102 113 119 107 11 3 17 5 2 13 19 7
Scenario #1:
21: 61 64 65 71 81
Scenario #2:
10: 2 3 5 7 11

1 人解决,3 人已尝试。

1 份提交通过,共有 11 份提交。

9.9 EMB 奖励。

创建: 13 年,8 月前.

修改: 2 年,6 月前.

最后提交: 9 年,3 月前.

来源: TUD Programming Contest 2006 (Training Session), Darmstadt, Germ