TopCoder

User's AC Ratio

62.5% (5/8)

Submission's AC Ratio

35.1% (40/114)

Tags

uva

Description

還記得草甘嗎?忘了就去看看TIOJ1676吧!


話說,正當草甘開心的在欣賞超級違和的烏龜塔時,突然開始天搖地動。
一片光芒亮得草甘幾乎睜不開眼。而在那陣陣金光中,似乎有隻烏龜緩緩的步出……

草甘定神一看,那不正是在百年前創辦第一屆ITO的──艸干嗎!?
傳說在疊完神秘的烏龜塔後消失,同時是草甘從小的偶像的艸干,
如今竟顯身在草甘眼前,草甘不禁痛哭流涕、淚濕衣襟。

還不待草甘說出話,艸干便開口了:「你那座烏龜塔流露出了前所未有的光芒。」
「若不是天賦異稟加上無比的熱忱是不可能疊出這種烏龜塔的,你已有資格進入神聖的殿堂。」
「不過在帶你走前,還有最後的試煉,任何一隻想進入殿堂的烏龜都需通過的試煉。」

草甘在哽咽中努力的擠出了一句話:「什麼試煉?」

艸干從殼中拿出了一疊東西並說:「東西我就放這了,今天就必須完成。該怎麼做你會知道。」
「切記,一但失敗,殿堂的入口將被惡鬼所占據,在你死前永不散去。趨時你就再也無法進入。」
言畢艸干就如一陣輕煙消散,只留下了方才那疊物體。

過了許久,草甘好不容易冷靜後上前拿起了那疊物體。
那疊物體是由$13$片長得一模一樣的$5 \times n$的板子所疊起來。
而在這片$5 \times n$的版子上有若干個格子上有著奇怪的印記。
草甘觀察後發現幾件神奇的事情:

  1. 當這$13$個版子一起排成一個$5 \times k$的長條時(可以相疊),會出現很強的違和波。
  2. 只要有任兩個印記疊在同個位置,就算中間有隔著別的版子,違和波會全消失。
  3. 隨著$k$的減小,違和波的強度會以不可思議的速度增加。
  4. 經過翻轉的版子會和其他版子互斥,一靠近就彈開。

望了望身旁那超違和的烏龜塔,草甘突然懂了,
所謂的試煉,就是要將這些版子排出最短的$5 \times k$長條,達成最高的違和度吧!

請問,所有草甘能疊出的$5 \times k$長條中, $k$最小到底能多小?

Input Format

每筆測資開頭有一個數字 $n$ 代表版子的長度。
接下來有 $5$ 個長度為 $n$ 的字串描述版子的長相。
如果是 . 代表該格是空白的,如果是 X 代表該格有印記。
以EOF作為結尾。

($5 \leq n \leq 27$)
保證板子的第一行跟最後一行一定有X

Output Format

對每筆測資請輸出一行,該行包含一個數字代表 $k$ 的最小值。

Sample Input 1


6
X.....
......
......
......
.....X
6
X.....
......
......
.....X
...XX.

Sample Output 1

18
30

Hints

第二筆範測如下

1.2.3.4.5.6.7.8.9.A.B.C.D.....
..............................
..............................
.....1.2.3.4.5.6.7.8.9.A.B.C.D
...112233445566778899AABBCCDD.

Problem Source

原TIOJ1729 / Problem Setter : worm
Adapted From : UVa 690
added $\LaTeX$ by Seanliu on 16.10.2020

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1