Football League
Memory limit: 32 MB
There are teams in a football league (we assume that is even).
During a season each team plays with every other team exactly once.
The season consists of turns.
Every team plays exactly once during a turn.
It is desired for a team to play consecutive matches on different
stadia: one at home stadium, and one away, etc.
Unfortunately it is not always possible to construct such a game schedule
that no team plays twice in a row at home stadium,
or twice in a row away.
When constructing the schedule the number of such situations should
be minimized.
(For example, if a team plays once away, then four times at home stadium
and then once away, it counts as three such situations.)
Your task is to minimize the number of situations in which a team plays
twice in a row at home or away and to construct such game schedule for
the whole season.
The schedule should consist of turns.
Each turn consists of matches -
each team plays exactly one match.
There are matches in the whole season, and every two
teams should play exactly one match against each other.
Each match is played at one of the opponents' stadium -
one team plays at home stadium and the other one plays away.
The total number of situations in which a team plays two consecutive
matches at home or away should be minimal.
Task
Write a program, that:
-
reads the number of teams from the standard input,
-
computes the minimum total number of situations in which a team
plays twice in a row at home or away and constructs the game
schedule,
-
writes the result to standard output.
Input
The first and only one line of the standard input contains one even
integer () - the number of teams.
Output
The first line of the standard output should contain a single integer
- the minimum total number of situations in which a team plays
twice in a row at home or away.
The following lines should contain a game schedule:
the line should contain the description of
the -th turn.
The description of a turn consists of different numbers
from separated by single spaces.
For the pair denotes a
match between teams and . Team plays at
home and team plays away.
Example
For the input data:
4
the correct result is:
2
1 4 2 3
1 2 4 3
2 4 3 1
Task author: Jakub Pawlewicz.