612 - DNA Sorting
Moderator: Board moderators
Is there some special case I am ignoring with this one?
I've got a struct with the string, and a parameter for initial list position, which I use as a tie-breaker in my compare function.
Is there something wrong with my unsortedness counter? Seems to be exactly what the problem asks for...
d->sort = 0;
for(i=0;i<len;++i) for(j=i+1;j<len;++j)
if(d->str > d->str[j]) ++d->sort;
This looks fine to me... perhaps the problem gives invalid strings? or are the letters not only in upper case?
Bolster
I've got a struct with the string, and a parameter for initial list position, which I use as a tie-breaker in my compare function.
Is there something wrong with my unsortedness counter? Seems to be exactly what the problem asks for...
d->sort = 0;
for(i=0;i<len;++i) for(j=i+1;j<len;++j)
if(d->str > d->str[j]) ++d->sort;
This looks fine to me... perhaps the problem gives invalid strings? or are the letters not only in upper case?
Bolster
-
- New poster
- Posts: 5
- Joined: Sat Sep 28, 2002 3:46 pm
612-DNA SORTING WA
[pascal]
type tt=record
d:string;
pos:integer;
end;
var data:array[1..200] of tt;
d3:array[1..200]of INTEGER;
temp:tt;
var a,b,n,jb:integer;
function hitung(s:string):integer;
var a,b,c,d:integer;
se1,se2:set of char;
begin
se1:=[];
d:=0;
for a:=1 to N do begin
if not (upcase(s[a]) in se1)and
(upcase(s[a]) in ['G','C','A','T']) then
begin
se1:=se1+[upcase(s[a])];
se2:=[];
for b:=a+1 to N do begin
if (upcase(s)<upcase(s[a]))then
begin
inc(d);
end;
end;
end;
end;
hitung:=d;
end;
var min,z,jum,l:integer;
begin
readln(jum);
for l:=1 to jum do begin
readln(input);
readln(input,n,jb);
for a:=1 to jb do begin
readln(input,data[a].d);
data[a].pos:=a;
end;
for a:=1 to jb-1 do
for b:=a+1 to jb do begin
if hitung(data.d)>hitung(data[a].d) then
begin
temp:=data;
data:=data[a];
data[a]:=temp;
end;
end;
for a:=1 to jb-1 do
for b:=a+1 to jb do begin
if (hitung(data.d)=hitung(data[a].d))
and
(data.pos>data[a].pos) then begin
temp:=data;
data:=data[a];
data[a]:=temp;
end;
end;
for a:=JB DOWNto 1 do begin
writeln(data[a].d);
end;
writeln;
end;
end.[/pascal]
type tt=record
d:string;
pos:integer;
end;
var data:array[1..200] of tt;
d3:array[1..200]of INTEGER;
temp:tt;
var a,b,n,jb:integer;
function hitung(s:string):integer;
var a,b,c,d:integer;
se1,se2:set of char;
begin
se1:=[];
d:=0;
for a:=1 to N do begin
if not (upcase(s[a]) in se1)and
(upcase(s[a]) in ['G','C','A','T']) then
begin
se1:=se1+[upcase(s[a])];
se2:=[];
for b:=a+1 to N do begin
if (upcase(s)<upcase(s[a]))then
begin
inc(d);
end;
end;
end;
end;
hitung:=d;
end;
var min,z,jum,l:integer;
begin
readln(jum);
for l:=1 to jum do begin
readln(input);
readln(input,n,jb);
for a:=1 to jb do begin
readln(input,data[a].d);
data[a].pos:=a;
end;
for a:=1 to jb-1 do
for b:=a+1 to jb do begin
if hitung(data.d)>hitung(data[a].d) then
begin
temp:=data;
data:=data[a];
data[a]:=temp;
end;
end;
for a:=1 to jb-1 do
for b:=a+1 to jb do begin
if (hitung(data.d)=hitung(data[a].d))
and
(data.pos>data[a].pos) then begin
temp:=data;
data:=data[a];
data[a]:=temp;
end;
end;
for a:=JB DOWNto 1 do begin
writeln(data[a].d);
end;
writeln;
end;
end.[/pascal]
-
- Experienced poster
- Posts: 193
- Joined: Thu Sep 19, 2002 6:39 am
- Location: Indonesia
- Contact:
In your function "hitung", looks like you only check only the first occurences of A, C, G, T.
If I interpreted "hitung" correctly:
- hitung('ACA') returns 0 .......... eventhough there's 1-reversal (CA).
- hitung('ACG') returns 0 .......... 0-reversal.
I'm sure in order to find out the 'sorted-degree' you have to count all reversed condition.
I might be wrong since I'm not too sure with Pascal sets there ...
Try this input and see what it will return:
3 3
ACA
ACG
ACG
Regards,
-turuthok-
If I interpreted "hitung" correctly:
- hitung('ACA') returns 0 .......... eventhough there's 1-reversal (CA).
- hitung('ACG') returns 0 .......... 0-reversal.
I'm sure in order to find out the 'sorted-degree' you have to count all reversed condition.
I might be wrong since I'm not too sure with Pascal sets there ...
Try this input and see what it will return:
3 3
ACA
ACG
ACG
Regards,
-turuthok-
612 ???
[c]
#include <stdio.h>
typedef struct {
char string[51];
int nilai;
} liststring;
int main()
{
int i,n,m,count,j,key,k;
liststring data[101],temp;
scanf ("%d %d",&n,&m);
for (i=0;i<m;i++)
scanf ("%s",&(data.string));
/* Algoritma */
for (k = 0;k<m;k++) {
count = 0;
for (i = 0;i<n;i++) {
key = data[k].string;
for (j=i+1;j<=n-1;j++)
if (key > data[k].string[j]) count ++;
}
data[k].nilai = count;
}
for (i=0;i<m-1;i++) {
for (j=0;j<m-1;j++) {
if (data[j].nilai > data[j+1].nilai) {
temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
}
}
}
for (i=0;i<m;i++)
printf ("%s\n",data.string);
return 0;
}
Why my source wrong answer?I don't unsderstand[/c]
#include <stdio.h>
typedef struct {
char string[51];
int nilai;
} liststring;
int main()
{
int i,n,m,count,j,key,k;
liststring data[101],temp;
scanf ("%d %d",&n,&m);
for (i=0;i<m;i++)
scanf ("%s",&(data.string));
/* Algoritma */
for (k = 0;k<m;k++) {
count = 0;
for (i = 0;i<n;i++) {
key = data[k].string;
for (j=i+1;j<=n-1;j++)
if (key > data[k].string[j]) count ++;
}
data[k].nilai = count;
}
for (i=0;i<m-1;i++) {
for (j=0;j<m-1;j++) {
if (data[j].nilai > data[j+1].nilai) {
temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
}
}
}
for (i=0;i<m;i++)
printf ("%s\n",data.string);
return 0;
}
Why my source wrong answer?I don't unsderstand[/c]
612 - can anyone help me
i don't understand why my program is wrong
please give any comments ....
[pascal]
program p612 (input,output);
type
dnaset=array[1..50] of string;
dnacountset=array[1..50] of integer;
var
m,n,j,k:integer;
ch:string;
dnacount:dnacountset;
dna:dnaset;
procedure ssort(z:integer;dna:dnaset);
var
n,j,k : integer;
x,y,temp :string;
begin
dnacount[z]:=0;
for j:=m downto 1 do
for k:=1 to j-1 do begin
x:=copy(dna[z],k,1);
y:=copy(dna[z],k+1,1);
if x>y then begin
writeln(x,' is greater than ',y);
dnacount[z]:=dnacount[z]+1;
delete(dna[z],k,2);
insert(y+x,dna[z],k);
end;
end;
writeln(z,'=',dnacount[z]);
end;
procedure psort(dna:dnaset);
var
j,k,temp :integer;
dnacount2:dnacountset;
begin
for j:=1 to n do
dnacount2[j]:=j;
for k:=1 to n do
for j:=1 to n-1 do
if dnacount[j]>dnacount[j+1] then begin
temp:=dnacount[j];
dnacount[j]:=dnacount[j+1];
dnacount[j+1]:=temp;
temp:=dnacount2[j];
dnacount2[j]:=dnacount2[j+1];
dnacount2[j+1]:=temp;
end;
for j:=1 to n do
writeln(dna[dnacount2[j]]);
end;
begin
while not eof(input) do begin
read(m,n);
readln;
for j:=1 to n do begin
readln(ch);
dna[j]:=copy(ch,1,m);
ssort(j,dna);
end;
psort(dna);
end;
end.
[/pascal]
please give any comments ....
[pascal]
program p612 (input,output);
type
dnaset=array[1..50] of string;
dnacountset=array[1..50] of integer;
var
m,n,j,k:integer;
ch:string;
dnacount:dnacountset;
dna:dnaset;
procedure ssort(z:integer;dna:dnaset);
var
n,j,k : integer;
x,y,temp :string;
begin
dnacount[z]:=0;
for j:=m downto 1 do
for k:=1 to j-1 do begin
x:=copy(dna[z],k,1);
y:=copy(dna[z],k+1,1);
if x>y then begin
writeln(x,' is greater than ',y);
dnacount[z]:=dnacount[z]+1;
delete(dna[z],k,2);
insert(y+x,dna[z],k);
end;
end;
writeln(z,'=',dnacount[z]);
end;
procedure psort(dna:dnaset);
var
j,k,temp :integer;
dnacount2:dnacountset;
begin
for j:=1 to n do
dnacount2[j]:=j;
for k:=1 to n do
for j:=1 to n-1 do
if dnacount[j]>dnacount[j+1] then begin
temp:=dnacount[j];
dnacount[j]:=dnacount[j+1];
dnacount[j+1]:=temp;
temp:=dnacount2[j];
dnacount2[j]:=dnacount2[j+1];
dnacount2[j+1]:=temp;
end;
for j:=1 to n do
writeln(dna[dnacount2[j]]);
end;
begin
while not eof(input) do begin
read(m,n);
readln;
for j:=1 to n do begin
readln(ch);
dna[j]:=copy(ch,1,m);
ssort(j,dna);
end;
psort(dna);
end;
end.
[/pascal]
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
It's multi input...
Read all about it at http://acm.uva.es/problemset/minput.html.
Read all about it at http://acm.uva.es/problemset/minput.html.
anyone can catch my mistakes???
this is my code :
this is my code :
Code: Select all
#include <stdio.h>
#include <string.h>
char buffer[50][101];
int inv[50];
value(char a) {
if(a=='A') return 0;
if(a=='C') return 1;
if(a=='G') return 2;
if(a=='T') return 3;
return -1;
}
inversion(char *a) {
int i,j,count=0;
for(i=0;i<strlen(a)-1;i++)
for(j=i+1;a[j];j++) {
if(value(a[i]) > value(a[j])) count++;
}
return count;
}
void sort(int n) {
char buf[101];
int i,j;
for(i=0;i<n-1;i++)
for(j=0;j<n-1;j++) if(inv[j]>inv[j+1]) {
inv[j]^=inv[j+1]^=inv[j]^=inv[j+1];
strcpy(buf,buffer[j]);
strcpy(buffer[j],buffer[j+1]);
strcpy(buffer[j+1],buf);
}
}
main() {
int i,j,n,m,multiple;
scanf("%d",&multiple);
for(i=0;i<multiple;i++) {
scanf("%d %d\n",&m,&n);
for(j=0;j<n;j++) {
scanf("%s",buffer[j]);
inv[j] = inversion(buffer[j]);
}
sort(n);
if(i!=0) printf("\n");
for(j=0;j<n;j++) printf("%s\n",buffer[j]);
}
return 0;
}
peace...
612 WA help!!
Hi, i just wrote this code for the 612 DNA sorting problem, no matter what imput i select to test my program it ALWAYS gives me the CORRECT answer but when i submit the program the judge says WA.
[cpp]
#include <fstream.h>
#include <string.h>
#include <stdlib.h>
struct Cadenas
{
int peso;
int orden;
char *palabra;
};
int main(void)
{
//ifstream cin;
//cin.open("texto.txt");
int longitud;
int verdad=0;
int numStrings;
int auxPeso;
int pruebas;
cin>>pruebas;
while (pruebas){
verdad=0;
cin>>longitud;
cin>>numStrings;
Cadenas *ArrCadenas = new Cadenas[numStrings];
char *auxString = new char[longitud+1];
for(int t=0; t<numStrings; t++){
ArrCadenas[t].palabra = new char[longitud+1];
cin.ignore();
cin.getline( ArrCadenas[t].palabra, longitud+1);
ArrCadenas[t].peso = 0;
ArrCadenas[t].orden = t;
}
for(int k=0; k<numStrings; k++)
for(int m=0; m<longitud-1; m++)
for(int j=m+1; j<longitud; j++)
if(ArrCadenas[k].palabra[m] > ArrCadenas[k].palabra[j])
ArrCadenas[k].peso += 1;
for(int q=0; q<numStrings-1; q++)
for(int j=q+1; j<numStrings; j++)
if(ArrCadenas[q].peso > ArrCadenas[j].peso){
strcpy(auxString,ArrCadenas[q].palabra);
strcpy(ArrCadenas[q].palabra,ArrCadenas[j].palabra);
strcpy(ArrCadenas[j].palabra,auxString);
auxPeso = ArrCadenas[q].peso;
ArrCadenas[q].peso = ArrCadenas[j].peso;
ArrCadenas[j].peso = auxPeso;
auxPeso = ArrCadenas[q].orden;
ArrCadenas[q].orden = ArrCadenas[j].orden;
ArrCadenas[j].orden = auxPeso;
}
do
{
verdad = 0;
for(int f=0; f<numStrings-1; f++)
if( ArrCadenas[f].peso == ArrCadenas[f+1].peso)
if(ArrCadenas[f].orden > ArrCadenas[f+1].orden){
strcpy(auxString,ArrCadenas[f].palabra);
strcpy(ArrCadenas[f].palabra,ArrCadenas[f+1].palabra);
strcpy(ArrCadenas[f+1].palabra,auxString);
auxPeso = ArrCadenas[f].orden;
ArrCadenas[f].orden = ArrCadenas[f+1].orden;
ArrCadenas[f+1].orden = auxPeso;
verdad=1;
}
}
while(verdad==1);
for( int w=0; w<numStrings; w++)
cout<<ArrCadenas[w].palabra<<endl;
cout<<endl;
pruebas--;
}
return 0;
}
[/cpp]
Can someone tellme whats wrong? im considering multiple inputs and all that stuff but nothing
I also know that this solution is wide too big but Im to lazzy to write this again, maybe Im not considering some critical inputs but i have tryed a lot.
I even compared the results of my program with the results of this correct code. Both are giving the same answer but mine is getting WA...
[cpp]
#include <iostream.h>
#include <string.h> using namespace std;
#include <fstream.h>
int main(){
int cases,i;
cin>>cases;
for (i=1;i<=cases;i++){
char dat[102][52]={0};
int col,row;
int c,r,a;
int inver[102] = {0};
cin>>col>>row;
for (r=1;r<=row;r++){
cin>>dat[r];
for (c=0;c<col-1;c++)
for (a=c+1;a<col;a++)
if (dat[r][a]<dat[r][c]) inver[r]++;
}
int max=0;
for (r=1;r<=row;r++)
if (inver[r]>max) max = inver[r];
for (a=0;a<=max;a++)
for (r=1;r<=row;r++)
if (inver[r]==a){
for (c=0;c<col;c++)
cout<<dat[r][c];
cout<<endl;
}
cout<<endl; //new line
}
return 0; //end program
}
[/cpp]
[cpp]
#include <fstream.h>
#include <string.h>
#include <stdlib.h>
struct Cadenas
{
int peso;
int orden;
char *palabra;
};
int main(void)
{
//ifstream cin;
//cin.open("texto.txt");
int longitud;
int verdad=0;
int numStrings;
int auxPeso;
int pruebas;
cin>>pruebas;
while (pruebas){
verdad=0;
cin>>longitud;
cin>>numStrings;
Cadenas *ArrCadenas = new Cadenas[numStrings];
char *auxString = new char[longitud+1];
for(int t=0; t<numStrings; t++){
ArrCadenas[t].palabra = new char[longitud+1];
cin.ignore();
cin.getline( ArrCadenas[t].palabra, longitud+1);
ArrCadenas[t].peso = 0;
ArrCadenas[t].orden = t;
}
for(int k=0; k<numStrings; k++)
for(int m=0; m<longitud-1; m++)
for(int j=m+1; j<longitud; j++)
if(ArrCadenas[k].palabra[m] > ArrCadenas[k].palabra[j])
ArrCadenas[k].peso += 1;
for(int q=0; q<numStrings-1; q++)
for(int j=q+1; j<numStrings; j++)
if(ArrCadenas[q].peso > ArrCadenas[j].peso){
strcpy(auxString,ArrCadenas[q].palabra);
strcpy(ArrCadenas[q].palabra,ArrCadenas[j].palabra);
strcpy(ArrCadenas[j].palabra,auxString);
auxPeso = ArrCadenas[q].peso;
ArrCadenas[q].peso = ArrCadenas[j].peso;
ArrCadenas[j].peso = auxPeso;
auxPeso = ArrCadenas[q].orden;
ArrCadenas[q].orden = ArrCadenas[j].orden;
ArrCadenas[j].orden = auxPeso;
}
do
{
verdad = 0;
for(int f=0; f<numStrings-1; f++)
if( ArrCadenas[f].peso == ArrCadenas[f+1].peso)
if(ArrCadenas[f].orden > ArrCadenas[f+1].orden){
strcpy(auxString,ArrCadenas[f].palabra);
strcpy(ArrCadenas[f].palabra,ArrCadenas[f+1].palabra);
strcpy(ArrCadenas[f+1].palabra,auxString);
auxPeso = ArrCadenas[f].orden;
ArrCadenas[f].orden = ArrCadenas[f+1].orden;
ArrCadenas[f+1].orden = auxPeso;
verdad=1;
}
}
while(verdad==1);
for( int w=0; w<numStrings; w++)
cout<<ArrCadenas[w].palabra<<endl;
cout<<endl;
pruebas--;
}
return 0;
}
[/cpp]
Can someone tellme whats wrong? im considering multiple inputs and all that stuff but nothing
![:cry:](./images/smilies/icon_cry.gif)
I even compared the results of my program with the results of this correct code. Both are giving the same answer but mine is getting WA...
[cpp]
#include <iostream.h>
#include <string.h> using namespace std;
#include <fstream.h>
int main(){
int cases,i;
cin>>cases;
for (i=1;i<=cases;i++){
char dat[102][52]={0};
int col,row;
int c,r,a;
int inver[102] = {0};
cin>>col>>row;
for (r=1;r<=row;r++){
cin>>dat[r];
for (c=0;c<col-1;c++)
for (a=c+1;a<col;a++)
if (dat[r][a]<dat[r][c]) inver[r]++;
}
int max=0;
for (r=1;r<=row;r++)
if (inver[r]>max) max = inver[r];
for (a=0;a<=max;a++)
for (r=1;r<=row;r++)
if (inver[r]==a){
for (c=0;c<col;c++)
cout<<dat[r][c];
cout<<endl;
}
cout<<endl; //new line
}
return 0; //end program
}
[/cpp]
-
- New poster
- Posts: 2
- Joined: Sun Nov 02, 2003 4:10 am
- Location: ES - Brasil
- Contact:
612 - WA ?
I'm getting WA for my program. Does anyone have some thinking about this???
[pascal]
Program t612;
var
m, n : Integer;
i, j, q, p : integer;
Maior : Integer;
DNA : array [0..50, 0..100] of Char;
count : array [0..100] of Integer;
order : array [0..100] of Integer;
Begin
while not eof do
begin
readln(m,n);
//input
For i:=0 to m do
For j:=0 to n do
read(DNA[j]);
For i:= 0 to n do
count := 0;
end;
//counter
For i:=0 to m do
For j:=0 to n-1 do
For q:=j+1 to n do
if DNA[q] > DNA[j] then
count := count;
//order
Maior:= count[0];
For i:= 0 to m do begin
For j:= 1 to m do
if count[j] > Maior then begin
Maior := count[j];
order := j;
end;
count[order] := -1;
end;
//printer
For i:= 0 to m do begin //indice do order = linha
For j:=0 to n do
write(DNA[order][j]);
writeln( );
end;
End.
[/pascal]
![:roll:](./images/smilies/icon_rolleyes.gif)
[pascal]
Program t612;
var
m, n : Integer;
i, j, q, p : integer;
Maior : Integer;
DNA : array [0..50, 0..100] of Char;
count : array [0..100] of Integer;
order : array [0..100] of Integer;
Begin
while not eof do
begin
readln(m,n);
//input
For i:=0 to m do
For j:=0 to n do
read(DNA[j]);
For i:= 0 to n do
count := 0;
end;
//counter
For i:=0 to m do
For j:=0 to n-1 do
For q:=j+1 to n do
if DNA[q] > DNA[j] then
count := count;
//order
Maior:= count[0];
For i:= 0 to m do begin
For j:= 1 to m do
if count[j] > Maior then begin
Maior := count[j];
order := j;
end;
count[order] := -1;
end;
//printer
For i:= 0 to m do begin //indice do order = linha
For j:=0 to n do
write(DNA[order][j]);
writeln( );
end;
End.
[/pascal]
-
- Experienced poster
- Posts: 146
- Joined: Sat Apr 26, 2003 2:51 am
-
- Guru
- Posts: 647
- Joined: Wed Jun 26, 2002 10:12 pm
- Location: Hong Kong and New York City
- Contact:
612 - DNA Sorting - WA After rejudgement
What's new in the data set that's crucial? Can someone give me test cases? Thanks.
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
I want what's change after rejudgement too....
I don't see any trap in this problem but got WA (or TLE - I don't get report) after rejudgement ...
Best regards
DM
I don't see any trap in this problem but got WA (or TLE - I don't get report) after rejudgement ...
Best regards
DM
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)
The data has changed.
http://online-judge.uva.es/board/viewtopic.php?t=4932
http://online-judge.uva.es/board/viewtopic.php?t=4932
AC makes me feels good,
But WA makes me thinks hard.
But WA makes me thinks hard.