루미 알고리즘

#1483실버Studschiffret

PO 2019 학교 예선코딩출제 Fredrik Ekholm스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Fretchif har hittat på ett revolutionärt chiffer som ingen kommer kunna lösa! S å här går det till: Man väljer en sträng att kryptera och två heltal N och M. Sedan ritar man upp ett rutnät med N rader och M kolumner. Därefter börjar man skriva ut strängen man krypterar en bokstav i taget snett nedåt till höger från översta vänstra hörnet. Om vi numrerar kolumnerna från vänster till höger 1 till M, och raderna uppifrån och ned 1 till N så hamnar första bokstaven hamnar på position (1,1), andra på (2,2), tredje på (3,3) och så vidare. När man kommer till en av rutnätets väggar, så låter man ”bokstavsstrålen” studsa på väggen (se exempelförklaringen). Ifall man vid något tillfälle hamnar på en r uta som det redan står en bokstav i, så tar bokstaven man skulle skrivit och skriver den i nästa lediga ruta man kommer till istället. När alla bokstäver i strängen som krypteras är slut så läser man av rutnätet rad för rad, och det blir det krypterade meddelandet.

Givet ett meddelande som Fretchif krypterat med studschiffret, och givet storleken på rutnätet som användes, skriv ut orginalmeddelandet.

Notera att vissa meddelanden inte går att kryptera med vissa storlekar på rutnät, då det är möjligt att man aldrig kommer till någon ny ledig ruta men fortfarande har bokstäver kvar att placera ut. Här är det dock garanterat att det inte hände när Fretchif krypterade strängen.

Exempelförklaring

Säg att strängen vi ska kryptera är ABCDEFGHIKLMNOPQRST, och att rutnätet har storlek 6 × 13. Så här ser rutnätet ut vid olika tidspunkter i krypteringen:

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

I det här exemplet blir alltså det krypterade meddelandet ATKBSJLCRIMDHNEGQOFP. Exempel 2 är att avkoda ATKBSJLCRIMDHNEGQOFP, vilket då avkodas till ABCDEFGHIKLMNOPQRST.

Indata

På första raden står två heltal 2 ≤ N ≤ 20 och 2 ≤ M ≤ 20, antalet rader och kolumner i rutnätet. På andra raden står en sträng med K bokstäver (1 ≤ K ≤ 30), det krypterade meddelandet. Meddelandet består endast av bokstäverna A till Z och alla bokstäver är stora. Det är garanterat att det finns en möjlig ursprungssträng som ger denna chiffertext.

Utdata

Programmet ska skriva ut en rad med en sträng: orginalmeddelandet, så som det såg ut innan det krypterades.

Poängsättning

GruppPoängGränser
120N=2 och att bokstavsstrålen aldrig studsar på högra väggen.
240Bokstavsstrålen studsar aldrig på högra väggen.
340Inga ytterligare begränsningar.

예제

예제 1

입력
2 20
PORMEIGRGAMRN
출력
PROGRAMMERING

예제 2

입력
6 13
ATKBSJLCRIMDHNEGQOFP
출력
ABCDEFGHIJKLMNOPQRST

예제 3

입력
5 7
SLUIMPEGEHTR
출력
SUPERHEMLIGT

예제 4

입력
15 19
DALIGREKTANGEL
출력
DALIGREKTANGEL

출처 표기

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