Ciobanasul
Ion vrea sa îsi modernizeze zona de pasunat si sa construiasca niste carari
intre pasunile sale. El are n
pasuni, numerotate de la 1 la n.
O carare va uni doua pasuni. Un drum este format dintr-o succesiune de pasuni,
astfel incat intre doua pasuni consecutive de-a lungul drumului sa existe o carare
de legatura. Lungimea unui drum este egala cu numarul de pasuni aflate pe drumul
respectiv. Pentru a-si face oile fericite el trebuie sa indeplineasca o conditie
stranie: oilor nu le va place cum sunt construite cararile daca exista trei pasuni
p1, p2,
p3 astfel ca drumul cel mai scurt
de la p1 la p2
are aceeasi lungime cu drumul cel mai scurt de la p2
la p3, si de asemenea aceeasi lungime
cu drumul cel mai scurt de la p1
la p3.
Cerinta
Scrieti
un program care sa-i spuna ciobanasului Ion care este numarul de posibilitati
de construire a cararilor care respecta restrictia din enunt.
Date de intrare
Fisierul
de intrare numit grazing.in va
contine pe prima linie un numar intreg n
reprezentand numarul de pasuni.
Date de iesire
Fisierul
de iesire grazing.out va contine
pe prima linie un singur numar reprezentand numarul de modalitati de constructie
a cararilor.
Restrictii si precizari
1
<= n <= 300
Exemplu
grazing.in
grazing.out
Explicatie
3
7
Cele 7 posibilitati sunt
ilustrate in figura urmatoare (in fiecare caz, cu linie subtire sunt marcate cararile
posibile, iar cu linie ingrosata sunt marcate cararile construite):
Cosmin
Negruseri Universitatea
Babes-Bolyai Cluj
Contact:cosminn@gmail.com
