루미 알고리즘

#1448플래티넘Kryssring

PO 2018 훈련 캠프코딩출제 Simon Lindholm, Måns Magnusson, Nils Gustafsson스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Simon och Måns sitter på tunnelbanan, och spelar ett spel. Simon ritar upp ett n × m rutnät och ritar in ett par kryss och ringar i rutorna. Han skriver även ett tal på varje rad.

Måns uppgift är nu att fylla i rutnätet så att varje ruta har ett kryss eller en ring, så att det finns lika många kryss på varje rad som talet som står där. Målet för Måns är att varje rad, kolumn och diagonal har högst 2 kryss eller ringar i rad.

Simon har ritat ut kryssen och ringarna helt på måfå, så det är inte uppenbart att detta är möjligt. Vi kan dock ge Måns poäng beroende på hur väl han lyckats: vi definierar värdet för en utplacering som antalet gånger det förekommer tre kryss eller tre ringar i rad i någon rad, kolumn eller diagonal (åt båda hållen). Måns ska då försöka få så lågt värde han kan.

Hjälp Måns spela spelet så bra som möjligt!

Indata

Observera: testdatan på detta problem är öppen. Den finns som attachement till problemet, Den första raden innehåller ett heltal 0 ≤ t ≤ 10, ordningstalet för detta testfall. Fallet t = 0 representar exempelfallet, och ska ignoreras (du kan skriva ut vad du vill då).

Den andra raden innehåller två heltal n och m (2 ≤ n, m ≤ 500): höjden och bredden på rutnätet. Den tredje raden innehåller n tal: antalet kryss som måste skrivas in på varje rad. Därefter följer n rader, med m tecken vardera: det ursprungliga rutnätet. Varje tecken kommer att vara antingen “.”, “o” eller “x”, där “.” betyder att rutan ännu inte fyllts i.

Det är garanterat att antalet kryss som finns i varje rad är högst lika med talet som Simon skrivit för den raden.

Utdata

Skriv ut n rader med m tecken vardera: det helt ifyllda rutnätet, där alla “.” bytts ut mot antingen “o” eller “x”.

Notera att Kattis har en storleksgräns på källkod på 128kB. För rutnäten av maximal storlek går det därmed inte att hårdkoda kompletta lösningar i koden.

Poängsättning

Din lösning kommer att få poäng på varje av de tio testfallen.

Varje testfall poängsätts på följande vis. Antag att värdet du åstadkommit på testfallet är X, och det minimala värdet någon deltagare lyckats åstadkomma under tävlingen är X_min. Om X_min ≠ 0, låt X_min' = X_min, annars låt X_min' vara den näst bästa deltagarens värde på det testfallet (som inte är 0). Om X ≥ 2X_min' tilldelas testfallet 0 poäng, annars tilldelas 10(1 - r) poäng, där r = (X - X_min) / (2X_min' - X_min).

Under tävlingen kommer X_min vara satt till ett av domarna framräknat värde. Det betyder att scoreboard kan temporärt visa poäng upp till 200, och det är möjligt att ens poäng på ett testfall kan räknas om till 0 efter tävlingen!

Förklaring av Sample 1

I lösningen på exemplet finns 26 st. vertikala tre-i-rad, 18 st. horisontella, och 32 st. diagonala. Totalt ger detta alltså ett värde på 76.

예제

예제 1

입력
0
10 10
5 2 5 3 3 2 5 5 6 5
.....o..o.
..........
..o.......
.....o....
..........
...x......
.o..x.....
...o......
....xo....
.o........
출력
oxxxxooxoo
oooooxxooo
oxoxooxoxx
ooxxooxooo
oxooxoxooo
oxoxoooooo
ooxoxoxxxo
ooxooxxxox
oxxxxoxxoo
ooxooxxxxo

출처 표기

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