Boz Zona#5786
Dr. Grey hər gün dünyanın müxtəlif yerlərindən toplanan məlumatları vizuallaşdıran bir məlumat analitikidir. O, mürəkkəb vizuallaşdırma alətlərində çox bacarıqlıdır, lakin ən çox sevdiyi sadə, özünün hazırladığı histogram generatorudur.
Şəkil 1: Histogram
Şəkil 1 onun histogram generatoru tərəfindən avtomatik yaradılan bir histogram nümunəsidir. Histogram, dəyərlərin tezliklərini sütunlar şəklində vizual təsvir edir. Bu nümunədə, 0–9 intervalında olan dəyərlər beş dəfə, 10–19 intervalında olanlar üç dəfə, 20–29 və 30–39 isə hər biri bir dəfə meydana gəlir.
Dr. Grey-in histogram generatoru sadə bir alətdir. Əvvəlcə, histogramın hündürlüyü sabitdir, yəni ən yüksək sütunun hündürlüyü həmişə eynidir və digərləri avtomatik olaraq nisbətən tənzimlənir. İkincisi, sütunların enləri də sabitdir. O, yalnız bərabər interval histogramı yarada bilər, yəni histogramın hər intervalı eyni enə malik olmalıdır (yuxarıdakı nümunədə 10). Nəhayət, hər interval üçün sütun boz rəngdə boyanır, burada ən sol və ən sağ intervalın rəngləri müvafiq olaraq qara və ağdır və sütunların qaranlıq səviyyəsi soldan sağa eyni sürətlə monoton olaraq azalır. Məsələn, Şəkil 1-də dörd sütunun qaranlıq səviyyələri müvafiq olaraq 1, 2/3, 1/3 və 0-dır.
Bu məsələdə, histogramı kağıza çap edərkən mürəkkəb istehlakını təxmin etməyiniz tələb olunur. Sütunu çəkmək üçün lazım olan mürəkkəb miqdarı həm onun sahəsinə, həm də qaranlıq səviyyəsinə nisbətlidir.
Giriş bir neçə datasetdən ibarətdir, hər biri tam ədədlərdən ibarətdir və histogram generatoru üçün dəyər cədvəli və intervalları aşağıdakı formatda göstərir.
n w
v_1
v_2
...
v_n
n histogram üçün ümumi dəyər tezliklərinin sayıdır və birinci sətirdən sonra gələn n sətirin hər biri bir dəyər ehtiva edir. Eyni dəyərin bir neçə dəfə meydana gəlməsi mümkündür.
w intervalın enidir. Bir dəyər v ilk (yəni ən sol) intervalda yerləşir, əgər 0 ≤ v < w, ikinci intervalda isə əgər w ≤ v < 2w və s. Qeyd edək ki, 0 (daxil) ilə w (xaric) arasındakı intervalda heç bir dəyər meydana gəlməsə belə, bu interval ən sol interval kimi qəbul edilməlidir. Ən sağ interval isə datasetdəki ən böyük dəyəri əhatə edən intervaldır.
Aşağıdakıları qəbul edə bilərsiniz.
1 ≤ n ≤ 100
10 ≤ w ≤ 50
0 ≤ v_i ≤ 100 üçün 1 ≤ i ≤ n
Maksimum dəyərin w-dən az olmadığını da qəbul edə bilərsiniz. Bu, histogramın bir neçə intervala malik olduğunu göstərir.
Girişin sonu iki sıfırdan ibarət bir sətirlə göstərilir.
Hər dataset üçün, histogramı çap etmək üçün sərf olunan mürəkkəb miqdarını ehtiva edən bir sətir çıxarın.
Bir ən yüksək sütunu qara rəngə boyamaq üçün bir mürəkkəb vahidi lazımdır. Sütunları boyamaqdan başqa, xətləri və simvolları çəkmək kimi müxtəlif məqsədlər üçün histogram başına 0.01 mürəkkəb vahidi sərf olunur (bax Şəkil 1). Məsələn, Şəkil 1-dəki histogramı çap etmək üçün sərf olunan mürəkkəb miqdarı:
Hər bir çıxış dəyəri onluq kəsr şəklində olmalı və 10^{−5}-dən az bir səhvə malik ola bilər.
Nümunə 1