Autor da análise: 
gabrielrcp
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)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)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.
Discuta o problema
Andei pensando bem nesse, e não cheguei a lugar nenhum.
Imagino que exista uma estrategia gulosa para colocar as rainhas no tabuleiro (estrategia essa que deve ter sido usada pra provar que o numero maximo é aquele do enunciado), mas não tenho idéia de como faze-la.
Dê uma olhada no último exemplo de caso de teste que você vai descobrir rapidinho qual é a estratégia.
Eu também tirei conclusões sobre o algoritmo apenas estudando as entradas e saídas do enunciado com bastante atenção.
Eita, tenho que pegar o costume de olhar para os exemplos com mais cuidado… vi os casos com tamanho maior que 10 e fiquei com preguiça de desenhar :)
Consegui, vlw!
Depois escrevo a descrição do problema.