Parte 2 da T5: Algoritmo Guloso

Esta parte recebe como entrada o número n e uma sequência de inteiros entre 1 e n representando uma sequência X de buscas. Você deve executar o algoritmo guloso visto em aula nos pontos da visão geométrica da sequência X. Para tanto, você deve implementar a rotina GreedyASS, descrita no arquivo das interfaces.

A saída da parte 2 deve ser um conjunto AS que contém os pontos da visão geométrica da sequência X. Se a sequência X tem comprimento m, sua implementação do algoritmo guloso deve consumir tempo O(mn).

Descrição da entrada:

A primeira linha da entrada contém o valor do inteiro n.
A linha seguinte contém uma sequência de inteiros, cada um entre 1 e n.

Descrição da saída:

Sequência de duplas de inteiros, uma por linha, representando os pontos do conjunto final produzido pelo seu algoritmo.

Exemplo de entrada para a parte 2: 

10
3 8 10 4 5 2 6 9 1 7
Saída esperada para esta entrada: 
3 1
3 2
8 2
8 3
10 3
3 4
4 4
8 4
4 5
5 5
8 5
2 6
3 6
4 6
5 7
4 7
6 7
8 7
8 8
9 8
10 8
1 9
2 9
4 9
8 9
6 10
4 10
7 10
8 10

Parte 3 da T5: Certificação de conjunto arboreamente satisfeito

Esta parte recebe um conjunto de pontos exatamente no formato de saída do algoritmo guloso: um ponto por linha da entrada. Você deve executar o algoritmo visto em aula neste conjunto de pontos para decidir se esse conjunto é ou não arboreamente satisfeito. Para tanto, você deve implementar a rotina CheckASS, descrita no arquivo das interfaces.

A saída da parte 3 deve ser ASS se o conjunto dado for AS, e se o conjunto não for AS, a saída deve ser um par dos pontos dados que está arboreamente insatisfeito, impressos no formato dos exemplos abaixo.

Adicionalmente a rotina pode ser acionada em modo DEBUG, no qual ela deve imprimir, durante sua execução, o estado da treap mantida pelo algoritmo após processar os pontos de cada linha.

Se os pontos tem x-coordenadas entre 1 e n e há t pontos na coleção dada, seu algoritmo deve consumir tempo O(tn).

Descrição da entrada:

A entrada consiste em uma sequência de linhas, cada uma com uma dupla de inteiros que representa as coordenadas de um ponto do conjunto. Os pontos são dados em ordem crescente de y-coordenada.

Descrição da saída:

Com o modo DEBUG desacionado:

Caso o conjunto seja arboreamente satisfeito, deverá imprimir ASS. Caso o conjunto não seja arboreamente satisfeito, deverá imprimir um par de pontos arboreamente insatisfeito.

Com o modo DEBUG acionado:

Deve imprimir uma treap válida por instante. Ao final, deve imprimir a saída normal que é impressa fora do modo DEBUG.

Exemplo 1 de entrada: 

3 1
3 2
8 2
8 3
10 3
3 4
4 4
8 4
4 5
5 5
8 5
2 6
3 6
4 6
5 7
4 7
6 7
8 7
8 8
9 8
10 8
1 9
2 9
4 9
8 9
6 10
4 10
7 10
8 10
Saída esperada para o exemplo 1 com o modo DEBUG acionado: 
Time = 1 -----------------
         1 9
      2 6
   3 1
         4 4
            5 5
               6 7
                  7 10
      8 2
            9 8
         10 3

Time = 2 -----------------
         1 9
      2 6
   3 2
         4 4
            5 5
               6 7
                  7 10
      8 2
            9 8
         10 3

Time = 3 -----------------
            1 9
         2 6
      3 4
         4 4
            5 5
               6 7
                  7 10
   8 3
         9 8
      10 3

Time = 4 -----------------
            1 9
         2 6
      3 4
         4 4
            5 5
               6 7
                  7 10
   8 4
         9 8
      10 8

Time = 5 -----------------
            1 9
         2 6
      3 6
   4 5
         5 5
            6 7
               7 10
      8 5
            9 8
         10 8

Time = 6 -----------------
            1 9
         2 6
      3 6
   4 6
      5 7
            6 7
               7 10
         8 7
               9 8
            10 8

Time = 7 -----------------
         1 9
      2 9
         3 +inf
   4 7
      5 7
            6 7
               7 10
         8 7
               9 8
            10 8

Time = 8 -----------------
            1 9
         2 9
            3 +inf
      4 9
            5 +inf
         6 10
            7 10
   8 8
         9 8
      10 8

Time = 9 -----------------
            1 9
         2 9
            3 +inf
      4 9
            5 +inf
         6 10
            7 10
   8 9
      9 +inf
         10 +inf

Time = 10 -----------------
      1 +inf
         2 +inf
            3 +inf
   4 10
            5 +inf
         6 10
            7 10
      8 10
         9 +inf
            10 +inf

Time = 11 -----------------
            1 +inf
               2 +inf
                  3 +inf
         4 +inf
            5 +inf
      6 +inf
   7 +inf
      8 +inf
         9 +inf
            10 +inf

ASS
Exemplo 2 de entrada: 
1 1
2 1
2 2
3 2
4 4
Saída esperada para o exemplo 2 com o modo DEBUG acionado: 
Time = 1 -----------------
   1 1
      2 1
         3 2
            4 4

Time = 2 -----------------
      1 +inf
   2 2
      3 2
         4 4

Time = 3 -----------------
(3,2) (4,4)
Aqui você encontra mais alguns exemplos.