루미 알고리즘

#1353골드Felskrivning

PO 2015 결선코딩출제 Oskar Werkelin Ahlin, Pär Söderhjelm스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Gunilla ska gå in på sin favorithemsida. Ibland blandar hon dock ihop vissa bokstäver, och råkar istället gå in på en annan hemsida. Intressant nog gör hon aldrig exakt samma fel två gånger i samma adress.

Givet adressen till hennes favorithemsida och en beskrivning av vilka bokstäver hon brukar blanda ihop, skriv ut längden på den lista över addresser som hackers borde registrera för att lura in henne på sin hemsida.

Input

På första raden står en sträng: adressen till Gunillas favorithemsida. Endast bokstäverna a-z samt punkt förekommer, och längden är mellan 2 och 20 tecken. Det är inte nödvändigtvis en verklig adress eller ens en korrekt strukturerad adress. På andra raden står ett heltal N (där 1 ≤ N ≤ 13), antalet grupper av bokstäver som Gunilla blandar ihop. Var och en av de följande N raderna innehåller en sträng med mellan 2 och 26 bokstäver, alla olika och valda bland a-z. Bokstäverna i varje sträng utgör en grupp där alla bokstäver kan blandas ihop med varandra. Exempelvis, om strängen är "boi" innebär det att "b" kan bytas mot "o" eller "i", att "o" kan bytas mot "b" eller "i", och att "i" kan bytas mot "b" eller "o". Ingen bokstav förekommer i mer än en grupp.

Output

Ett heltal: antalet adresser som Gunilla kan hamna på genom att skriva fel minst en gång, men utan att göra exakt samma felskrivning (byta ut en viss bokstav mot en viss annan bokstav) flera gånger.

Poängsättning

Din lösning kommer att testas på två testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

GruppPoängvärdeGränser
130Svaret är mindre än 200 och alla N hopblandnings-strängar har exakt 2 bokstäver
230Svaret är mindre än 10000
340Svaret är mindre än 2 miljarder

Förklaring till exemplen

De potentiella hacker-adresserna i de tre första exemplen är:

po.pe     kartis.com      abbe
so.pe     katris.com      abbi
so.se     kartix.com      ebba
          katrix.com      ebbi
          kattix.com      ibba
          kartiz.com      ibbe
          katriz.com
          kattiz.com

Notera avsaknaden av exempelvis "karris.com" och "ebbe" där samma fel gjorts två gånger.

예제

예제 1

입력
po.se
1
sp
출력
3

예제 2

입력
kattis.com
2
tr
sxz
출력
8

예제 3

입력
abba
1
iea
출력
6

예제 4

입력
progolymp.se
3
okmpn
li
st
출력
8819

출처 표기

출처: Programmeringsolympiaden 2015년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.