IF096 - Algoritmos e Estruturas de Dados

==========
Questão 1
==========
Arquivo fonte: L4Q1.c | L4Q1.cpp | L4Q1.java
Arquivo de entrada: L4Q1.in
Arquivo de saída: L4Q1.out

O arquivo de entrada consiste de vários conjuntos de dados. Cada conjunto começa com uma linha contendo o número X de vértices do grafo. As próximas X linhas de cada conjunto contêm as listas de adjacências do grafo. O primeiro número de cada uma das X linhas é um inteiro N tal que 1 <= N <= X. Depois seguem vários pares de inteiros. Cada par possui um vértice V adjacente ao vértice N e o peso Pda aresta (N, V). A lista de pares termina quando o primeiro termo desse par é 0(zero) (esse par não deve ser considerado). Queremos identificar a árvore de menor custo desse grafo.
O arquivo de entrada é terminado por um conjunto de dados começando com X = 0. Esse conjunto não deve ser processado. Considere que 0 <= X <= 100 e que cada aresta tem peso maior que 0 e menor que 1000.

Entrada exemplo:
3
1 2 5 3 3 0
2 1 5 3 7 0
3 1 3 2 7 0
3
3 2 7 0
2 1 5 3 7 0
1 2 5 0
5
1 2 25 3 30 4 10 0
2 1 25 3 50 5 15 0
3 1 30 2 50 4 40 5 20 0
4 1 10 3 40 5 5 0
5 2 15 3 20 4 5 0
0

Para cada conjunto, você deve imprimir X + 2 linhas. Na primeira linha, imprima o número do conjunto de dado, como mostrado na saída exemplo. Na próxima linha, imprima o peso da árvore encontrada (soma dos pesos de todas as suas arestas). Nas próximas X linhas, imprima a nova lista de adjacências do grafo (árvore), sem os custos.
Note que podem existir várias respostas, dê preferência ao caminho com vértices de menor índice; para tanto, basta direcionar o heap de forma que dê prioridade ao menor índice.
Imprima uma linha em branco após cada conjunto.

Saída do exemplo acima:
Conjunto #1
Peso: 8
1 2 3
2 1
3 1

Conjunto #2
Peso: 12
1 2
2 1 3
3 2

Conjunto #3
Peso: 50
1 4
2 5
3 5
4 1 5
5 2 3 4

==========
Questão 2
==========
Arquivo fonte: L4Q2.c | L4Q2.cpp | L4Q2.java
Arquivo de entrada: L4Q2.in
Arquivo de saída: L4Q2.out

O arquivo de entrada consiste de vários conjuntos de dados. Cada conjunto começa com uma linha contendo o número X de vértices do grafo. As próximas X linhas de cada conjunto contém as listas de adjacências do grafo. O primeiro número de cada uma das X linhas é um inteiro N tal que 1 <= N <= X. Depois seguem vários pares de inteiros. Cada par possui um vértice V adjacente ao vértice N e o peso da aresta (N,V). A lista de pares termina quando o primeiro termo desse par é 0(zero) (esse par não deve ser considerado). Após as X linhas, segue uma linha contendo um inteiro K que é um vértice do grafo. Queremos identificar as arestas que compõem os caminhos mais curtos de K para cada um dos vértices do grafo.
O arquivo de entrada é terminado por um conjunto de dados começando com X = 0. Esse conjunto não deve ser processado. Considere que 0 <= X <= 100 e que cada aresta tem peso maior que 0 e menor que 1000.

Entrada exemplo:
4
4 3 10 1 5 0
2 1 2 3 4 0
3 2 4 4 10 0
1 2 2 4 5 0
2
4
4 3 20 1 70 0
2 1 100 3 10 0
3 2 10 4 20 0
1 2 100 4 70 0
2
4
4 3 20 1 7 0
2 1 100 3 10 0
3 2 10 4 20 0
1 2 100 4 7 0
2
0

