루미 알고리즘

#1344골드Rövarspråket

PO 2014 온라인 예선코딩출제 Johan Sannemo스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

I rövarspråket översätter man text man skrivit genom att ersätta alla konsonanter x med xox, medan alla vokaler är oförändrade. T.ex. översätts hej till hohejoj, moo till momoo och ojoj till ojojojoj.

Oskar har precis lärt sig rövarspråket, men glömmer ibland bort att ändra vissa konsonanter. Oskar översätter alltså bara en delmängd av konsonanterna på ovanstående vis. Du kommer att få en ursprungstext och en potentiell översättning som Oskar har gjort. Du ska avgöra om det är möjligt att Oskar översatte den första strängen till den andra enligt beskrivningen ovan.

Om Oskar hade skrivit hejoj kan den ursprungliga texten till exempel varit hej eller hejoj. För tydlighets skull så definierar vi följande bokstäver som vokaler: a,e,i,o,u,y och alla andra bokstäver är då konsonanter.

Indata

Den första raden innehåller ordet som vi undrar om det kan ha varit usprungstexten. Den andra raden innehåller ett ord som Oskar har skrivit. Båda orden innehåller minst ett tecken och bara tecken a-z och endast små bokstäver. Ingen sträng är längre än 1000 tecken.

Utdata

Utdata ska bestå av ett enda ord: ja om det är möjligt att det andra ordet är en översättning av det första, annars nej. Svaret ska alltså vara ja om och endast om det går att välja någon delmängd av konsonanterna i det första ordet och applicera rövarspråktransform så att man får det senare ordet.

Poängsättning

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

GruppPoängvärdeGränser
120Strängarna är max 20 tecken långa
230Strängarna är max 100 tecken långa
350Inga ytterligare begränsingar.

Förklaring av exempelfall

Förklaring av exempelfall 1: det spelar ingen roll vilken av konsonanterna som Oskar väljer att applicera rövarspråkstranform på - så länge han väljer precis ett av de j som finns. Låt säga att Oskar glömde att omvandla alla j utom det första - då förvandlas ojojoj till ojojojoj. Svaret är alltså "ja".

Förklaring av exempelfall 2: det är omöjligt att omvandla den första strängen till den andra. Ett sätt att visa detta på är att observera att det i den första strängen finns två j intill varandra, vilket innebär att det alltid kommer finnas två j intill varandra. Alltså går det inte att omvandla den första strängen till den andra, och svaret är "nej".

예제

예제 1

입력
ojojoj
ojojojoj
출력
ja

예제 2

입력
ojjoj
ojojojoj
출력
nej

예제 3

입력
lolf
lolfof
출력
ja

출처 표기

출처: Programmeringsolympiaden 2014년 온라인 예선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.