스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Agenten August har ett problem som han behöver din hjälp med. August har två mejladdresser som han använder för att kommunicera med sina agentkollegor. Men han misstänker att någon okänd person sedan en tid tillbaka övervakar varje knapptryckning han gör. Bland annat känner denna person vid det här laget till de två lösenord som August använder till mejladdresserna.
De två lösenorden s_1 och s_2 är textsträngar som består av bokstäverna “a”-“z”. De två lösenorden skrivs in i två olika textrutor, med maxlängd l_1 respektive l_2. Maxlängden hos en textruta är ett positivt heltal som avgör hur många bokstäver som kan stå i textrutan. Om man trycker på en bokstav så hamnar den bokstaven längst bak i textrutan, förutom om antalet bokstäver som står i textrutan är lika med maxlängden, för då händer ingenting.
För att orsaka förvirring skulle August vilja ha en sekvens av knapptryckningar som åstadkommer att s_1 hamnar i den första textrutan och s_2 hamnar i den andra. På så sätt kan den okända övervakaren inte veta vilken mejladdress August använder. Din uppgift är att konstruera en sådan sekvens. Det finns 27 knappar du kan använda, bokstäverna “a”-“z” och “<” (backspace). Om backspace trycks in så försvinner den sista bokstaven i rutan (om det finns minst en bokstav i rutan, annars händer ingenting).
För att få full poäng ska du hitta en sekvens som innehåller så få tecken som möjligt. I vissa testgrupper behöver du bara hitta en sekvens som har max 10^6 tecken.
Indata
Den första raden innehåller ett heltal K ∈ {0, 1}, som indikerar om du behöver hitta en kortaste lösning. Om K = 1 måste du hitta en kortaste lösning, annars räcker det med att den har max 10^6 tecken.
Den första raden innehåller en sträng s_1 och ett heltal l_1 (1 ≤ |s_1| ≤ l_1 ≤ 1000).
Den andra raden innehåller en sträng s_2 och ett heltal l_2 (1 ≤ |s_2| ≤ l_2 ≤ 1000).
Både s_1 och s_2 innehåller bara små bokstäver från “a” till “z”.
Utdata
Om det inte finns en sekvens av knapptryckningar så som beskrivs i uppgiften, skriv ut ett utropstecken “!”.
Annars, skriv ut en sträng bestående av tecknen “a”-“z” och “<”, den sekvens du hittade. Om det finns flera lösningar kan du skriva ut vilken som helst. Om K = 1 ska sekvensen vara så kort som möjligt, annars räcker det med att den har högst 10^6 tecken. Det är garanterat att om det finns en lösning, så finns det en med högst 10^6 tecken.
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.
| Grupp | Poängvärde | Gränser |
| 1 | 7 | Lösenorden består enbart av bokstaven “a”, och K = 0. |
| 2 | 30 | K = 0. |
| 3 | 11 | Lösenorden består enbart av bokstäverna “a” och “b”, och l_1, l_2 ≤ 5. |
| 4 | 15 | l_1, l_2 ≤ 50. |
| 5 | 17 | l_1, l_2 ≤ 200. |
| 6 | 20 | Inga ytterliggare begränsningar. |
Förklaring av exempel 1
När det första tecknet “<” trycks ner så händer ingenting eftersom det inte står något i rutorna. Efter de följande fyra knapptryckningarna kommer det stå “bara” i den andra rutan precis som vi vill, däremot kommer det stå “bar” i den första eftersom den har maxlängd 3. Därefter raderas de två sista bokstäverna så att det står “b” i den första rutan och “ba” i den andra. Till slut skrivs “ra” in så att det står “bra” och “bara”. Notera att eftersom det första tecknet är helt onödigt så hade det gått att lösa med en kortaste sekvens, men det gör inget eftersom K = 0.
예제
예제 1
0 bra 3 bara 5
<bara<<ra
예제 2
0 password 10 secret 12
!
예제 3
1 gg 2 ogeggig 8
ogegg<<ggig