Punkti un nogriežņi

Uzdevums

Regulāra N-stūra (N>2) virsotnes ar nogriežņu palīdzību ir savienotas savā starpā. Nogriežņu izvietojumu sauksim par korektu, ja vienlaicīgi ir izpildītas sekojošas īpašības:

• katrs nogrieznis savieno divas virsotnes;
• katra virsotne ir savienota ar ne vairāk kā vienu citu virsotni;
• nogriežņi savā starpā nekrustojas;
• nav iespējams savienot vēl kādu virsotņu pāri tā, lai netiktu pārkāpts kāds no iepriekšējiem noteikumiem.

Zīmējumos redzams viena korekta (pa kreisi) un nekorekta (pa labi) izvietojuma piemērs, ja N=8.



Uzrakstiet programmu, kas ievadītai N vērtībai nosaka, kāds ir dažādo korekto nogriežņu izvietojumu skaits! Arī tad, ja vienu nogriežņu izvietojumu var iegūt no otra ar pagriešanas un/vai atspoguļošanas palīdzību, tie tomēr tiek uzskatīti par dažādiem.

 

Ievaddati

Teksta faila punknogr.dat pirmajā rindā dota naturāla skaitļa N (2<N≤500) vērtība.

 

Izvaddati

Teksta faila punknogr.rez vienīgajā rindā jāizvada naturāls skaitlis - dažādo korekto nogriežņu izvietojumu skaits.

 

Piemērs

punknogr.dat	punknogr.rez
77	229273020380942305237417760698
punknogr.dat	punknogr.rez
6	20

  Visi korektie nogriežņu izvietojumi pie N=6 ir:



Atsauces

Uzdevums izmantots Latvijas 17.informātikas olimpiādē 2004.gadā.
Autors Mārtiņš Opmanis

---

© 2001-2002 olimps! http://www.lio.lv/olimps/