| Submeter | Todas submissőes | Melhores | Voltar |
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:
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 |