Dördbucaqlıların hesablanması
На tor 10x10 ölçüsündə, aşağıda göstərilən beş fərqli dördbucaqlı növünü görə bilərsiniz. (Tor üzərində dördbucaqlı, zirvələri tam ədədi koordinatlara malik olan, tərəfləri yalnız zirvələrdə kəsişən və heç bir daxili bucağı 180 dərəcə olmayan dördbucaqlıdır.) Təbii ki, bu 10x10 torunda təsvir edilə biləcək milyonlarla dördbucaqlının yalnız bir neçəsi göstərilmişdir. Verilmiş NxN toru üçün siz bu tor üzərində qurula biləcək ümumi dördbucaqlıların sayını müəyyən etməlisiniz.
Giriş verilənləri
Giriş məlumatları ən çox 150 test nümunəsi ehtiva edir. Hər bir sətirdə tək bir N (0 < N < 121) ədədi var. Giriş məlumatları N dəyəri sıfır olan bir sətirlə bitir.
Çıxış verilənləri
Girişdə alınan hər bir sətir üçün cavabı ayrıca bir sətirdə çıxarın. Hər bir sətir iki ədəd ehtiva etməlidir. İlk ədəd giriş məlumatlarından alınan N ədədi, ikinci isə NxN toru üçün axtarılan dördbucaqlıların sayıdır. Axtarılan ədədin 64-bit tam ədədi keçməyəcəyi təmin edilir.
Xəbərdarlıq: Bu məsələ müəllifin həllinə alternativ həll yolu yoxdur. Test nümunələrini yoxlamaq üçün tam axtarış həlli yaza bilərsiniz. Beləliklə, kiçik ölçülü torlar (təxminən 22x22) üçün bütün cavabları tapa bilərsiniz, əgər proqramı işə salıb təxminən 14 saat vaxt sərf etsəniz.
Məsləhət: Bu məsələni test etmək üçün sistemdə vaxt 2 saniyədir. Əvvəlcədən hesablama, əgər effektiv həll alqoritmi tapmaqda çətinlik çəkirsinizsə, daha yaxşı bir seçim ola bilər. Hər halda, "kobud güc" metoduna əsaslanan həllin 1.8 Ghz Pentium IV tipli kompüterdə təxminən 200 il işləyəcəyini bildiririk.