KURORO製作公司是一作製造超級鑰匙的公司(茶)。
這次他們發明了一種非常酷炫的鑰匙,叫做kukukey。
而為什麼叫做kukukey呢?因為對應於這種鑰匙的鎖(kukulock)有一種特殊結構,一開始你需要用kukukey的n公分先插入鎖中,旋轉一圈後,再繼續插入n公分,再旋轉一圈,再繼續插入n公分....,總共會轉k次,也就是打開前總共會有k*n公分的鑰匙在鎖裡面,而我們稱這個n叫kuku 值,k則叫轉圈圈率。
因為鎖是鐵作的(意思是很硬XD),所以當你鑰匙深入p*n公分要旋轉時,前面部分的(p-1)*n公分也必須跟著旋轉,可想而知,如果要滿足這樣條件,從kukukey開始插入後每n公分就必須是長一樣的。
現在KURORO公司收到了一堆凹凸不平的鐵條,因為要把某些高出來的地方磨平很廢時又廢力,所以你想直接利用他上面凹凸不平的特性來製作這種鑰匙,因為當kuku值越大時,鑰匙的保護功用就越好(當然也可以賣的越貴),所以你希望盡可能的使kuku值大一點,對了因為鐵條是有方向性的,所以鐵條左端也會是鑰匙左端。
P.S.你不用擔心假如鐵條可以全部插到鑰匙孔裡時要怎麼旋轉,因為他們都會在右端加上塑膠柄,方便旋轉。
第一行有一數k(1<=k<=100)代表要製作的鑰匙的轉圈圈率。
第二行包含一個很長的字串(1<=長度<=5000000),代表鐵條左到右每公分的凹凸情形(同樣的凹凸情形將會以同樣的字母來表示)。
輸出一行一數代表最大的kuku值。
是說因為"kukukey"就是k=2,n=2的一把kukukey。
原TIOJ1531 / INFOR 22nd幹部考(prob H)。
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 10 |
2 | 1 | 10 |
3 | 2 | 10 |
4 | 3 | 10 |
5 | 4 | 10 |
6 | 5 | 10 |
7 | 6 | 10 |
8 | 7 | 10 |
9 | 8 | 10 |
10 | 9 | 10 |