uCoder | 1266 | Nível: 4 | Tempo Limite: 3
Heap, heap!
Adaptado por Erich Rodrigues
Competição: Interfatecs 2016 1ª Fase
Heaps são estruturas de dados muito interessantes, que permitem solucionar alguns problemas de maneira bem elegante. Um heap é, antes de mais nada, uma árvore. E é uma árvore em que todos os seus níveis estão completos, com eventual exceção do seu último nível. No caso de estar incompleto, o último nível estará preenchido a partir da esquerda, como mostram as figuras 1, 2 e 3. Se em um heap cada nó tem o seu valor maior ou igual ao de cada um de seus filhos, ele é chamado Max-Heap; se ocorrer o inverso, ou seja, cada nó possui um valor menor ou igual ao de cada um de seus filhos, temos um Min-Heap.
Seu objetivo neste problema é determinar se uma árvore binária completa informada é um Max-Heap, um Min-Heap ou nenhum dos dois.
Entrada
A entrada consiste de vários casos de teste. Cada caso é dado em uma linha da entrada iniciada por um inteiro N (2 ≤ N ≤ 25) que indica a quantidade de nós da árvore binária. Seguem-se então N inteiros V (-1000 ≤ V ≤ 1000) correspondentes aos nós da árvore, apresentados a partir da raiz e, em cada nível, os nós são apresentados da esquerda para a direita. Considere que não serão informadas árvores com todos os seus valores iguais. O conjunto de entradas deve ser lido até a condição de fim de arquivo ser atingida.
Saída
Caso a árvore lida em um caso de teste seja um Max-Heap, imprimir a string ‘max’ (em minúsculas); caso seja um Min-Heap, imprimir ‘min’ (em minúsculas) e caso a árvore lida não seja nem um Max-Heap nem um Min-Heap, imprimir ‘nada’ (em minúsculas).
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
7 90 68 30 44 53 14 7 |
max |