Dasha got a new camera. She taked some photo about the moon, but the resolution was not too hight. In the photo only two colors are visible, white and black.

Dasha taked a lot of picture and she want to know where is the position of the moon in each photo. The moon has an **r** radius$(r\geq0)$. The Moon is a set of
squares, where each square is colored white from the center of the moon in **r** range. So if a block's center is in the Moon, then the block should be colored white.

Unfurtunetly some stars are visible on the picture.

Write a program which print the largest possible radius of the Moon, and print out the position of the Moon.

Two integer, **w** and **h**- the width and the height of the picture$(1\leq w,h\leq 50)$. In the next **h** lines contain **w** characters. `.`

means black and `*`

means white squares.

First line should contain the largest possible radius. The next line should contain the coordinates of the Moon's center(column, row, numbered from 1).

If there are more possible outputs, then print only the first. Left to Right, Up to Down.

$\color{#888888}\Large\bigodot \hspace{-666200sp}\rule[3px]{1.3px}{5.5px}\hspace{-289000sp}\rule[11.5px]{7.5px}{1.7px}$ $\hspace{1pt}$ Time limit **1** second

$\color{#888888}\rule[4px]{14px}{2.2px}\hspace{-14px}\rule{14px}{2.2px}\hspace{-14px}\rule[-4px]{14px}{2.2px}$ Memory limit **64** MiB

$\begin{array}{ll} \textsf{\large Input example \#1}\hspace{200px}&\textsf{\large Output example \#1}\\ \begin{matrix} \texttt{7}&\texttt{8}\\ \texttt{.}&\texttt{*}&\texttt{.}&\texttt{*}&\texttt{.}&\texttt{.}&\texttt{.}\\ \texttt{.}&\texttt{*}&\texttt{*}&\texttt{*}&\texttt{*}&\texttt{*}&\texttt{.}\\ \texttt{.}&\texttt{*}&\texttt{*}&\texttt{*}&\texttt{*}&\texttt{*}&\texttt{.}\\ \texttt{*}&\texttt{*}&\texttt{*}&\texttt{*}&\texttt{*}&\texttt{*}&\texttt{*}\\ \texttt{.}&\texttt{*}&\texttt{*}&\texttt{*}&\texttt{*}&\texttt{*}&\texttt{.}\\ \texttt{.}&\texttt{*}&\texttt{*}&\texttt{*}&\texttt{*}&\texttt{*}&\texttt{.}\\ \texttt{.}&\texttt{.}&\texttt{.}&\texttt{*}&\texttt{.}&\texttt{.}&\texttt{.}\\ \texttt{.}&\texttt{.}&\texttt{.}&\texttt{.}&\texttt{.}&\texttt{.}&\texttt{*} \end{matrix}& \begin{matrix} \texttt{3}\\\texttt{4}&\texttt{4}\\ \\ \\ \\ \\ \\ \\ \\ \end{matrix} \end{array}$

From there

Bonus problem: Write a program, which print the Moon with a given radius.

One number, **n**.

Some lines. The **k**th line contains the amount of numbers with **k** prime factors **2** to **n**. The lines can't contain **0**.

No limits

$\begin{array}{ll} \textsf{\large Input example \#1}\hspace{200px}&\textsf{\large Output example \#1}\\ \begin{array}{l} \texttt{10}\\ \\ \end{array}& \begin{array}{l} \texttt{4}\\\texttt{4}\\\texttt{1} \end{array}\\ \textsf{\large Input example \#2}\hspace{200px}&\textsf{\large Output example \#2}\\ \begin{array}{l} \texttt{10000}\\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \end{array}& \begin{array}{l} \texttt{1229}\\\texttt{2625}\\\texttt{2569}\\\texttt{1712}\\\texttt{963}\\\texttt{485}\\\texttt{231}\\\texttt{105}\\\texttt{47}\\\texttt{22}\\\texttt{7}\\\texttt{3}\\\texttt{1} \end{array} \end{array}$

No vote yet

1 vote

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in`\(`

...`\)`

or`\[`

...`\]`

to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestMy lame brute logic: try BFS from every *. Since a moon’s center is at an integer grid, we can find the grid through brute force.

Or apply Floodfill to find the regions. Then find the up and down, left and right limits to the region. then test a $3\times 3$ matrix center of grid $(U+D)\div 2,(L+R)\div 2$.

Log in to reply

Can you solve the second problem?

Log in to reply

Do the factors need to be different?

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Thank you! I will try it.

Log in to reply

But wait, how do you define a moon’s radius? also if the stars are arranged around the moon, expanding it? :)

Log in to reply

The biggest perfect circle will be the Moon. So if one block is missing from a perfect circle, then it can't be the Moon. BTW you should write the whole code :)

Log in to reply

I am working on it, maybe finished by tomorrow :)

Log in to reply

BTW, have you found a solution?

Log in to reply

Log in to reply

Log in to reply

Try these!

Log in to reply

Nice!

Log in to reply

Thank you!

Log in to reply