612 - DNA Sorting
Moderator: Board moderators
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
We know, that data was changed. But problem is: what in new data is different from old one?
It's strange that in one moment 800 people (in which are famous names) changing your status from Acc to other ...
Best regards
DM
PS. In problem description I don't see any changes - limits or algorithms ...
It's strange that in one moment 800 people (in which are famous names) changing your status from Acc to other ...
Best regards
DM
PS. In problem description I don't see any changes - limits or algorithms ...
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Born from ashes - restarting counter of problems (800+ solved problems)
-
- Learning poster
- Posts: 71
- Joined: Thu Aug 21, 2003 1:56 am
Can anyone tell me what's wrong with my code?
[c]
#include <stdio.h>
struct s
{ int serno;
char dna[51];
int inversion;
}a[100];
int n,m;
int getdna(char x)
{
switch(x)
{ case 'A': return 0;
case 'C': return 1;
case 'G': return 2;
case 'T': return 3;
default : abort();
}
}
int count_sort(char *str)
{ int i,j,k,invers=0,count[4]={0,0,0,0};
for(i=0; str; i++)
{
k=getdna(str);
count[k]++;
for(j=k+1; j<4; j++)
invers += count[j];
}
return invers;
}
int sort_function( const void *a, const void *b)
{
struct s *p=(struct s *)a, *q=(struct s *)b;
if(p->inversion > q->inversion) return 1;
else if(p->inversion < q->inversion) return -1;
else
{ if(p->serno > q->serno) return -1;
else return 1;
}
}
void main()
{
int testcase,t,i;
/*freopen("in612.txt","r",stdin);*/
scanf("%d",&testcase);
for(t=1; t<=testcase; t++)
{ if(t>1) printf("\n");
scanf("%d %d",&n,&m);
for(i=0; i<m; i++)
{
scanf("%s",&a.dna);
a.serno=i;
a.inversion=count_sort(a.dna);
}
qsort(a,m,sizeof(a[0]),sort_function);
for(i=0; i<m; i++) printf("%s\n",a.dna);
}
}
[/c]
[c]
#include <stdio.h>
struct s
{ int serno;
char dna[51];
int inversion;
}a[100];
int n,m;
int getdna(char x)
{
switch(x)
{ case 'A': return 0;
case 'C': return 1;
case 'G': return 2;
case 'T': return 3;
default : abort();
}
}
int count_sort(char *str)
{ int i,j,k,invers=0,count[4]={0,0,0,0};
for(i=0; str; i++)
{
k=getdna(str);
count[k]++;
for(j=k+1; j<4; j++)
invers += count[j];
}
return invers;
}
int sort_function( const void *a, const void *b)
{
struct s *p=(struct s *)a, *q=(struct s *)b;
if(p->inversion > q->inversion) return 1;
else if(p->inversion < q->inversion) return -1;
else
{ if(p->serno > q->serno) return -1;
else return 1;
}
}
void main()
{
int testcase,t,i;
/*freopen("in612.txt","r",stdin);*/
scanf("%d",&testcase);
for(t=1; t<=testcase; t++)
{ if(t>1) printf("\n");
scanf("%d %d",&n,&m);
for(i=0; i<m; i++)
{
scanf("%s",&a.dna);
a.serno=i;
a.inversion=count_sort(a.dna);
}
qsort(a,m,sizeof(a[0]),sort_function);
for(i=0; i<m; i++) printf("%s\n",a.dna);
}
}
[/c]
-
- Learning poster
- Posts: 94
- Joined: Wed Jul 31, 2002 12:44 pm
- Location: Dacca, Bangladesh
- Contact:
Actually, at first you were doing the reverse thing, that is list the strings in reversed order when they are equally ....If two or more strings are equally sorted, list them in the same order they are in the input file.
So in the previous code, the sort function would have been
[cpp]int sort_function( const void *a, const void *b)
{
Istiaque Ahmed [the LA-Z-BOy]
I'm also getting Wrong Answer in this problem. I'm reading some of your replies talking about "rejudgement". What is this?
Example of input:
Example of output:
Thanks in advance!
Example of input:
Code: Select all
10 8
AACATGAAGG
BBDBUFBBHH
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
CCECVGCCII
3 3
ACC
ACG
ACA
Code: Select all
CCCGGGGGGA
AACATGAAGG
BBDBUFBBHH
CCECVGCCII
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA
ACC
ACG
ACA
Hello, although my answer was not rejudgeg I still get WA too. Maybe my answer is really a "tank" but on my computer works correctly
[cpp]#include <stdio.h>
#include <stdlib.h>
char tab[100][51];
unsigned wartosc[100]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,};
int main()
{
int dlogosc;
int ilosc;
while(scanf("%d%d",&dlogosc,&ilosc)==2)
{
for(int i=0;i<ilosc;i++)
{
scanf("%s",&tab[0]);
for(int j=0;j<dlogosc-1;j++)
{
int k=1;
for(;k<dlogosc;k++)
{
if(tab[j+k]<tab[j])wartosc++;
}
}
}
for(int num=0;num<15000;num++)
{
for(int mum=0;mum<ilosc;mum++)if(wartosc[mum]==num)printf("%s\n",tab[mum]);
}
}
return 0;
}[/cpp]
Thanks for help
PS Like you sow - I am not really good programer :(
[cpp]#include <stdio.h>
#include <stdlib.h>
char tab[100][51];
unsigned wartosc[100]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,};
int main()
{
int dlogosc;
int ilosc;
while(scanf("%d%d",&dlogosc,&ilosc)==2)
{
for(int i=0;i<ilosc;i++)
{
scanf("%s",&tab[0]);
for(int j=0;j<dlogosc-1;j++)
{
int k=1;
for(;k<dlogosc;k++)
{
if(tab[j+k]<tab[j])wartosc++;
}
}
}
for(int num=0;num<15000;num++)
{
for(int mum=0;mum<ilosc;mum++)if(wartosc[mum]==num)printf("%s\n",tab[mum]);
}
}
return 0;
}[/cpp]
Thanks for help
PS Like you sow - I am not really good programer :(
612 - DNA Sorting - WA, why?
Hi. I'm getting WA for problem 612, but I don't know why. I tested my program against a reasonably large (and in my opinion complete) input/output combination, and my program gets everything right (newlines and so too).
I'd like to ask whether anybody minds giving me some sample input/output to test my program against, help is appreciated a lot, thanks!
I'd like to ask whether anybody minds giving me some sample input/output to test my program against, help is appreciated a lot, thanks!
That's my input:
and that's my output:
I hope it helps...
Joan
Code: Select all
3
10 13
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GGGGGGGGGG
GATCAGATTT
CCCGGGGGGA
TTTTTTTTTT
ATCGATGCAT
AAAAAAAAAA
CCCCCCCCCC
ACGTACGTAC
CGTACGTACG
TGCATGCATG
10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
10 13
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GGGGGGGGGG
GATCAGATTT
CCCGGGGGGA
TTTTTTTTTT
ATCGATGCAT
AAAAAAAAAA
CCCCCCCCCC
ACGTACGTAC
CGTACGTACG
TGCATGCATG
Code: Select all
GGGGGGGGGG
TTTTTTTTTT
AAAAAAAAAA
CCCCCCCCCC
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ACGTACGTAC
ATCGATGCAT
CGTACGTACG
TGCATGCATG
TTTTGGCCAA
TTTGGCCAAA
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA
GGGGGGGGGG
TTTTTTTTTT
AAAAAAAAAA
CCCCCCCCCC
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ACGTACGTAC
ATCGATGCAT
CGTACGTACG
TGCATGCATG
TTTTGGCCAA
TTTGGCCAAA
Joan