Primes’ Problemi
Bir müəllimin ən çətin işlərindən biri yekun imtahanı üçün sual hazırlamaqdır. Dr. Ghavamnia İsfahan Universitetində (UI) "Alqoritmlərin Əsasları" dərsini tədris edir və imtahan üçün maraqlı bir praktiki alqoritmik problem hazırlayıb. O istəyir ki, tələbələr bu problemi ən yaxşı və səmərəli şəkildə həll etmək üçün bütün alqoritmik bacarıqlarını işə salsınlar. Problem belədir: bir halqa, şəkildə göstərildiyi kimi, 1-dən N-ə qədər nömrələnmiş N dairədən ibarətdir. Sizə N tam ədəd verilir. Bu ədədləri hər bir dairəyə ayrı-ayrılıqda yerləşdirin ki, üç qonşu dairədəki ədədlərin cəmi sadə ədəd olsun.
Hər bir test halında bir neçə həll ola bilər və sizin vəzifəniz minimum çəkili cəmi olanı tapmaqdır. Çəkili cəm, hər bir dairədəki ədədin həmin dairənin sıra nömrəsi ilə hasilinin cəmi kimi müəyyən edilir. Məsələn, yuxarıdakı şəkildə çəkili cəm 36-dır (və həmçinin bu minimumdur).
Giriş verilənləri
Girişin ilk sətri test hallarının sayını göstərən tək bir tam ədəd ehtiva edir. Sonra, hər bir test halı üçün bir sətr var. Hər bir test halı bir tam ədəd, N (3 ≤ N ≤ 15) ilə başlayır, bu da dairələrin sayıdır. Sonra N tam ədəd verilir ki, bunlar dairələrə yerləşdiriləcək ədədlərdir (hamısı 1 ilə 100 arasında, daxil olmaqla).
Çıxış verilənləri
Çıxışda hər bir test halı üçün bir sətr olmalıdır. Əgər halqanı qurmaq üçün heç bir yol yoxdursa, "impossible" sözü çıxış edilməlidir, əks halda, minimum çəkili cəmi olan tək bir tam ədəd çıxış edilməlidir.