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