29964번 - Tekstide erinevus 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 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:
- tähe lisamine rea lõppu;
- rea viimase tähe kustutamine (kui rida ei ole tühi).
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.
예제 입력 1
3 a ab aaaaa
예제 출력 1
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$.
예제 입력 2
4 b aab baaa ba
예제 출력 2
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$.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호