Robot-toplayıcı
Universitetlərdən birində tələbələrdən biri aviasiya mühərrikinin yığılması prosesini qismən avtomatlaşdırmaq üçün bir robot layihələndirdi.
Mühərrikin yığılması prosesində 26 növ əməliyyat mövcuddur və bunlar latın əlifbasının kiçik hərfləri ilə təmsil olunur. Yığma prosesi n əməliyyatdan ibarətdir. Robot, bu yığma prosesində ardıcıl gələn əməliyyatların bir hissəsini yerinə yetirmək üçün bir dəfə istifadə ediləcək.
Robotun yaddaşı k hüceyrədən ibarətdir və hər hüceyrədə bir əməliyyat saxlanılır. Əməliyyatlar yaddaşda yerləşdikləri qaydada, birincidən başlayaraq ardıcıl şəkildə yerinə yetirilir. Sonuncu əməliyyatı yerinə yetirdikdən sonra robot birinci əməliyyatdan davam edir. Robotu istənilən sayda əməliyyatı yerinə yetirdikdən sonra dayandırmaq mümkündür. Robotdan istifadə iqtisadi cəhətdən məqsədəuyğundur, əgər o, ən azı (k + 1) əməliyyat yerinə yetirərsə.
Verilmiş yığma prosesinə əsasən, robotdan iqtisadi cəhətdən məqsədəuyğun istifadə üsullarının sayını müəyyən edən bir proqram yazmaq tələb olunur.
Giriş məlumatları
Birinci sətirdə robotun yaddaşına yazıla biləcək əməliyyatların sayı k (1 ≤ k < n) qeyd olunub.
İkinci sətir n (2 ≤ n ≤ 200000) kiçik latın hərflərindən ibarətdir və mühərrik yığma prosesini göstərir. Eyni növ əməliyyatlar eyni hərflə göstərilir.
Çıxış məlumatları
Tək bir tam ədəd - robotdan iqtisadi cəhətdən məqsədəuyğun istifadə üsullarının sayını çıxış edin.
Nümunələrə izah
Birinci nümunədə robotdan aşağıdakı əməliyyat ardıcıllıqları üçün iqtisadi cəhətdən məqsədəuyğun istifadə etmək olar:
2-ci əməliyyatdan 4-cü əməliyyata qədər: "aba", bu zaman robotun yaddaşında "ab" əməliyyatları var;
4-cü əməliyyatdan 6-cı əməliyyata qədər: "aca", robotun yaddaşında "ac";
6-cı əməliyyatdan 8-ci əməliyyata qədər: "aba", robotun yaddaşında "ab";
6-cı əməliyyatdan 9-cu əməliyyata qədər: "abab", robotun yaddaşında "ab";
7-ci əməliyyatdan 9-cu əməliyyata qədər: "bab", robotun yaddaşında "ba".