Mobil Telefonla Yazı Yazmaq#6597
Bir tədqiqat qrupu mobil cihazlarda mətn mesajları yazarkən vaxtı qənaət etmək üçün yeni bir texnologiya hazırlayır. Onlar istifadəçilərin müvafiq düyməni basaraq hər hansı bir hərfi yaza biləcəyi tam klaviaturaya malik yeni bir model üzərində işləyirlər. Bu şəkildə, istifadəçi uzunluğu P olan bir sözü yazmaq üçün P düymə basışına ehtiyac duyur.
Lakin, bu kifayət qədər sürətli deyil. Komanda istifadəçinin yaza biləcəyi ümumi sözlərin lüğətini bir araya gətirəcək. Məqsəd lüğətdə olan sözləri yazmaq üçün lazım olan orta düymə basış sayını azaltmaqdır. Bir söz yazılarkən, növbəti hərf unikal olaraq müəyyən edildikdə, mobil telefon sistemi onu avtomatik olaraq daxil edəcək, düymə basışına ehtiyac olmadan. Daha dəqiq desək, mobil telefon sisteminin davranışı aşağıdakı qaydalarla müəyyən ediləcək:
Sistem heç vaxt bir sözün ilk hərfini təxmin etmir, buna görə də ilk hərf həmişə müvafiq düyməni basaraq əl ilə daxil edilməlidir.
Əgər c_1c_2...c_n qeyri-boş hərflər ardıcıllığı daxil edilibsə və elə bir c hərfi varsa ki, lüğətdə c_1c_2...c_n ilə başlayan hər bir söz həm də c_1c_2...c_nc ilə başlayırsa, sistem c hərfini avtomatik olaraq daxil edir, düymə basışına ehtiyac olmadan. Əks halda, sistem istifadəçini gözləyir.
Məsələn, əgər lüğət 'hello', 'hell', 'heaven' və 'goodbye' sözlərindən ibarətdirsə və istifadəçi 'h' düyməsini basırsa, sistem 'e' hərfini avtomatik daxil edəcək, çünki 'h' ilə başlayan hər bir söz həm də 'he' ilə başlayır. Lakin, 'hel' və 'hea' ilə başlayan sözlər olduğuna görə, sistem indi istifadəçini gözləməlidir. İstifadəçi sonra 'l' düyməsini basarsa, 'hel' qismən sözü əldə edərək, sistem ikinci 'l' hərfini avtomatik daxil edəcək. 'hell' daxil edildikdə, sistem təxmin edə bilmir, çünki söz bitmiş ola bilər, ya da istifadəçi 'o' düyməsini basaraq 'hello' sözünü yazmaq istəyə bilər. Bu şəkildə, 'hello' sözünü yazmaq üçün istifadəçiyə üç düymə basışı lazımdır, 'hell' üçün iki, və 'heaven' üçün də iki, çünki cari daxil edilmiş 'hea' olduqda, sistem ikinci qaydanı təkrar tətbiq edərək sözün qalanını avtomatik daxil edə bilər. Eyni şəkildə, 'goodbye' sözü yalnız bir düymə basışı tələb edir, çünki ilkin 'g' düyməsini basdıqdan sonra sistem bütün sözü avtomatik dolduracaq. Bu nümunədə, lüğətdəki bir sözü yazmaq üçün lazım olan orta düymə basış sayı (3 + 2 + 2 + 1)/4 = 2.00 olur.
Sizin vəzifəniz, verilmiş bir lüğətə görə, yeni mobil telefon sistemi ilə lüğətdəki bir sözü yazmaq üçün lazım olan orta düymə basış sayını hesablamaqdır.
Hər test halı bir neçə sətirdə təsvir edilir. İlk sətir lüğətdəki sözlərin sayını göstərən N tam ədədini ehtiva edir (1 ≤ N ≤ 10^5). Növbəti N sətirin hər biri lüğətdəki bir sözü təmsil edən, İngilis əlifbasından ən çox 80 kiçik hərfdən ibarət olan boş olmayan bir sətir ehtiva edir.
Hər test halında bütün sözlər fərqlidir və bütün sözlərin uzunluqlarının cəmi ən çox 10^6-dır.
Hər test halı üçün lüğətdəki bir sözü yazmaq üçün lazım olan orta düymə basış sayını təmsil edən bir rasional ədəd ilə bir sətir çıxarın. Nəticə lazım olduqda yuvarlaqlaşdırılaraq, ondalık nöqtədən sonra dəqiq iki rəqəm ilə çıxarılmalıdır.
Nümunə 1