시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB43375.000%

문제

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 ruta 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.

입력

På första raden står två heltal $2 \leq N \leq 20$ och $2 \leq M \leq 20$, antalet rader och kolumner i rutnätet. På andra raden står en sträng med $K$ bokstäver ($1 \leq K \leq 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.

출력

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

예제 입력 1

2 20
PORMEIGRGAMRN

예제 출력 1

PROGRAMMERING

예제 입력 2

6 13
ATKBSJLCRIMDHNEGQOFP

예제 출력 2

ABCDEFGHIJKLMNOPQRST

예제 입력 3

5 7
SLUIMPEGEHTR

예제 출력 3

SUPERHEMLIGT

예제 입력 4

15 19
DALIGREKTANGEL

예제 출력 4

DALIGREKTANGEL

힌트

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

Efter 6 bokstäver är skrivna Efter 8 bokstäver är skrivna, vi har nu studsat en gång i bottenväggen
Efter 14 bostäver är skrivna, vi har nu även studsat i övre och högra väggen Efter alla 20 bokstäver är skrivna, notera att vi inte skrev över H:et med ett R, utan vi skrev R:et på nästa lediga plats

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

출처

Olympiad > Swedish Olympiad in Informatics > 2019 > Qualification 2번

  • 문제를 만든 사람: Fredrik Ekholm