Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.
Submit All submissions Best solutions PDF Back to list

EDUPT09 - DNA

A análise genômica teve avanços significativos nessa última década, culminando com o completo mapeamento do genoma humano.

Há muitas formas de armazenar os dados gerados por esse mapeamento, mas uma das formas mais comuns de manipular os elementos é com o uso de listas duplamente encadeadas, que contém a informação das bases de DNA na ordem quem que parecem em um gene. Cada tipo de base é representada por um caracter.

As análises desses dados vão de contagem à simulação de crossover. A contagem precisa ser realizada para cada gene.

E nesse caso, se conta o número de vezes que cada elemento aparece no gene, gerando uma nova lista tendo como informações a base e quantas vezes ela aparece no gene. Computacionalmente falando o gene é representado por uma lista simplesmente encadeada e as informações da contagem, em uma lista ordenada (por quantidade encontrada da base, e do caracter da base para casos de empate) duplamente encadeada. Vale lembrar que um vetor não consegue armazenar a quantidade de informações de um gene e que uma base pode, em tese, não estar presente em um gene

 

 

ENTRADA

 Cada linha contem um inteiro N, de 10 a 248 956 422 pares de bases, que indica a quantidade de pares do gene a ser analisado.

 Na sequencia há N linhas da entrada corresponde ao mapeamento de um gene, cada linha contém dois caracteres representando as bases do DNA (cada caracter pode ser A,T,C ou G)

 A leitura do 0 indica o fim da análise

  

SAÍDA

 Para cada gene, são produzidas 4 linhas de saída, contendo o caracter que representa a base e quantas vezes a base apareceu no gene, seguida de uma linha em branco

 

 EXEMPLOS

  

Entrada

72

T C

G A

C T

T T

A G

A T

T T

A G

C C

G T

G G

A C

T C

C C

G G

C G

G G

G T

G A

G C

A A

G C

A T

A A

C A

A C

A G

A T

G C

G A

A C

T A

C A

A G

G A

T A

T G

T G

A C

C C

T C

A A

T C

G G

A G

T C

C G

A T

G G

A T

A A

A G

C A

C G

A T

G G

C A

C A

C T

G A

C T

T C

T C

T C

A C

C A

A T

G C

T G

G A

C T

T T

10

C T

G G

C G

T G

A G

G C

T C

C T

A C

A C

0

 

SAÍDA

T 32

C 36

G 36

A 40


A 3

T 4

G 6

C 7

 

 

 
Submit solution!
Added by:IFTM_Maratona
Date:2022-10-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C
hide comments
2022-10-20 16:11:00
#include <stdlib.h>
#include <stdio.h>

struct no
{
int info;
struct no* prox;
};
typedef struct no No;

struct nod
{
int info;
struct nod* prox;
struct nod* ant;
};
typedef struct nod Nod;

struct listad
{
Nod* ini;
Nod* fim;
};
typedef struct listad Listad;

Listad* cria_listad()
{
Listad* novalista;
novalista = (Listad *)malloc(sizeof(Listad));
novalista->ini = novalista->fim = NULL;
return novalista;
}
Nod* cria_nod(void* valor)
{
Nod* novo = (Nod*)malloc(sizeof(Nod));
novo->ant = novo->prox = NULL;
novo->info = valor;
return novo;
}
Listad* insere_inicio_listad(Listad *L, void* valor)
{
Nod *novo= cria_nod(valor);

if (L == NULL)
{
L = cria_listad();
L->ini = L->fim = novo;
}
else
{
if (L->ini == NULL)
L->ini = L->fim = novo;
else
{
novo->prox = L->ini;
L->ini->ant = novo;
L->ini = novo;
}
}
return L;
}
Listad* insere_fim_listad(Listad* L, void* valor)
{
Nod *novo = cria_nod(valor);

if (L == NULL)
{
L = cria_listad();
L->ini = L->fim = novo;
}
else
{
if(L->ini == NULL)
{
L->ini = L->fim = novo;
}
else
{
novo->ant = L->fim;
L->fim->prox = novo;
L->fim = novo;
}
}
return L;
}
void* remove_inicio_listad(Listad *L)
{
Nod* aux;
void* resposta = NULL;//quando nao tem nada pra remover
if (L!=NULL)
if (L->ini != NULL)
{
aux = L->ini;

if (L->ini != L->fim)
{
L->ini->prox->ant = NULL;
L->ini = L->ini->prox;
}
else
L->ini = L->fim = NULL;

resposta = aux->info;
free(aux);
}
return resposta;
}
void* remove_fim_listad(Listad *L)
{
Nod* aux;
void* resposta = NULL;

if(L != NULL && L->fim != NULL)
{
aux = L->fim;
if(L->ini != L->fim)//mais de um elemento na lista
{
L->fim->ant->prox = NULL;
L->fim = L->fim->ant;
}
else//so tem um elemento na lista
L->ini = L->fim = NULL;

resposta = aux->info;
// free(aux);
}
return resposta;
}
Listad* libera_listad(Listad *L)
{
Nod *aux = L->ini;

while (aux != NULL)
{
L->ini = L->ini->prox;
free(aux);
aux = (Nod*)L;
}

free(L);
return NULL;

}
Listad* divide_lista(Listad *L, int nro_elementos)
{
Nod *aux = L->ini;
Listad *L2 = cria_listad();
while (nro_elementos > 0)
{
aux = aux->prox;
nro_elementos--;
}
L2->ini = aux;
L2->fim = L->fim;
L->fim = aux->ant;
L->fim->prox = NULL;
L2->ini->ant = NULL;

return L2;
}
No* cria_no(int valor)
{
//alocar um nó
No* novo = NULL;
novo = (No*) malloc (sizeof(No));
//inicializar campos
novo->prox = NULL;
novo->info = valor;
return novo;
}

No* insere_inicio(No* L, int valor)
{
No* novo;
if (L ==NULL)
{
L = cria_no(valor);
}
else
{
novo = cria_no(valor);
novo->prox = L;
L = novo;
}
return L;
}
No* insere_fim(No* L, int valor)
{
No* novo = cria_no(valor);
No* cont = L;

if (L == NULL)
L = novo;
else
{
while(cont->prox!=NULL){
cont=cont->prox;
}
cont->prox=novo;

}
return L;
}
void mostraL(No*L)
{
No* cont=L;
while(cont!=NULL){
printf("%d ",cont->info);
cont=cont->prox;
}
printf("\n");
}

int main()
{
int i=0, n=0, entrada=0;
Nod* ND;
Listad* LD;

printf("Quantidade de linhas: ");
scanf("%d", &n);

printf("Insira suas %d bases: \n");

for(i=0;i<n;i++){
if(entrada!=0){
scanf("%c",&entrada);
LD=insere_fim_listad(Listad* LD, void* entrada);
}

}
return 0;
}
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.