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.|

SANIDADE - Sanidade

 

Os Alunos de Algoritmos e Estruturas de Dados I, geralmente aprendem o
conceito de listas encadeadas e durante o processo de aprendizado os
professores, geralmente, pedem para que os alunos implementem as suas
bibliotecas de listas encadeadas.
Um problema clássico nas listas é identificado quando os alunos implementam
as listas duplamente encadeadas. Estas listas possuem apontadores para o
próximo elemento e para o anterior. Geralmente as implementações dos alunos
possuem alguns bugs e após algumas inserções e remoções a lista deixar de
ficar sana, isto é, o caminho percorrido de um elemento qualquer PTR1 para
outro elemento PTR2 deixa de ser o inverso do percurso de PTR2 para PTR1.

Os Alunos de Algoritmos e Estruturas de Dados I, geralmente aprendem o conceito de listas encadeadas e durante o processo de aprendizado os professores, geralmente, pedem para que os alunos implementem as suas bibliotecas de listas encadeadas.

Um problema clássico nas listas é identificado quando os alunos implementam as listas duplamente encadeadas. Estas listas possuem apontadores para o próximo elemento e para o anterior. Geralmente as implementações dos alunos possuem alguns bugs e após algumas inserções e remoções a lista deixar de ficar sana, isto é, o caminho percorrido de um elemento qualquer PTR1 para outro elemento PTR2 deixa de ser o inverso do percurso de PTR2 para PTR1.

Então para ajudar os alunos o professor definiu o problema da sanidade:

Dado dois ponteiros PTR1 e PTR2 pertencentes a uma lista duplamente encadeada, que:

 

  • Estes ponteiros existem e não serão passados valores nulos;
  • Podem estar em qualquer posição da lista;
  • PTR1 vem ``antes'' na lista, de PTR2;
  • Pode existir qualquer quantidade de elementos antes de PTR1, depois de PTR2 e entre PTR1 e PTR2.

 

Um subconjunto de uma lista duplamente encadeada é dita sana quando o caminho de PTR1 a PTR2 é o inverso do caminho de PTR2 a PTR1.

 

Para ajudar a identificar listas insanas, o professor fez um patch no Valgrind fazendo um dump da memória pertinente a lista encadeada, ou seja, com que todos os elementos da lista encadeada fossem impressos na tela contendo o endereço daquele elemento e os ponteiros para o próximo e anterior.

Infelizmente o professor já gastou muito tempo implementando o patch e precisa de sua ajuda para implementar um programa que leia o dump da lista duplamente encadeada e diga se a lista está sana ou não.

Entrada

A entrada é composta por um único caso de teste, contendo o dump da lista encadeada de um aluno. A entrada possui diversas linhas. Cada linha possui 3 números inteiros em formato hexadecimal representando, respectivamente, o endereço do elemento, o endereço do elemento anterior e o endereço do próximo elemento. O endereço 0 representa NULL.

As duas primeiras linhas do caso de teste representam os ponteiros de PTR1 e PTR2.

Nem todos os ponteiros fornecidos na entrada precisam, necessariamente, fazer parte do caminho PTR1->PTR2.

Para representar os ponteiros utilize inteiro sem sinal de 64bits.

Saída

A saída deverá conter uma única linha contendo a palavra sana, quando o caminho de PTR1 para PTR2 for o inverso de PTR2 para PTR1  e insana quando não.

Exemplo

Entrada:
a 0 b
f e 0
e d f
b a c
c b d
d c e

Saída:
sana

Entrada:
facada dead babaca dead 0 facada babaca facada 0 Saída: insana

Adicionado por:Bruno Ribas
Data:2014-06-08
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:8o Contest Noturno

hide comments
2014-08-10 03:26:04 gustavo iaguzeski
a saída dada como 'insana' pode ser expressa como uma lista definida pelos seguintes endereços de memória:


dead facada babaca

nesse caso ela năo seria onsiderada uma resposta 'sana'?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.