시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 33 | 10 | 10 | 83.333% |
It is few days to Nowruz (Persian new year), and grandpa has invited his family to his garden. There are $k$ kids among the guests. To make the gathering more fun for the kids, grandpa is going to run a game of hide-and-seek.
The garden can be represented by an $m \times n$ grid of unit cells. Some (possibly zero) cells are blocked by rocks, and the remaining cells are called free. Two cells are called neighbors if they share an edge. That is, each cell has up to 4 neighbors: two in the horizontal direction, and two in the vertical direction. Grandpa wants to turn his garden into a maze. For this purpose, he can block some free cells by planting bushes in them. The cells where he plants the bushes are no longer free.
A maze must have the following property. For each pair $a$ and $b$ of free cells in the maze there must be exactly one simple path between them. A simple path between cells $a$ and $b$ is a sequence of free cells in which the first cell is $a$, the last cell is $b$, all cells are distinct, and each two consecutive cells are neighbors.
A kid can hide in a cell if and only if that cell is free and has exactly one free neighbor. No two kids can hide in the same cell.
You are given the map of the garden as input. Your task is to help grandpa create a maze in which many kids can hide.
This is an output-only task with partial scoring. You are given $10$ input files, each describing grandpa's garden. For each input file you should submit an output file with a map of a maze. For each output file you will get points based on the number of kids that can hide in your maze.
You are not supposed to submit any source code for this task.
Each input file describes one grid representing a garden and gives the number of kids $k$ invited by grandpa. The format is as follows:
.
': a free cell,#
': a rock..
': a free cell,#
': a rock,X
': a bush. (Note that the letter X must be in uppercase.)An output file is considered to be valid if all the following conditions are met:
.
' characters in the input map can be changed to 'X
' characters (cells blocked by bushes).If your output for a test case is not valid, your score for that test case will be $0$. Otherwise, the score will be $\min(10, 10 \cdot l/k)$ points. Here, $l$ is the number of kids that can hide in your output maze, and $k$ is the number provided in the input. You will score $10$ points for a test case if and only if your output is a maze in which $k$ or more kids can hide. For each test case there exists a solution that scores $10$ points.
4 5 5 ....# .#..# ...#. ....#
.X.X# .#..# ...#X XX..#
Above is a possible valid output:
Since $l=4$ kids can hide in this maze, this solution will receive $10 \cdot 4 / 5 = 8$ points. The cells in which kids can hide are marked with O
below:
OXOX# .#.O# ...#X XX.O#
The following three outputs are not valid:
.XXX# ...X# XXXX# .#XX# .#.X# X#XX# ...#. ...#X ..X#X XX..# XXXX# ..XX#
In the left output there is no simple path between the free cell in the top left corner and the free cell in the rightmost column. In the two other outputs, for each pair of distinct free cells there are exactly two distinct simple paths between them.
Olympiad > International Olympiad in Informatics > IOI 2017 > Day 1 1-2번
Text