Trabalho de Faculdade Para quarta 25/11/2009

[mavelcvo 0]

DESAFIO I - Cruzadas Sem Palavras

Embora jogos de palavras utilizando o formato quadrado sejam utilizados há muito tempo -- um quadrado

de palavras foi encontrado nas ruínas romanas de Pompéia -- apenas em 1913 o jornal Sunday New York

World imprimiu um passatempo denominado 'palavras-cruzadas' inventado por Arthur Wynne, um

jornalista que tinha como tarefa inventar semanalmente um passatempo para a seção de diversões do

jornal. O passatempo teve sucesso imediato, tornando-se semanal, e hoje em dia é provavelmente o mais

popular e mais conhecido passatempo com palavras em todo o mundo.

(Para aquelas pessoas um tanto estranhas que não conhecem o jogo, palavras cruzadas é uma forma de

passatempo em que um jogador deve colocar as palavras indicadas por sentenças na vertical e na

horizontal, em um padrão quadriculado, de forma que as letras das palavras que se cruzam sejam

comuns.

Através dos anos diversos formatos e figuras (losango, círculo, quadrado, ...) foram experimentados antes

que o formato retangular familiar com uns poucos quadradinhos pretos (utilizados para separar palavras)

fosse universalmente utilizado.

A configuração de um jogo de palavras cruzadas é a figura formada pelos quadradinhos vazios (os que

devem ser preenchidos com as letras das palavras) e pelos quadradinhos pretos. Para este problema

vamos definir que uma configuração com N linhas e M colunas é válida se e somente se:

• cada coluna contém apenas um quadradinho preto; e

• quadradinhos pretos não estão em colunas adjacentes na mesma linha

Tarefa

Dada uma lista de comprimentos de palavras, que devem ser todas colocadas na direção vertical, sua

tarefa é encontrar uma configuração válida para um jogo de N linhas e M colunas, com M quadradinhos

pretos.

Entrada

A entrada é composta de vários casos de teste. A primeira linha de um caso de teste contém três inteiros

N, M e K, indicando respectivamente o número de linhas no jogo (2 ≤ N ≤ 10000), o número de colunas do

jogo (2 ≤ M ≤ 10000) e o número de comprimentos de palavras (2 ≤ K ≤ 20000). A segunda linha contém K

inteiros Pk, representando os comprimentos das palavras que devem ser colocadas na direção vertical no

jogo (1 ≤ Pk ≤ N-1). O final da entrada é indicado por N = M = K = 0.

Os dados de entrada devem ser lidos da entrada padrão (teclado)

Exemplo de entrada

5 4 10

2 2 2 2 2 2 2 2 2 2

3 4 6

1 1 1 2 1 2

0 0 0

Saída

Para cada conjunto de teste da entrada seu programa deve produzir uma resposta na saída. A primeira

linha da resposta deve conter um identificador do conjunto de teste, no formato "Teste n", onde n é

numerado a partir de 1. Então, se existe uma solução, seu programa deve produzir M linhas na saída,

descrevendo uma configuração válida para o jogo. Cada linha deve conter dois inteiros L e C, separados

por um espaço em branco, indicando a posição de um quadradinho preto (L indica o número da linha e C

indica o número da coluna, com 1 ≤ N e 1 ≤ M). Se existe mais de uma configuração válida para o jogo,

imprima qualquer uma dessas. Se não há uma configuração válida para o jogo, seu programa deve

imprimir uma linha contendo a palavra 'impossivel' (note a ausência de acento). A última linha de uma

resposta deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida

rigorosamente.

A saída deve ser feita na saída padrão (tela)

Exemplo de saída

Teste 1

impossivel

Teste 2

2 1

1 2

2 3

1 4

Restrições

0 ≤ M ≤ 10000 (M = 0 apenas para indicar o fim da entrada)

0 ≤ N ≤ 10000 (N = 0 apenas para indicar o fim da entrada)

0 ≤ K ≤ 20000 (K = 0 apenas para indicar o fim da entrada)

 

Alguem saberia Fazer esse algoritmo??????

 

Obrigado