Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VIDAMG - Jogo da vida

Você provavelmente já ouviu falar de futebol, um jogo para 22 jogadores. Também provavelmente já ouviu falar de xadrez, que é um jogo para dois jogadores, e de paciência, um jogo para um único jogador. O jogo da vida é um jogo peculiar porque ele é um jogo para... zero jogadores.

O jogo da vida é composto por um tabuleiro 2D infinito, que possui infinitas colunas numeradas (..., -2, -1, 0, 1, 2, ...) e infinitas linhas também numeradas (..., -2, -1, 0, 1, 2, ...). Em cada posição do tabuleiro, há uma célula, que pode estar em dois estados: viva ou morta. O jogo começa em um dado estado inicial, que é completamente especificado por uma lista das células que estão vivas. A partir daí, há várias etapas. Em cada etapa, uma célula vai “nascer” (passar de morta para viva), morrer ou manter o estado atual, de acordo com os seus vizinhos. Os vizinhos de uma célula são as 8 células adjacentes, incluindo as diagonais. As regras que definem o que acontece com cada célula são:

  • Se uma célula viva possui menos de dois vizinhos vivos, ela morre de solidão.
  • Se uma célula viva possui mais de três vizinhos vivos, ela morre por superpopulação.
  • Uma célula viva que possua dois ou três vizinhos vivos continua viva.
  • Uma célula morta com exatamente três vizinhos vivos se torna uma célula viva.

    Em cada etapa, todas as células atualizam seus estados de acordo com essas regras, simultaneamente.

    Dada uma configuração inicial do jogo da vida, calcule e imprima a lista de células vivas após K etapas.

    Entrada

    Há vários casos de teste.

    Cada caso de teste começa com um inteiro N, que representa o número de células vivas na configuração inicial (0 < N ≤ 1000). Em seguida, há N linhas, cada uma das quais descrevendo uma célula viva. Essas linhas possuem dois inteiros L e C que indicam a linha e a coluna, respectivamente, de uma célula viva (-1048576 < L, C < 1048576). Você pode supor que a mesma célula não aparece duas vezes nessa lista. Por fim, a última linha do caso de teste possui um único inteiro K, que representa o número de etapas (0 < K ≤ 100).

    A entrada termina com N = 0, que não deve ser processado.

    Saída

    Para cada caso de teste, imprima uma linha contendo um inteiro C, o número de células vivas após K etapas. Em seguida, imprima C linhas, contendo as coordenadas L e C das células vivas. As células devem ser impressas ordenadas pelo número da linha. Células que possuem o mesmo número de linha devem ser ordenadas pelo número da coluna.

    Exemplos

    Entrada:
    3
    -1 0
    -1 1
    0 0
    1
    0
    
    Saída:
    4
    -1 0
    -1 1
    0 0
    0 1
    

  • Adicionado por:Wanderley Guimarăes
    Data:2012-06-21
    Tempo limite:1s
    Tamanho do fonte:50000B
    Memory limit:1536MB
    Cluster: Cube (Intel G860)
    Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
    Origem:Maratona Mineira 2012

    © Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.