The 7 different possibilities
to build the roads are depicted in the next picture (in each case, the
thin line is a possible road, and the thick line is a built road):
grazing
Shepard
John wants to modernize his grazing zone by building some roads between his
pastures. He has n pastures,
which are identified by numbers from 1
to n. A road will be built between
two different pastures, and any two pastures will have at most one road between
them. A path is a succession of pastures thus any two consecutive pastures on
the path are connected by a road. The length of a path is equal to the number
of it's pastures.
In order to make his sheep happy he needs to fulfill a strange requirement:
the sheep don't like the way roads were built if there are three pastures p1,
p2 and p3
so that the shortest path from p1
to p2 has the same length as
the shortest path from p2 to
p3, and also the same length
as the shortest path from p1
to p3.
Task
Write a program that tells shepard John how many possibilities to build the roads respect the condition mentioned above.
Input data
The input file named grazing.in will have on the first line one integer n, which represents the number of pastures.
Output data
The output file named grazing.out will contain a single line on which it will be written the number of possibilities to build roads between pastures.
Constraints
| grazing.in | grazing.out | Explanation |
| 3 | 7 |
The 7 different possibilities
to build the roads are depicted in the next picture (in each case, the
thin line is a possible road, and the thick line is a built road): |
Time limit: 1 second/test
Cosmin Negruseri
Babes-Bolyai University
Cluj
Contact:cosminn@gmail.com