Para cada conjunto, você deve imprimir X linhas. Na primeira linha, imprima o número do conjunto de dado, como mostrado na saída exemplo. Nas próximas x-1 linhas imprima um par K -> V: (onde V é um vértice do grafo), o custo do melhor caminho até V e os vértices que compõem o melhor caminho para V.
Note que podem existir várias respostas, dê preferência ao caminho com vértices de menor índice; para tanto, basta direcionar o heap de forma que dê prioridade ao menor índice.
Imprima uma linha em branco após cada conjunto.

Saída do exemplo acima:
Conjunto #1
2 -> 1: Custo = 2 Caminho = 2 1
2 -> 3: Custo = 4 Caminho = 2 3
2 -> 4: Custo = 7 Caminho = 2 1 4

Conjunto #2
2 -> 1: Custo = 100 Caminho = 2 1
2 -> 3: Custo = 10 Caminho = 2 3
2 -> 4: Custo = 30 Caminho = 2 3 4

Conjunto #3
2 -> 1: Custo = 37 Caminho = 2 3 4 1
2 -> 3: Custo = 10 Caminho = 2 3
2 -> 4: Custo = 30 Caminho = 2 3 4

==========
Questão 3
==========
Arquivo fonte: L4Q3.c | L4Q3.cpp | L4Q3.java
Arquivo de entrada: L4Q3.in
Arquivo de saída: L4Q3.out

O arquivo de entrada consiste de vários conjuntos de duas seqüências de caracteres. Cada conjunto consiste em uma linha contendo duas strings do alfabeto Inglês com no máximo n e m caracteres, respectivamente. As duas strings podem estar separadas por um ou mais espaços em branco. Um conjunto em que as duas strings são "#" indica o final do arquivo. Cada caractere das strings serão minúsculos como no exemplo abaixo.

OBS: 0 <= n <= 100 e 0 <= m <= 100, n pode ser diferente de m

Entrada exemplo:

abcdefg abcdeh
bcd abcde
abcde bcgfe
# #

Para cada conjunto, você deve imprimir uma serie de linhas. Na primeira linha, imprima o numero do conjunto, como mostrado na saída exemplo. Na proxima linha imprima o custo "c" mínimo de edicao e nas próximas linhas quais os passos para transformar a cadeia A na cadeia B com este custo.

Os passos podem ser:
R c n - replace A[n] por c;
M c n - ocorreu match de c na posicao n de A;
D c n - delete c da posicao n de A;
I c n - insert c na posicao n de A.

Os passos devem ser apresentados na ordem inversa (como são identificados pelo retrocesso na matriz). Quando houver mais de uma possibilidade de movimento, a escolha deve obedecer à seguinte ordem de prioridades: (1) Match/Substituição, (2) Remoção, (3) Inserção.

Exemplo:

Saída exemplo correspondente a entrada acima:
Conjunto #1
2
R h 7
D f 6
M e 5
M d 4
M c 3
M b 2
M a 1

Conjunto #2
-1
I e 4
M d 3
M c 2
M b 1
I a 1

Conjunto #3
-2
M e 5
R f 4
I g 4
M c 3
M b 2
D a 1

==========
Questão 4
==========
Arquivo fonte: L4Q4.c | L4Q4.cpp | L4Q4.java
Arquivo de entrada: L4Q4.in
Arquivo de saída: L4Q4.out

OBS: 0 <= n <= 100 e 0 <= m <= 100, não pode ser diferente de m.

Entrada exemplo:

abca bcab
x b
ace abcde
# #

Para cada conjunto, você deve imprimir três linhas. Na primeira linha, imprima o numero do conjunto, como mostrado na saída exemplo. Na segunda, imprima uma maior subseqüência das duas seqüências e na terceira, uma menor supersequência. Caso alguma das subseqüências ou supersequências for vazia, imprima uma linha em branco.

Saída exemplo correspondente a entrada acima:

Conjunto #1
bca
abcab

Conjunto #2

bx

Conjunto #3
ace
abcde