| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 5 | 5 | 1 | 100.000% |
Kuulus tarkvarafirma Interplanetary Software Systems on loomas uut tekstitoimetit, mis suudab töödelda väga pikki väikestest ladina tähtedest koosnevaid ridu. Toote esimesel versioonil on ainult kaks funktsiooni:
Nimetame kahe sõne $s$ ja $t$ erinevuseks $\mathrm{diff}(s, t)$ minimaalset sõnest $s$ sõne $t$ saamiseks vajalike käskude arvu. Näiteks $\mathrm{diff}($'tests','text'$) = 5$: algul kustutame sõne 'tests' lõpust kolm viimast tähte ja seejärel lisame tulemuse lõppu tähed 'x' ja 't'.
Kirjutada programm, mis antud $N$ sõne $S_i$ kohta leiab $\mathrm{diff}(S_i, S_j)$ summa üle kõigi paaride, kus 1ドル \le i \le N$ ja 1ドル \le j \le N$.
Faili esimesel real on tekstiridade arv $N$ (1ドル \le N \le 200,000円$) ja järgmisel $N$ real igaühel üks väikestest ladina tähtedest koosnev mittetühi sõne $S_i$. On teada, et $S_i$ pikkuste summa ei ületa 10ドル^6$.
Faili ainsale reale väljastada otsitav erinevuste summa.
3 a ab aaaaa
20
Kuna $\mathrm{diff}($'a','ab'$) = 1,ドル $\mathrm{diff}($'a','aaaaa'$) = 4$ ja $\mathrm{diff}($'ab','aaaaa'$) = 5$ ning mistahes $s$ ja $t$ korral $\mathrm{diff}(s, s) = 0$ ja $\mathrm{diff}(s, t) = \mathrm{diff}(t, s),ドル saamegi otsitavaks summaks 2ドル \cdot (1 + 4 + 5) = 20$.
4 b aab baaa ba
44
$\mathrm{diff}($'b','aab'$) = 4,ドル $\mathrm{diff}($'b','baaa'$) = 3,ドル $\mathrm{diff}($'b','ba'$) = 1,ドル $\mathrm{diff}($'aab','baaa'$) = 7,ドル $\mathrm{diff}($'aab','ba'$) = 5,ドル $\mathrm{diff}($'baaa','ba'$) = 2$ ja seega vastus ongi 2ドル \cdot (4 + 3 + 1 + 7 + 5 + 2) = 44$.