루미 알고리즘

#1322다이아Miniröj

PO 2013 훈련 캠프코딩스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

De flesta som suttit vid en dator utan internet-uppkoppling har antagligen testat på att spela Minröj. Minröj spelas på en rektangulär spelplan med RxC stycken celler vars innehåll från början är okänt. Spelaren kan sedan klicka på cellerna för att se dess innehåll. I ett antal celler har minor placerats ut och klickar spelaren på en sådan så är spelet över. I varje cell utan mina finns istället en siffra som talar om hur många minor det finns i cellerna runtom, dvs i de celler med vilka den delar en sida eller ett hörn. Tanken är att dessa siffror ska användas för att lista ut var minorna finns och på så sätt undvika dem.

Rudolf har bestämt sig för att bli en professionell Minröj-spelare. Han har dock inte spelat det förut och tänker därför testa en lättare version, Miniröj, som spelas på ett spelbräde av storlek 2xN. Han har dessutom laddat ner MinesweeperHaXX3000, som genom att utnyttja en mystisk bugg kan avslöja innehållet i alla celler på den nedre halvan av spelplanen. Rudolf känner sig dock inte helt säker ändå, och ber dig att skriva ett program som givet den informationen han fått kan avgöra vilka celler som är säkra att klicka på.

Indata

På den första och enda raden finns en sträng av längd N (1 ≤ N ≤ 50000). Denna beskriver spelplanens nedre halva, och varje tecken är antingen ett 'X', vilket innebär en mina, eller ett heltal d, 0 ≤ d ≤ 5, som beskriver att det finns d minor i närheten av rutan.

Utdata

Om det inte finns någon giltig spelplan som är kompatibel med indata ska programmet skriva ut 'fel' på en rad (notera små bokstäver). Skriv annars ut en sträng med N tecken - 'S', 'O' eller 'X' - beskrivande cellerna på den övre halvan av spelplanen. En cell beskrivs med 'S' om cellen inte kan innehålla en mina, 'X' om cellen helt säkert innehåller en mina och 'O' (ett stort 'o') om cellen skulle kunna innehålla en mina men inte behöver göra det. Det sista alternativet innebär att det finns minst en giltig spelplan där cellen innehåller en mina och minst en giltig spelplan där cellen inte gör det, se bilderna för närmare förklaring.

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ängGränser
1401 ≤ N ≤ 10000 och det finns inte några minor i den nedre raden.
260Inga ytterligare begränsningar.

Förklaring av exempelfall 1

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

Figur 1: En illustration av en möjlig lösning för det första exempeltestfallet.

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

Figur 2: En illustration av den andra möjliga lösningen för det första exempeltestfallet.

예제

예제 1

입력
11111
출력
OOSOO

예제 2

입력
121
출력
XSX

예제 3

입력
2211
출력
fel

예제 4

입력
2X4XX32
출력
OOOOSXX

출처 표기

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