루미 알고리즘

#1480실버Multationer

PO 2019 학교 예선코딩출제 Pär Söderhjelm스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

På den ännu oupptäckta exoplaneten PO-2019 består invånarnas arvsmassa av en sträng, där varje bokstav är antingen A, B eller C. Livets utveckling har gått lite snabbare där än på jorden (exempelvis kan alla lösa programmeringsproblem redan som nyfödda). Anledningen tros vara att istället för vanliga mutationer sker “multationer”, som ändrar alla förekomster av en viss bokstav samtidigt. Bokstaven byts ut mot en sträng som kan innehålla 1, 2 eller 3 bokstäver (se figuren nedan). Detta gör att längden på arvsmassan kan öka ganska snabbt.

Skriv ett program som, givet två strängar S och T, skriver ut den kortaste sekvensen av multationer som ändrar S till T. Det kommer alltid att finnas en lösning med högst 3 multationer.

Indata

På första raden står strängen S. På andra raden står strängen T. Ingen av strängarna innehåller mer än 10 bokstäver och varje bokstav är antingen A, B eller C.

Utdata

Programmet ska skriva ut en rad för varje multation, i den ordningen de sker. Varje rad ska innehålla två strängar: bokstaven som ändras, och strängen som den ändras till.

Om det finns flera optimala sekvenser kan du ange vilken som helst av dem.

GruppPoängGränser
120S och T är lika långa.
240Det finns en optimal sekvens som bara består av samma multation, men eventuellt upprepad flera gånger.
340Inga ytterligare begränsningar.

(그림은 원문 저장소에서 볼 수 있습니다)

예제

예제 1

입력
ABA
CBC
출력
A C

예제 2

입력
BC
CACCAB
출력
B A
C CAB
A CA

예제 3

입력
CAC
CABCACAB
출력
C AB
A CA

예제 4

입력
AABAC
AABBBBAC
출력
B BB
B BB

출처 표기

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