| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 8 초 (추가 시간 없음) | 1024 MB | 17 | 13 | 10 | 71.429% |
文字数が多い英単語はしばしば,前後の1文字ずつだけを残し,それ以外の中間部分をその文字数で置き換える形で省略されることがある. たとえば,"internationalization" は "i18n","localization" は "l10n","accessibility" は "a11y" などと略記される. ここではこの略記を一般化し,前後の文字を 1 文字以上であれば好きなだけ残してよいものとし,この表記を「字数略記」と呼ぶこととする. 例えば,"i18n","int13tion","i1ternationalization" はいずれも "internationalization" の字数略記であるが,"i123n","i4national3tion","19n" はいずれも "internationalization" の字数略記ではない.ただし,どの区間も字数に置き換えないそのままの "internationalization" も,"internationalization" の字数略記として有効であるものとする.
あなたは,英小文字のみからなる単語が N 個含まれた辞書を持っており,この辞書内の単語をそれぞれ字数略記に変換した辞書を作ろうと思っている. ここで,もしもある字数略記が変換前の辞書に含まれる複数の単語の字数略記として有効であると,その字数略記だけを見て元の単語を一意に復元することができなくなってしまう.よって,そのような字数略記を変換後の辞書に含めることはできない. 例えば,"love" と "live" がともに辞書に含まれる場合,いずれかでも "l2e" という字数略記に変換してしまうと,"l2e" を見たときに元が "love" だったのか "live" だったのかわからず,復元できなくなってしまう.この場合,例えば "love" を "lo1e","live" を "li1e" と字数略記すれば,いずれも元の単語を一意に特定することができる.
与えられた辞書に対し,字数略記変換後の辞書として考えられるもののうち,変換に使用した整数の和として考えられるものの最大値を求めよ. ただし,単語そのままを字数略記とする場合に使用した整数は,0 であるとみなす.
入力は 50 個以下のデータセットからなる.各データセットは次の形式で表される.
N
s1
s2
...
sN
最初の行は辞書に含まれる単語の個数 N からなる (1 ≤ N ≤1,000).続く N 行には,変換前の辞書に含まれる単語が,各行ごとに 1 つ与えられる.各単語の長さは 3 以上 30 以下であり,英小文字アルファベットのみからなる.辞書に含まれる単語はすべて相異なることが保証される.
入力の終わりは,1 つのゼロからなる行で表される.
各データセットについて,各単語を一意に復元できるよう字数略記に変換するとき,使用した整数の和の最大値を 1 行に出力せよ.
5 abcxxfg abcyyfg abcdefx azcdefg www 3 internationalization localization accessibility 4 love live cat cut 3 class comes cross 2 aaa aaaaaaaaaa 0
16 39 2 6 9