你最近迷上了H遊戲(Heuristic Game,一款能啟發人coding大進步的遊戲)。
但是你最近卡關了,這讓你覺得很不愉快。
在一次偶然的機會中,你在圖書館發現了一本『H遊戲密笈』,裡面有教你如何破台的方法,因此你迫不及待的想要把那本『H遊戲密笈』借回家。
但不幸的是,那本是鎮館之寶,是不能外借的,所以你只能靠圖書館內的打字機把那本『H遊戲密笈』帶回家(抱歉,影印機故障了。)。
這台打字機非常有趣,操作的方法只有三個動作:
1.在顯示在螢幕上的字串後面加一個字元
2.把顯示在螢幕上的字串從後面刪除掉一個字元
3.把顯示在螢幕上的字串在紙上輸出成一行(但螢幕上的字串並未消失)
(注意:一開始螢幕上顯示的是空字串)
不過,每操作一次,就要給圖書館老伯一枚金幣,但圖書館老伯很機車,所以你不希望給他太多的金幣。
並且使用完之後一定要把螢幕清空,才不會造成下一個使用者的負擔(其實是怕被圖書館老伯罵)
你想要抄的『H遊戲密笈』共有 n 行,你希望以最少的操作次數完整的把『H遊戲密笈』帶回家。
(PS.順帶一提,『H遊戲密笈』是提示式的,所以每一行跟其他行並沒有直接的關係,所以印出順序並不會影響到閱讀)
本題只有一組測試資料:
第一行有一個數字 $N$ ,代表『H遊戲密笈』共有 $N$ 行 ( $0 < N \leq 100,000$ )
接下來有$N$行,代表『H遊戲密笈』的第 $i$ 行(每個字元都會是小寫字母)
每行不會超過$100$個字元。
請輸出一個數字 $k$ ,代表你最少需要 $k$ 個操作才能把『H遊戲密笈』帶回家。
※2008/10/16 測資範圍加入 by peter50216。
原TIOJ1446 / 建中校內培訓第二次模擬考試。
Problem Setter:hallogameboy、peter50216
Adapt From:IOI 08'
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 |