Tarefa 1: Dropsum

Essa semana terminou o prazo do primeiro laboratório de MC202, do qual sou monitor e responsável pela elaboração, criação do gabarito e correção do laboratório. O enunciado pode ser acessado através da minha página.

O problema é basicamente o seguinte: dadas n strings, representando pilhas de bloquinhos com letras, queremos saber o resultado de uma rotação de 90 graus dessas pilhas. Além do mais, se depois da rotação houver bloquinhos sem apoio embaixo, ele cai por ação da gravidade. Um exemplo para clarificar:

ABC
DE
FGHI

vira,

FDA
GEB
HC

Foi pedido para implementar um programinha em C. Apesar do número de caracteres m ser limitado a 100.000, não é possível alocar uma matriz “cheia”, pois pode haver 100.000 palavras de 1 caractere ou 1 palavra de 100.000 caracteres. A ideia inicial é então alocar cada linha da matriz com o tamanho exato de cada string. Aí percorremos da primeira até a última coluna e então da última até a primeira string, imprimindo os caracteres.

Porém, esse algoritmo tem complexidade O(max_len*n), onde max_len é o tamanho da maior string e n o número de strings. Ora, existe um caso com 100.000 caracteres mas max_len = 50.000 e n = 50.000 (consegue me dar um exemplo?).

A ideia agora é alocar uma estrutura auxiliar, que corresponderia à matriz rotacionada. Para isso precisamos saber o tamanho dela. O número de linhas é fácil: max_len. A primeira coluna dessa matriz tem o tamanho igual ao número de palavras com pelo menos uma letra, a segunda igual às palavras com pelo menos duas e assim por diante. Podemos calcular esse valor da seguinte forma: ao passar pelo j-ésimo caractere de uma string da entrada, incrementamos o contador de j.

Finalmente, uma vez alocada a matriz intermediária, percorremos a partir da última string, mantendo um contador, para cada uma das linhas dessa matriz, contendo a última posição em que foi inserido um elemento. Esse contador começa com zero. Assim, ao percorrer o j-ésimo caractere da string, colocamos ele na linha j e coluna correspondente ao contador j e incrementamos esse contador.

Como estamos percorrendo somente os caracteres da string, pode-se ver que esse algoritmo tem complexidade O(m), onde m é o número de caracteres.

O intuito deste primeiro exercício era relembrar alguns dos conceitos aprendidos em MC102 (alocação dinâmica, ponteiros, etc). Porém, alguns alunos já utilizaram conhecimento aprendido em estruturas de dados e resolveram o laboratório usando listas ligadas.

Os comentários estão fechados.

%d bloggers like this: