if672 - Algoritmos e Estruturas de Dados

==========
Questão 01
==========

Arquivo fonte: L6Q1.java | L6Q1.c | L6Q1.cpp
Arquivo de entrada: L6Q1.in
Arquivo de saída: L6Q1.out

O arquivo de entrada consiste de vários conjuntos de dados. Cada conjunto de dados contém 3 linhas.
Na primeira linha teremos a informação de que alinhamento queremos. Na segunda linha teremos o valor da string s.
Por fim, na última linha teremos o valor da string t.
A informação do alinhamento será dada pelos números (1 ou 2).
1 - Alinhamento local
2 - Alinhamento semi-global
O fim da entrada é indicado pelo fim do arquivo

Para cada caso da entrada, a saída deve conter três linhas, uma com o custo de alinhar s e t, uma com a seqüência align-s, outra com a seqüência align- t, que contêm as seqüências s e t originais, com " -" onde ocorrer uma inserção ou remoção, como descrito em sala de aula. Após listar cada tripla (custo,align-s, align- t), deixar uma linha em branco.

NOTA:

A prioridade das operações é: Match > Substituição > Remoção > Inserção;
Caso as duas tabelas do alinhamento semi-global encontrem o mesmo "melhor custo", dê à que dá a primeira resposta da especificação (ignora inserções no início e remoções no fim);
Na busca pelo maior valor (maior score do alinhamento), em caso de empate, escolha o que tiver na linha mais abaixo (maior i). Caso ambas estejam na mesma linha, escolha o mais à direita (maior j);
A string s deve ficar na esquerda da tabela (na vertical, indexada pelas linhas da matriz) e a string t em cima (na horizontal, indexada pelas colunas da matriz).
Obedeça com atenção os critérios de desempate acima, para que a resposta desejada seja encontrada.

Entrada exemplo:

1
xyyx
yyxyy

2
xyyx
yyxyy

1
xyyxxy
yxxxxx

2
xyyxxy
yxxxxx

1
x
y

2
x
y

1
xy
yx

2
xy
yx

1
katia
professora

2
katia
professora

1
aaabbb
bbbaaa

2
aaabbb
bbbaaa

1
bbbaaa
aaabbb

2
bbbaaa
aaabbb

1
abab
baba

2
abab
baba

1
baaa
aaab

2
baaa
aaab

1
aaab
baaa

2
aaab
baaa

Saída exemplo correspondente à entrada acima:

Conjunto #1
Score: 6
xyyx--
-yyxyy

Conjunto #2
Score: 6
--xyyx
yyxyy-

Conjunto #3
Score: 6
xyyxxy--
--yxxxxx

Conjunto #4
Score: 4
xyyxxy--
--yxxxxx

Conjunto #5
Score: 0
x
y

Conjunto #6
Score: 0
-x
y-

Conjunto #7
Score: 2
xy-
-yx

Conjunto #8
Score: 2
-xy
yx-

Conjunto #9
Score: 2
-----katia
professora

Conjunto #10
Score: 0
--------katia
professora---

Conjunto #11
Score: 6
aaabbb---
---bbbaaa

Conjunto #12
Score: 6
---aaabbb
bbbaaa---

Conjunto #13
Score: 6
bbbaaa---
---aaabbb

Conjunto #14
Score: 6
---bbbaaa
aaabbb---

Conjunto #15
Score: 6
abab-
-baba

Conjunto #16
Score: 6
-abab
baba-

Conjunto #17
Score: 6
baaa-
-aaab

Conjunto #18
Score: 6
baaa-
-aaab

Conjunto #19
Score: 6
-aaab
baaa-

Conjunto #20
Score: 6
-aaab
baaa-

Obs.:

O formato dos arquivos de saída deverá seguir EXATAMENTE o padrão estabelecido nos exemplos acima.

==========
Questão 02
==========

Arquivo fonte: L6Q2.java | L6Q2.c | L6Q2.cpp
Arquivo de entrada: L6Q2.in
Arquivo de saída: L6Q2.out

A entrada consiste de vários linhas, cada uma com dois inteiros positivos indicando N e K.

O arquivo de saída consiste do K-ésimo tabuleiro que representa uma solução, assim como o número de retrocessos necessários para encontrá-la. Caso não haja tal solução, imprima uma linha com -1.

NOTA:

A busca deve ser feita de cima para baixo;
Cada rainha deve tentar ser colocada em cada posição da linha, da esquerda para a direta, até que a solução seja encontrada. Caso não nenhuma das posições encontre a solução, deve ser feito um retrocesso para a linha anterior;
Dependendo de onde a contagem de retrocessos foi feita, um dos dois resultados abaixo pode ser encontrado. Qualquer das duas saídas será aceita.

Entrada exemplo:

Saída exemplo correspondente à entrada acima (alternativa 1):

Conjunto #1
Retrocessos: 0
Q

Conjunto #2
-1

Conjunto #3
-1

Conjunto #4
-1

Conjunto #5
Retrocessos: 4
.Q..
...Q
Q...
..Q.

Conjunto #6
Retrocessos: 8
..Q.
Q...
...Q
.Q..

Conjunto #7
-1

Conjunto #8
Retrocessos: 105
Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....

Conjunto #9
Retrocessos: 139
Q.......
.....Q..
.......Q
..Q.....
......Q.
...Q....
.Q......
....Q...

Conjunto #10
Retrocessos: 409
.Q......
......Q.
..Q.....
.....Q..
.......Q
....Q...
Q.......
...Q....

Saída exemplo correspondente à entrada acima (alternativa 2):

Conjunto #1
Retrocessos: 0
Q

Conjunto #2
-1

Conjunto #3
-1

Conjunto #4
-1

Conjunto #5
Retrocessos: 4
.Q..
...Q
Q...
..Q.

Conjunto #6
Retrocessos: 7
..Q.
Q...
...Q
.Q..

Conjunto #7
-1

Conjunto #8
Retrocessos: 105
Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....

Conjunto #9
Retrocessos: 138
Q.......
.....Q..
.......Q
..Q.....
......Q.
...Q....
.Q......
....Q...

Conjunto #10
Retrocessos: 400
.Q......
......Q.
..Q.....
.....Q..
.......Q
....Q...
Q.......
...Q....

Obs.:

O formato dos arquivos de saída deverá seguir EXATAMENTE o padrão estabelecido nos exemplos acima.