TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

92.1% (35/38)

Submission's AC Ratio

44.4% (56/126)

Tags

Description

你最近迷上了H遊戲(Heuristic Game,一款能啟發人coding大進步的遊戲)。

但是你最近卡關了,這讓你覺得很不愉快。

在一次偶然的機會中,你在圖書館發現了一本『H遊戲密笈』,裡面有教你如何破台的方法,因此你迫不及待的想要把那本『H遊戲密笈』借回家。

但不幸的是,那本是鎮館之寶,是不能外借的,所以你只能靠圖書館內的打字機把那本『H遊戲密笈』帶回家(抱歉,影印機故障了。)。

這台打字機非常有趣,操作的方法只有三個動作:

1.在顯示在螢幕上的字串後面加一個字元

2.把顯示在螢幕上的字串從後面刪除掉一個字元

3.把顯示在螢幕上的字串在紙上輸出成一行(但螢幕上的字串並未消失)
(注意:一開始螢幕上顯示的是空字串)

不過,每操作一次,就要給圖書館老伯一枚金幣,但圖書館老伯很機車,所以你不希望給他太多的金幣。

並且使用完之後一定要把螢幕清空,才不會造成下一個使用者的負擔(其實是怕被圖書館老伯罵)

你想要抄的『H遊戲密笈』共有 n 行,你希望以最少的操作次數完整的把『H遊戲密笈』帶回家。

(PS.順帶一提,『H遊戲密笈』是提示式的,所以每一行跟其他行並沒有直接的關係,所以印出順序並不會影響到閱讀)

Input Format

本題只有一組測試資料:

第一行有一個數字 $N$ ,代表『H遊戲密笈』共有 $N$ 行 ( $0 < N \leq 100,000$ )

接下來有$N$行,代表『H遊戲密笈』的第 $i$ 行(每個字元都會是小寫字母)

每行不會超過$100$個字元。

Output Format

請輸出一個數字 $k$ ,代表你最少需要 $k$ 個操作才能把『H遊戲密笈』帶回家。

Sample Input 1

3
print
the
poem

Sample Output 1

25

Hints

※2008/10/16 測資範圍加入 by peter50216。

Problem Source

原TIOJ1446 / 建中校內培訓第二次模擬考試。
Problem Setter:hallogameboy、peter50216
Adapt From:IOI 08'

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10
10 3000 65536 262144 11