PKU 3091 - Triangular N-Queens Problem

Autor da análise: gabrielrcpgabrielrcp

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3091

Resumo

Acho que a descrição do problema está bem clara, e retirar a história dele acho que só o complica.

Solução

Fixado um $n \geq 1$, vamos chamar de $r$ o número máximo de rainhas que podemos colocar no tabuleiro. O enunciado do problema nos garante que $r = \left\lfloor\frac{2n + 1}{3}\right\rfloor$. Temos que dar as coordenadas de um posicionamento de $r$ rainhas no tabuleiro de modo que nenhuma ataque outra.

Uma maneira de fazer isso é sugerida pelos exemplos do enunciado. Eu encorajo a todos a olhá-los antes de ler, que é bem direto de descobrir a estratégia. Vou descrevê-la a seguir, e depois provar que ela é de fato um posicionamento válido.

Vou usar o mesmo sistemas de coordenadas que é pedido na saída, numerando a partir de 1, contando as linhas de cima para baixo e as colunas da esquerda pra direita. Note que nessa notação, uma casa $(i, j)$ ataca uma casa $( i\prime, j \prime)$ se e somente se:

(1)
\begin{cases} i = i \prime & \mathrm ou \\ j = j \prime & \mathrm ou \\ i - j = i \prime - j \prime \end{cases}

Começamos colocando uma rainha na posição $(n-r+1, 1)$. A seguir, se colocamos a última rainha na posição $(i, j)$, colocaremos a próxima na posição $(i+1, j+2)$. Faremos isso enquanto pudermos, isso é, até tentemos colocar uma rainha numa posição $(i,j)$ tal que $j > i$. Em vez disso, colocaremos uma rainha na posição $(i, 2)$, e continuaremos com a estratégia anterior (colocar a próxima na posição $(i+1, j+2)$ até que $i = n$.

Sempre colocamos uma rainha por linha, e colocamos primeiro elas nas colunas ímpares, e depois nas pares. Assim nenhuma delas vai se atacar por estar na mesma linha ou mesma coluna contando da direita.

Note ainda que, na primeira rainha que colocamos, teremos que $i - j = n-r$, e essa quantidade vai diminuindo em 1 a cada nova rainha que colocamos, até chegar a zero, que é quando começamos a colocar as rainhas em colunas pares. Depois disso, ela vai de novo diminuindo em 1 até chegarmos à última linha.

Na primeira etapa, nós colocamos $n - r + 1$ rainhas, enquanto que colocamos $r - (n-r+1) = 2r - n - 1$ rainhas na segunda. Assim a posição da última rainha será $(n, 4r - 2n - 2)$. Dessa forma, se calcularmos o $(i-j)$ da primeira rainha colocada menos o $(i-j)$ da última, vamos obter:

(2)
\begin{align} (i-j)_{\mathrm{ini}} - (i - j)_{\mathrm{fim}} = 3r - 2n - 2 \leq 3 \frac{2n+1}{3} - 2n - 2 = -1 < 0 \end{align}

Assim $(i-j)_{\mathrm{ini}} < (i - j)_{\mathrm{fim}}$, e portanto, nunca colocamos colocamos duas rainhas se atacando por estarem na mesma coluna contando da direita. Isso ainda mostra que a posição final é de fato uma posição no tabuleiro, assim nosso posicionamento é válido.

Essa prova está meio (bem) mal escrita, o problema é que isso é cheio de índices e contas, então fica difícil explicar. Desenhem o algoritmo, junto com essa conta acima, que fica claro que essa estratégia funciona.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License