612 - DNA Sorting

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

gary
New poster
Posts: 5
Joined: Sat Jan 01, 2005 1:19 pm
Location: Taiwan

612 - DNA Sorting

Post by gary » Sat Jan 01, 2005 1:33 pm

I'm sure I have used "multiple input".

this is test input file
http://www.csie.nctu.edu.tw/~chchu/acm/ ... t/612i.txt
this is output file
http://www.csie.nctu.edu.tw/~chchu/acm/ ... t/612o.txt

I use 612i.txt to test this program, and the output and 612o.txt are same exactly.

The online judge give me "wrong answer"; I don't know where is wrong.

could someone give me help? thx!

Code: Select all

#include<iostream>
using namespace std;

short unsortedness(char *, short);

short unsortedness(char *s, short n)
{
	short level;
	short i, j;

	level=0;
	for (i=0; i<(n-1); i++)
		for (j=i+1; j<n; j++)
			if (s[i]>s[j])
				level++;
	return level;
}

main()
{
	short n, m, i, j, k;
	char **s;
	short **d;
	int a;

	cin >> a;

	while (a--) {
	cin >> n >> m;

	s = new char *[m];
	for (i=0; i<m; i++)
		s[i] = new char [n+1];

	d = new short *[m];
	for (i=0; i<m; i++)
		d[i] = new short [2];

	for (i=0; i<m; i++)
		cin >> s[i];

	for (i=0; i<m; i++) {
		d[i][0] = i;
		d[i][1] = unsortedness(s[i], n);
	}

	short t[1][2];
	short flag;
	for (i=0; i<(m-1); i++) {
		for (j=i+1, k=i, flag=0; j<m; j++)
			if (d[k][1] > d[j][1])
				k=j;
		if (k != i)
			for (j=0; j<2; j++) {
				t[0][j]=d[k][j];
				d[k][j]=d[i][j];
				d[i][j]=t[0][j];
			}
	}

	for (i=0; i<m; i++)
		cout << s[d[i][0]] << endl;

	for(i=0; i<m; i++)
		delete [] d[i];
	delete [] d;

	for(i=0; i<m; i++)
		delete [] s[i];
	delete [] s;
	cout << endl;
	}
	return 0;
}

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Sat Jan 01, 2005 3:15 pm

here is my output for the cases you have given here.


AGTC
GTTA
TTGC

AACCACAGTT
GAGGGAGGTG
AAGCATGTGG
ATCATTGGTT
GCAAACGTAT
GACTAGGGGC
ATTCGGGAGT
GGTCCCATGT
TATTGTGCGG
TTGATCGGAG

AAAAGGCGTG
AAAACGACAT
CCGGTGGCGA
GGTTAGGACT
TATGCTCTAG
TTGCTAAGAA

GAGAATGAACAGAGCACGCAGAAACTCATGGCTACTTTTTCTCCCTGGCT
AAATTCGCAGCTTAAAACGACAGATGCGATGATGTTTCATTGTTGTTGAC
AGAGTCAATACAACCAACACAGCCTACTAGAAAATACTAATCATGGTGTT
AAAGGTCCAACCAGATCGGCCTAGAGAAGATGATATTGATGCCGTCCCTT
GAAAGGCGCAGGCACGCGGGTTTGGCCGATTGTTTCGATTACCGGGATCT
ACGCCATCCCCGGACATCGTATCACTAATGATTGAAGTGTATGTATTTCG
AAACCCTACTAGCAGCCCACTGCCAACCGTTTTTACATCGGCATCTCGAC
ATCCCACGAGAAGAACACACCTGGGCACTTCTGGATTGCTACTGGTAGAA
ACAACACTTAAAGGGTTGAAGACGCGTCCCGCGGCTGGGCGTCACATAGT
CTCGCGCTATGGTCTGAATGTAGGGGGTCTTTGACTGGTGGCACTTTTTG
CCGAAACTACAAAAAGCTCCAGTCTCACAGTGTGGAGTTGCAGCAGACGC
TAAGAAGAGTGAAGGAACACTCCCCTCCGTGGTGATGTTCGCCGTAGACG
CGCAAGAGTTTGATTAGGGGCGCACTCCCTGGCTTCGTTCGTTTGTTACC
CTCTACGCGTCACCCAGCAGGCTTAGGTAATCTAATCGATGGTTTATGGT
ACGCGGAACTGACGACCCACATAAACTGGATGCGTAAAACTGCCCGGGTG
TGGCCCCAGGAGGATCATTGTAGACCTCTACTGTATCCTTTTGCTCGTCG
GGGACGAGCAAAAATACAAGGAGAACCGTAGCGAGATGGATGCTGATAAA
CACCACTGAGGAAAACCCGCTGCCCTGCGTCATGCTTAGTGATGAAACCG
CGTGACTAACAAGGCGAAATCCTCCTGCTCGCTCTTGGTTATTGGCAGCA
CACTATAGAGTGTGCGGTACTTGGCAGAGATTAATCATTAGGGCCTTTGT
GGAAGCTAGCTATAAGGGCCTAATTGGGTTTCCTCTACTTGGTCTTACCC
AGATATACAATACCGAGGCGCAGTGCACCCCCTCATCCCCCACGGAGAGT
TCACTTAAACAATATACGGCCGGGCTTTCTACACGTAGTATTAGTTGCCA
CAGGCATAGCTGTAACACCGTCGGACCGCGAGGGATGATCCTTATACTCG
TTGAACAAGGTGGTTAGGAATGCAGGACGACCTTGTAGTGAGAGGTTAGT
AGTACACGCATCACCAGCGACAGCCGGGGACGTAGAAATCAGTATACCCT
TAGCAAACGTCCTAGCCTTAATCCTGTAAGCTGTAGAATGTCTGCCAGCT
CAAGCCCTGTGACCTGACCTGTAACAAAACGCGGTTAAGGTATCCGTCTA
GTATTACTCTAAGCTAGCAAGAATTAAGCATATATTACGGATGTACTGGT
CATGAAGGGAGAAACTGAGGTCCCCGGGGTCATCGTCCCTCATGAACTAT
ATCGTCGGGTACCATGAACCGTGTTATCGTCGGGAGTTAGGATTCGCCTG
CCTGTATGCCGATGTCATGGCGTGTTAAAGCGTCATCTCTATTTCTAGGT
GCTTATTACAAAAAAATCCCTCACAAGTGAGCCGACCTGGTGGAGTACAC
GTATAGAAGGCTACGAATAGGATTCATAACATAAGATGACCCACGTGTGG
CCGTCCTGCTATCTGCAAGCGCGTGTTAGGATTGTATGGCGGATGGAGGG
AACATTGTGGCACTACGAAAGTACCTGGTTATACATCGGTCTTGGATCAA
TGCACCAGTATCCAGTTAATAGACCTGGAGCTAGTCTTAGATACTGATGC
ATGCATGTAAGTACCGCGTGTACCTGTAGCGGAATATGATGGGTTTCAGA
TATACCTCGGCGTACTTGCCTGCCGCGGGGCCGACTCCATTGGGGTCCCG
TTATAGAATACTGTTCGGTTAAACTTTGCATAATTACTAATCTGATTGCG
TATAGGGTGCTAGACAGGGTGAAAATATGCTGCGGAACTGGTTCTACCGT
GCACAGTTGCTGAACTGAACACCGAGATTCACTATTTGTCAGAAGCTACT
AATGGTGTCTCGGCTAGATATACCCGGTGTATATCGTACATGGGTGGGGC
CCATCGTCTACAGTACAAGAAGCGGTCGGGTATATAGGCCGGCACCCCCT
CTAGTGCAAGAACAGGCTCCTGCGATAGTCTACTTAGAAGGCGACCGGAT
GTCGCCAAAACCAGCAACGGCAATACCCGAGCTATACTACAGGAATAAAT
GGTATAGCTCGATCAGCAGAGGGCTGCATGTCAGGATACGCTGCAGTGGC
GACCGCAACGAGTGGTTTGTAAATAATTTCCCCGGTTGTAATGTCAGAAA
GTCCGGTGCCGTGTGGAATCGCCAGTGTTATCTAGGGGATTTTGGCAGGA
CGCGCCTGTGGAAAACCCAACCGAGTACTATATAGACGTCACCACCCGTC
ATCATGAGACGCTAGTACAACTGCCCCGAAAAACATTACTCTCCTTAACA
GGTCGGATCTTTGAAATTACATATCATGATCGGCAATATATGTCTACGTG
CGCTGGCTCGTCCAGATAATTGCCTTACGGTTACGGTAGAGCCTCTTAAT
GATCCTACTTGCCCAGTTCACACCCCTCGGGATGCACCCCCTGGAGCACG
TCTTCAAGCGGATGATGCGTGGCATCTTGAGCCGAGGACTGTTGCTCAAT
GGTGAAGGGGATGAGCGCCGACCAGAGGTCTGTGATGGCACCATGGAATC
CTGGATATTCTTCCGACAAAATGCTTGCATCCGATTTTGGCGGGTAGAAG
GGTGACCGATGTATGGGTCCTACAAAGGGAGAGCGGGTATTGGTCCCAAT
CGTCTACGTACTTCATACGGATCACAACCACGGATCAATTACGAGTTTAC
CGCGCTCATGATGTGCGTGGGCGATACAACCCTTACGCCGTCCCATGTTA
AACTTTAACGGGTTATGGTAACCGTTGCTACTAGTTGTATCGCAGCAAAT
ACGGCAGCGAACCTTGCTGGGCCGAACGAAGACCGTCCAACACTTACCAT
TTGTATAGGGGCTATTCAGTGGGAGATGGTTCGCAGAAATTTAGTTGATA
GTAACCTATTGTTCTACCGCGCTTGACCGGCACCAGGTGGGCCCGAGTGA
GCCACGTCTTTTGGCTTTGCGTAAGAACACTGGAGTTGCGCACTTGGGCC
TGAGACGGTGACCAAATCAAGATGCGTGGTTGCAAGCGACAAGCAGCATC
GAGATTCGAGGGCACACAACTTAAAGTGCTTTAGATCCCCAAACACCGGC
TACTACATAGTTACCACCACGTAAACGGTCCGCGCCACCAAATACCAGGA
ACGTCGGTCGATTGATTAGGGATAGTATGAGTCCGTTAGAGGTGAACAAT
CTAGATGCGACTGTCTGGTCATCAAGACGCGTATCCGAGCAAATTCGCTC
GGCTTGCGGACGTCGATCAACATAGGGAAAGTGTGGGAAAACGTTATGCA
TCGCGCTTATGGTCATAAACTATGTCCGAGTTTCACTAATTGCTACGACG
CGGTGAGCCTTAGGGGTGGCGGAAGTCACTTGGGCAGACTTAAGGGACAT
TGTGTGTTAAGTGCCACTACCCCTGCGGTATGGGAGCTCCTTACCGGGCG
ATTCCTCGAAGTTCGTGTGACACCATACCAGCACTCAATCACATTTGCGA
GCTGCTTTATAATCCTCTGTCATGAATGCAATGTCTGCGTATTTACGCAA
GTCGGTCAAGGCCGCATTGGTGTGTTACGACAAGTGCAGCGAGAGAAGTG
GCCTGTAAGGGTAATCTAGATGGCAACGCGATTCGCCGGTCAGCCCGACC
CTGGTGCCGAGACTCCAGCGGTAATAAAGTCTGTGCCTGTAAACACTATA
TTCCCCACATTTTAGGAATCTCGCCTGTCGTCGAGTGGCGCACAATTAAG
CGTTACGTCTGAGAAAAGGTAAACGTACTAAAGTATAGGCCACAACAATG
CATTCGGTATTTAGGGAGCGGGACCGTAATCCAAACGGAGGAGGGAAGGG
ATCGTGTGGCGGACGCGGCGCAACGCTTGCCGATATCTGTAACCCTGAGA
TTTAGCGAACATTTGTCTGGAGGATTGCCATCTGCCATGAAGTTCCGGAC
CTTTGTCGACGGGTAACTGCCTCGGTCCCAAGTTCCGGTTACCGCCGGAC
CCGTATTGAGGTCTAAAAATAGCGTGCTGTGTCCGCACTATGACCACCAC
TGTCATTTATAACGTCAGTTTCGTAAATAGTTAGACCAACTAGAGCCGTA
CTTTACGTAACTCTATTGCAAGACGAACAATGTTCAAATAAAACAAATGC
TACTATGGAGCAATTTTCTCCGCTTATCCTAAACTAAGGAAAACTTAGAA
TGCTGTTATATGTCAACGAGGAGGGCAGGACCGGCCCACAAATTGTATGA
TTTTATTCATTGGTTCAAACCAACTCTTACCACATCTGGAGCGACGCCGC
GTGTTATGTTTGCGCCGTATACCAATGATCGCCAAACTGAGCGTATCGTC
GGGCGTCGGGCCTGTAGTCGAGATGTGCATAGCGTAGAGAGACCGACCAT
GCTTTGCGTGAACGAGAAGAGGCCAGTACAATCTTACAGAGGCAACGCCA
TGGAGCCGATGTATCAGTATGTGGCACGAGCTATTTAACCATAAGCCAAC
CCAGTAATTTATATTTTGGGAGAAGGCCGGATTACGACCTACGACCAAAG
TTTCGGTGACCGCCTAGTGCGACAGTAGAATTTGACATTAAAGGCGGACA
GGCGTGGCCTCATTAAATCCGCCGGAATGAACGCTCTGTACAAAAAAATC
GGACTTTGGTGGGTCATTATCTGAACTACAATGACCAAAGTGACCGCACG
TCTTTCTTATTATCTCGTAGACATACGTTAAGCACCCAACAAGTCCATAA

ATTACGACGCAAACAAAATAGGGACTCCAAAATTCACCCTGGTGTTGTTC
AAGACCTCGTAAGCCCCCGCGCTACCACGAGGCCGGGCTCCTCTAGCGTT
CGACGCCCAATATAGAGAACGAGTGGCCAACCTCGCGTGTAGTTGGTAGT
ACTTTAGCCTAAAACCTGTCCACCTTCTCCGCGGCCGTGTGGTGTATGTG
AAGAGACGGGCTATAAGCCGGAGGCTCAGGGGGATACAGTTAGTTGTCTC
CGTACCCTTCAAGCAGTGATATCCCCGAGTTTCGTTTAGGCGTTTTGGCG
AATATCAACCACCACGAGACCCATCCGTTATACGAATCAAGCGTCTCCCC
CCGCCCGGAAAAATTAGCCTGAACAGCAAGGCTCTAGCTGGTGGGGTATA
CGGTTCTCAAAAAACCTCAATCTAGAGACATGTCCGTATTCTTCTATGCT
AACGCCCTATCCGGACCGCCAACACTGCTAGTCTCGAGCCCGGTCGCGAG
CAAACCCTATGGTAAAAAATGCAGATGTTCCCCCCGTGGTGACCCCGCCG
AATAGGTGTAAAAGTCAACATAAAAATGTCCTGAAAGTTCTTCTGACGCG
GCGAGGAGGAGCTTTACAAGCGTCCGTTTTGGAAGGGGCCGTGGGCGTCG
CCGTCAAACTCACTAGCGAAGCTCAGACGCGAGATACTAGTCGACTTGCT
AATCGAACTAGACAGGGCCAATCCAGGGTACAAACGACTTCGAGGGCATG
CAGCAGGAACGAACACGACTGAAGGAAACAAGAGTCAGCATTCTACATCC
GACTTCAGCACATAACAACTTGGCTCTAAGGGGACCCCTGCCGACGGGTT
AGTGATAACGCCATAAAAGAACTACGGTCTACCTACGACTGGCGCCTGCC
AAACAAAAAGCTTGACTTCCCCTCACTGAAAAAAGACGACACAATACGTG
GCCACTCTAGAGTAATGTATCAAAACTCTCTCGACTTGGTCGGAGGTAGT
CTACGATCAGAACCACAGTTCCTCATTGCTCGGCTACGCCACCGGGTGAG
CAATTGGATGCATAGCCACATCGTAACTCTGGTGGGAAGAGTACTGGCTT
TTAGCCGGGAATCAATACCTCTCTTCGAATTTTTGAAAGGATGCTGCTTG
TAAGAGGGTTGGCCTGTGTTCAGACGAAACTTCTCCGTTCGGTTTGGTCC
AAGATCGGAATCGAGACGTATGCAATATCCTCCCCAGAGGACAGGGGTAG
AGTAGGGACAACCAGTCGATTCATACTATTATCATTGGTTGAATAGGCAG
TCCTTCGACGGTAGATGTACCGAACTGATCATTCGGGAGTTATTGTGCGG
GAGACAACGCGAAGGCATTTCCAACCGGACCGCATTATAGAGGAAAGCTC
AACGGTCACACTGCAATCTCCCTTTAAACTACTCTCAACCCTATAATAGT
CGATCATGTACGTAACGCCCCTACAAAGCTGGCGCTTACGCTAATCCGGG
GTACCTGCTCTCAAATCAGTAACAGTATCCGTATAGGGTCATTATTAATG
GAACCGATCCAGGGGGGGGCAGCCAAAAAAGTAGAGAACCCCTTTGCCAT
CGCTTCAGCAAAGGATTCATTCACCCATTTTACATACTGTTGTCATATAA
GGGCGATATCCCGAGGAAAGGAGCGGGACTCACTCTTCAGGCTACCGCGG
ACATCATCGTTTACAACGGTCCCAGAATGCTGGTCTTCCGAACCCCCTAT
TGGACTAAACGGCGCAGCGCAGTCGTTAGAACTGCAGCAGGTAACGATTG
GCAGAACCATGCGGGTCCCTGCTGCCCCAAGGCGACTGGTCCATTGTAAA
CTCGACAGATGCTGCACGGACTGCGATTCGCGCGACTAATTGATCGTGAC
TCCATCATGAATTTCATTCATCAAGAAGCTCCAGCTACTGGTCCGGCGCG
TTAAGGCTACATTTCTCCATACTTCTTCCTTCGTCCCGACTAATTGGATG
CGACCACCTACGGACCATGTGCTTAGAGCAGGGGATTCAGCCAACCCGAT
TGAACGTATTAAAATGTCGCGCGGGCAATGGTAGTCAGCAGGAGGTCCCT
CCCCTAGCGGCGCTGCAATCCAGGCCCATCGATTCGATTGCAAGATAATT
TATATACGATGTAATACCACTTAGGGTTGCCCCAGCATTCGCAGCATGCT
CTAAATCGTCCTTGTATGAACTGTATCAGAATTATTACCTGTTCCGCACG
GCTGGGCCCATAGTGCTTCCGCGAACTGCCGTGCCATGCCGACCATGTGT
GAACCACACGTAGACGCTTACACTTTACATGTAGACTGCAACAGCCCGAA
GCTCCTGATAGCGCCAAGGTGCACATGCGGCCTAGAAAATCGCTTGTTAC
TTAAGGGCCTCGGCGGCATGGGCTCCAACGCACCCTTTACTGTCTCTACG
GGTCTTCTCGGGACTTCAGTCGATATCTCCCTTACTTGGCAATACTTTTC
TGGCGGGAGTCAGTCACCCCCCATCGGTCCGAAAGGGATCTACGAGGCTT
CAGAGAGTGGTCCACCGTCGCGTATAGTTAGAAAAGCGGTACCCCGGACT
CAACATCCGGTTCTAAGTGGACGCCTGGTATAATGAGTCACCATAATGAG
GCGCCTTTGAGGCTCCCTCGTACAGGCCAGGGACTCAGCTGTCATTCAGT
TCGTTGCGTGTAAAGGATTCCGGGACTGGCACGGACACTTTTATTGGTCC
GTAACGTGGCCCCGCGCGTCGTATATAGTATGTTGACCTTGAATGCCTAA
AAGCATGTGGATCGTACTTCGAAAAACGCATGCGTCCCATACTCTGCAGA
TGCTGCTACGGACACCCCGAGACTCCGACATCGAAACAAGGGTTGAATGG
CCTTCCCGTGAAAGCGGAACCCATGCGACACGCAGGGTACCCGGTTACAA
AGGCAAGCCGAAATGGAACTCAATCGTTTAGTTAATAGACACCAAATAAA
CTTGTGTCAAACTCATGAGGAATAAAAGAGCCCATAGGGGGGTCTACCAT
GGACGGCTACCCGTGTAGCTGAACCGGAACCGACTGACCAGTGCGAAGTC
GCAACTAGGGTCACAGAATCGTGTATCCGCCCGCCTACCTAAAACCGGCC
ATCTATGTAAAACTGGTATATGTTGACGTAATACGACCACCACTTTCGAC
CTACGCTGTATCTCATCTACCCTCCAGGGTGAGGCATAGGACATTAGATG
GAGACCTGTAGTCTATATGTAACCTCCTGCAACGAGAACTATGCGGAGCG
TTAGGGTGCTGGTGACTCATAGGTAGTAGATGTTAGCTATGTCCCCGCGT
AAGGCGTTAACCGCTGAAAGGTTCAGGTCAGCAAACGTATTCAGGAAGAA
AAGCCGGTGGGAAGAGTCTTGCGTGCATAAAAAGCCATATCGTGAAAACT
GCGGACCGTGATTTTGTGGTGCTTGTCTCCCTGTCTATCTCCGCCGTAAG
TTGTAGTGTCAAGTCATCCTAGGCCCAACACATTTACGGCATCGGGTGTA
TGTGGCGTATCCTTAAGATAACCGGGACGATGTTACAGACGCGCCTCTTC
TTCCGCCTTTAAAGCCGGTTCTACTCGGTTTTGAACGCACCCCCTGTCAG
CTTTTATTTGACTTTGTACTGCTCGCTTATACTTCGTACGTGTGCTAATC
TGGGATTCATGTCTCGCAATTCAAATGTTGAGCGCCCATGACCCAGTCTT
CCTGATTGATGCTTGGCTATTAGATAGACCCTGCCGACAAAGCAGTGTTG
GGGCAAGGATCAGTTCTGCCCACTGAGGCGCTCTACATAAGCAAATCAGT
GTCCCCAGGTGCAAACCTGGTAGGCGCAGGTACACGCCATATCCTCGAAA
ACAGGCGTGGTGTGCATTCAGTGGCCCACCCCGCTAGCTCAGTTCCTAAA
GTCGATAAGTTCAAGTATTGGGACAAAAAACGTGCACCAAAACAATACTT
CTAAAGGTCGGTATAGCGAGTGGCAATGAACCTCGTTAGAGCAGAAACGA
GTCTTCCCCAAATACATCATAAATGGAAACTTAAGACACGACTACAACCA
CCATGGTTCCACCCGTCTAGTGGACATGTCGAGGTACGAGAATCCCATAC
GGCATGGTTTCGGGGAAATTCGCACCGTATAGGCGCACATACCGATGATG
TCTACTGGTCCTAGTCGGACTGTTAATAGATCCGGGCAAACCACTTGGCG
AGCGCACCTTCACGCTAGGTTTCCCACGGTTGCACTAGAACGATACGAAA
GTATTGCGCGAGTGACGTTCTGGAGGCGAGCGCCCATGGACTGACTGAGC
AGTGTTGGGGTTAGAGGAGAACCATCAATTATCTCATTTCGGAGAAAGAG
TCTGCCTACTACGTTTCCGAAGAATCTGTGAGTTCCAACGTCTGAGCCAA
GCCTTGACGGACCCTAATCGCGAAGTTAGCGAGTTCGAGAGGGAACAAAC
TTTGGCCGGTCCATACAGACTTCAGCGACCGCAGTGTCACACTACTCCCC
TACCTTCGCCGTGTTTAGTTCGATAAGTTGTGGCACACTCGCAAATTACG
TGATGGTGGCTACCTATCACGTAATACTAGCTACTGTGACTTCACAAAGC
CGTGTGTCCGGGGTATGATTTTGCAAAAGCTATGGTAGACAGTGCACTAA
TACTTCTGGCGCTTTCGCCGCGACTTACCCTCCAAAGTTAACCTCAATCC
ACTTGTAGGAGGCGTTGACGCGTCGGCTCCCCGAAAAAGGAAACGTAATG
AAGCCTATCTTTGAGAGGGTTAGGTTAACCGCCAGGAGCCCCAACGAAAG
TTCCGTGACCTTCAACAAATGTTAGGGTCAACTCGCAAGCCCAGCAACAA
TGTTGAGTGGACATTTTGGTACGGGTGGTCGGACCGCTCACGCGCCCATA
GTGGGTTATTCGTGCTGAATCGATCCGGGATATGTCCGCACGTAAAATAA

AATAAACACGAAGATCAATGCGAAAGCGCCTCGGGGGTTTCTTTAGCATA
CCCAATCAACCCACATAAGCCTTAATAACTATAGTACCACGCTGTTCTTT
AACTAAGGACTAACTGAATCCCGGGCTCTTCTAGGATCGTGCTTTTCTTA
TAAATGTCTCTAAAAATCTAAGTGCATGTTCGTCTGTGAGTTTTTTAGAT
CAACACCCAATGCGAGAAATGGGCGGCTAACCCCGCGTGTAGCCAGTAGT
CAAAGCCCGTACCCCGCGATCTAAATATTGGATGCCTGTGGTTTAACCTC
CCCCTACGTAACACTCTTAGCACAACCACACTCGACTCTGCTTCAGGTCT
ACGCACAAGCAAGGCGCGAAGGCCCCGACTGGAATCCACTCCTTTACAGG
TTGAGGCATTGACGGTTCATGGGCAGCGGATGTCGGTTGTGCTTTCGTGT
CTTCACACTGACAAATTGAACTCCAGCGAGGGCCTGGTTGCTTCATCTGC
AACAACGGTTGTGCAGAAATTTAATCTTCAGCATCAAAGATATCGTTGTT
TAACGGGGGCAAATGCAGCCGAGGGAAGTGAGGATCGGTATTCTGTATCC
AGTATCACTAAGCACAACTCTTGAAGGCGACGGCGCGTGGTGAATCATGT
ATCCACGCGAAACCAGCGTACGCCGACGTGATGCAGTTACTACCCCTGAT
CACCGCCGCGGGCGCCCCAGGGCTCCGACGCTGGAATGGAAATCGAGTGG
AATATGATGACACAGACGTGATTCGACAGGATTTTGCTCTTGTAGGCTAA
ACTACTTCAAAATAGTATACCGGAACTCCTCCAACCTAGTCGAAGGTGGT
GTCCGCACTATTAACGCCAGTCGACCCCGTACTCGCGGGCGGCGGGATTC
AAACAGGGACTAGCTCCGCCTGCCGGAGCATCCTGCGCAGGTGAACCGAT
TTCAACAAACGCCGTATAGGCCGTAATTCGTACAACCAGCCAGTTGTGGC
TCTAGCCACAACGCCCATGTTCCGATTATTAGCTTTAATGATTTCAACTG
AGAGCTTCACGAACCTTTGTACTATCACAAGATTGAGCCTTTTTAATATC
GTTACAATGCAGGCGGGGTAGAGGCCTTAAAGTTTATTTCAATGCCATTT
ATCCACGAGAAGTGTCGACATGCCAACTCTCCGGGGAAGGAGATATAGTG
CTGGGCAGCTAGGCTTCAGACTCGAAAGAACCATTGATCCTCTCGTCTTT
ACTGCTAACTAGCGTAAGTGAGCAGAGGTACTGACTACTCATTGGTGGCC
ATAGCACAAAAATCAGAAGTGGGCCTGCCCACAATCACGACGAATAGTCA
CGATAAAGAACTCTTACTGTGAAAGCGATTGCCTACTCTTCCGGAGGCCC
GACCTCTCCAGGGTCTTGGTTAGTGTCCTTCCTGTTTGACGGTACCTCTC
GGTTGGAAGCCGGAATGACGAGCCCTACATGTCCGTTGTCTATGCTCTAG
GGATTAACTCAAGGGAAGATAACCAGAAAAGTGGGGGGTCTTCCCACCGC
CCGTCGTGTGCGGAAAATTCCGAGACTAGCATGGGTACCTTTGCTGGTCC
GGCGCGCAAGGTACGATAACTAAACCTAGTAACCGGATTACCTCGCGGCG
GGACAGGTCAGAGTGGGACCTAGTTATCCAATTAATGGGTGCTAAGTGGA
ACGACCGGAACCGTGAGGCTATGTACCCGCTTGCTTGCCTGGAACTAACC
ACCGATAAACTCGAGCGTCGAGACGGGAAGCATGTACTAGAATGACATCC
GACTCGGCATAGGCTAAGGTTCAGTCGAAGTGGACTGAAGTCACGTCTCT
GGTCCTGATATACAGTAGTTTAATCCCGGAAAGACTTTTGTTGATAAATT
GAGTATACAAGTCATGTCTTAAAAGGCGTGTGTGCTCCACGTCTTACGGA
GGTACACTCCTACGTCAGACCCTCTGCAGCTATGCCGGAATAACGTGGGG
AAGCGGCTACTCGTACGACTGAACCGAGGTCGATTGGCCGGCACAAGGCT
CCCATTAACTCCAATCGAGCCATCGACGAACCCGGACGAGCCACCTGATA
CGGCGGGGCTGTAGTGGTGATCCTGTGCCGCTATATCTCGGTGTCCCTAT
AACGGTCACGCTACGACCCCTTCTTGAATCATCCCTAGTCCCACGGCAAT
ACAGACATAATATGTGTTCGACGATTCATCTTGTCGACCCGACCTCTGAA
CACCCTCGGCGTTTCCATTACAGCCTATTTTCTAGAATTGACCTCGACCT
CGTGCTTCCCAGGCGACAGTGCTCCTGGATTCCGTTCGAGTACCCTGGTA
ATCAACTCATGTACGTCCTAATATTCTAAAGATTCTCAACTTAAAGTCAG
TGCATCAAGTGGCAGCGTAAAAGAGAAATGGGCTGAATAGGGATTGACCC
CACCTCTGCTGTACTCAACCCAACAAATCACGATATATCCGTAGATTATA
TAGCCAAGTATACAGTCATATTGCAGTTTCGGCAAGAAAAATACTGACTT
TTAAGAGTCCCGGTGGCGCAGGTCTTAGTGCGCCTTCCGTTACCTTTACA
GGGATAGGACTGGCTTTCGGAATCCTGCAGAGCTGATAGACCGTGGTCTC
GCGAGCAAGGAAAACCGGTGGGAAACTTTCTCGCCCGCCAACCAGGGAAC
CGGTTGCGCATATAATGCTTCTGCAGAATTAACGTCCATGCTGATTTGAG
TAATAGGGTCATGACCCTGCATAAACACAATAATTACGGATGTCGCGTAA
TACAGCGCGCTGGATAATGGGATGATATAACTCGTTACAGTTACATGAGA
GCTAAACCCACGGTATCTTCGTGAGCTATCGCGCCGCGTTGACCACACAT
CAGGGGAGACTAGGTCACCCCCGAGCCGAGACGGACAATACTCTCAACGG
TTCACATCGAGCCTATAGAAAGTGGAAAGATCTACAAAGGAATCTACTGC
GACGTCCTACTCAAATTACTGATGCTGTTAACCCTAGATTCGACTACGAG
AGTAATGATACTATGGGGAAGTTACGGTCTACCTGCGACCAGCACTTACT
ATTTTTTGGACCAGCAAGAGAGGGCCAATGGAGCTCAGTGTATTTAATGA
TCTTGTGACCCCTCATGCCCCATGGCGTGTTCAGATGGTTTCAGGAGACT
CATAGTACATCTCTGGAGTGATCAAAGTAACGCCGTAGACGCATCTCCCC
GACGTGACTTTAAAAAGGTTTATATTATATGGATATGCACATCAACAGTA
CGGTTGTTCGCAAGTTGCACATTCGAAGCAAGGGGCCCAGTCGATCTGGT
GGGCCTATTTTTAAAAAGATCGGGTCGATTGCCAGGAGCTCCGGCGGGAG
GGCATTAAAATTAGAGAGGAGTTGCTAGTCACTCCGCCTCGGAGAAAAGG
TCTGCTTATTATGCTCCTGAGGGGCCTATGGGTCCCAACATCTGGGTTGG
GATGTTAGCCGCCGCAGAATCTACTTATCGTATGGGCTAGATACCCCTCC
GACAGCTTTCAGTTTCCGAACGCAGAGATATGCAGTCCGATGGGGCATAA
AGCTTCCGCAAGGGGAACTCGGCTGGTCAATATATGCCATCACAGAAGCT
CTGGCCACTACTTTTGTATATTGATAACTTTAGCGATGCGTGCGCCACCT
CGACGTATTAGCGGCGCTTGATCCACTATGACCAGTAGGTGCAATCGCAG
AGCGCTATCGGAAATTCCGCCTTTTGGGAGAAACGCAGCCATCATCACGG
GCCTGTTACGGCCATGTGCTTATACACCGCACGCACAACCGTGAACGTTT
CGGTTATGTGCTCCATAATCTATAGCAGCTTGGGCCGATCGCCTGCGGCC
GCTATCGTGTTGTCATGCAGTATAAAGAAAATCTTAACTGAGATTCGCGG
TTCGTCTGTACAGCATGTAATCGTCACCTTAGGGACTAAGACGGTGGCGG
TTGTACTATACTTTGCCTGCCCTTCGAAATAAGGTGTGGGGTGCTAGATA
CCAGGCTACCTTTATGCAGGTTATGTTAAGGCTGTCATCCACCTCACGCA
TCATAACACTGAATTGTTTTGGGCCCGATATGCTCGTGGCGCCGAACATA
TGGCTTTCTGGGATCCCAAACGCTACTCCTCCCTGAGCGCTATTTACCCC
CCTGTCACGAATCTCATTTACTAAGAGGTTTCAGTTATCGACCCAGCACA
TGAGTATGTTGGGGCATTGCATAGACAGCAGCGGTCGGTGGGAAACCTCT
TTCGATCGACACTCAGCTGTTAAGTGAGTTTTGCCGATAAAACAGCGTCA
TGTTGTAGTTTGACTGGGTAGTCTATCGACTTTGGGCGAACTGCAGTTAT
TGGCCTGTAATGACATTACAAGAAGTGAGGACAGGCCCACCTTCAAATAG
ACGCTTGTCTTTAGGTTAGTGACGACACCCACGTGGGACTACTATCAGCG
GCTGGATCTTCGCAGGTGCGAGCCTCTCGATACGGATCCGAGAGGTACCC
TGGAGGATAACTTACCGTTGTACGCGACCAAAGGAACAACACCTCGAACT
TATTATGGCTTACCTTACGTCAGATGTATGCGGACGTTAATACACATCCC
TGTGGGCCTCGAGAATTATCATACATGCTCAGTTACCGTATCACGACCCA
TTTTTTTGTAGAGACGGAGCCCATACAACACATAAGATATTTAGTCACGG
TGTTCCAGTGGAGAATTTGTCCGTCCACCTCACATGCTACCGCTGCGCAA
TCCTTTGGTGGCGAGCGTACTGAATCGACCACTCAGAGATCGCTGTACGA
TTTCCATGATTGACCCGCTCTCCGACCTACCTACCGCAAGAAAACGCTTA
TCGGGAGTTAGTGCGGTGGGCGGCGACAAGTTTCGCCAAAATAGAGATAG
AGGGTTGAGGTTAGGACGTGCATAATACCCCCTTTGGGGAACAAAGACAA

C

ACATTT
CAGCTG
ACTTCC
CTGAGT
CGGATC
GGACAG
GGTCTA
TTGCTA
GGCAAA
TGGGCA

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

AAAAA
AAAAA
AAAAA
AACTG
AACTG
CTCGT
GTCCA
GTCCA

gary
New poster
Posts: 5
Joined: Sat Jan 01, 2005 1:19 pm
Location: Taiwan

Post by gary » Sat Jan 01, 2005 8:03 pm

Raiyan Kamal wrote:here is my output for the cases you have given here.
Both of them are same.

could anyone help me?
(I still don't know why I got WA, so strange!!)

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Sun Jan 02, 2005 6:23 am

Are you taking care of printing new lines well ? multiple input problems often cause WA for wrong handling or blank lines. For example, two or three blank lines might mean a 'case' separated by two blank lines. so the output should be what ever the problem specification says about 'blank' cases.

If you are using e-mail to send solutions, trying the online submission form might help you.

gary
New poster
Posts: 5
Joined: Sat Jan 01, 2005 1:19 pm
Location: Taiwan

Post by gary » Sun Jan 02, 2005 7:06 am

Raiyan Kamal wrote:Are you taking care of printing new lines well ? multiple input problems often cause WA for wrong handling or blank lines. For example, two or three blank lines might mean a 'case' separated by two blank lines. so the output should be what ever the problem specification says about 'blank' cases.

If you are using e-mail to send solutions, trying the online submission form might help you.
I use the online submission, and still get WA.
I am sure that each case is separated by a blank line, so the output should not display a blank case.
(Getting WA makes me anxiety.) : :x

Evan Tsang
New poster
Posts: 11
Joined: Sun Jan 02, 2005 9:14 am

Post by Evan Tsang » Sun Jan 02, 2005 9:19 am

Maybe it's because you print a blank line after the last solution.

gary
New poster
Posts: 5
Joined: Sat Jan 01, 2005 1:19 pm
Location: Taiwan

Post by gary » Sun Jan 02, 2005 11:10 am

Evan Tsang wrote:Maybe it's because you print a blank line after the last solution.
I try your suggestion, and still GOT WA. :(

Evan Tsang
New poster
Posts: 11
Joined: Sun Jan 02, 2005 9:14 am

Post by Evan Tsang » Mon Jan 03, 2005 1:37 am

Your sorting part is incorrect.

Try this case
2 3
TG
CA
AA

Answer should be
AA
TG
CA

gary
New poster
Posts: 5
Joined: Sat Jan 01, 2005 1:19 pm
Location: Taiwan

Post by gary » Wed Jan 05, 2005 4:26 pm

I rewrite my code, and get AC. :D
(Maybe my old code has a wrong sort function, so I use STL's sort.)

Code: Select all

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

class DNA {
	string content;
	int count;

public:

// private:
	int unsortedness() const;

	friend bool operator<(const DNA &, const DNA &);
	friend ostream &operator<<(ostream &, const DNA &);
	friend istream &operator>>(istream &, DNA &);
};

int DNA::unsortedness() const
{
	int ret=0;
	int i, j;

	for (i=0; i<(content.length()-1); i++)
		for (j=i+1; j<content.length(); j++)
			if (content[i] > content[j])
				ret++;
	return ret;
}

bool operator<(const DNA &l, const DNA &r)
{
	return (l.count < r.count);
}

ostream &operator<<(ostream &os, const DNA &r)
{
	return (os << r.content);
}

istream &operator>>(istream &is, DNA &r)
{
	is >> r.content;
	r.count = r.unsortedness();

	return is;
}

main()
{
	DNA dna;
	vector<DNA> vec_dna;
	int n, m;
	int a, i;

	cin >> a;
	while (a--) {
		cin >> n >> m;

		for (i=0; i<m; i++) {
			cin >> dna;
			vec_dna.push_back(dna);
		}

//		sort(vec_dna.begin(), vec_dna.end());
		stable_sort(vec_dna.begin(), vec_dna.end());

		for (i=0; i<m; i++)
			cout << vec_dna[i] << endl;

		if (a)
			cout << endl;

		vec_dna.clear();
	}

	return 0;
}

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

612-output limit exeed

Post by emotional blind » Wed Jan 12, 2005 7:29 am

i do not know why my program
gets
output limit exeed
here is my code

Code: Select all

#include<stdio.h>

int main(void)
{
	unsigned long int num, temp,total,d[100], sort[100];
	int n, m, i, j,k;
	char dna[100][50];
	scanf("%lu",&num);
	while(num--){
		scanf("%d%d",&n, &m);
			
		for(i=0;i<m;i++)
			scanf("%s",&dna[i]);

		for(i=0;i<m;i++){
			total=0;
			for(j=0;j<n;j++){
				for(k=j+1;k<n;k++){
					if(dna[i][j]>dna[i][k])
						total++;	
				}
			}
			d[i]=total;
		}
		for(i=0;i<m;i++)sort[i]=i;
		for(i=0;i<m;i++)
			for(j=i+1;j<m;j++){
				if(d[sort[i]]>d[sort[j]]){
					temp=sort[i];
					sort[i]=sort[j];
					sort[j]=temp;
				}
			}

		for(i=0;i<m;i++)
			printf("%s\n",dna[sort[i]]);
		if(num>1)
		printf("\n");
	}
	return 0;
}
thanks

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Thu Feb 10, 2005 12:44 am

as n<=50 && m<=100 you have to take char dna[100][51] not char dna[100][50], that will make your prog `Output Limit Exceed' free, but it seems you still have error in your algorithm.
If two or more strings are equally sorted, list them in the same order they are in the input file.
your sort here is not stable. consider this case

Code: Select all

1

3 3
GTA
CTA
ATG
output should be:

Code: Select all

ATG
GTA
CTA
where your prog fails to output this.
bye.
Istiaque Ahmed [the LA-Z-BOy]

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Fri Feb 11, 2005 6:58 am

thanks a lot
at last i got accepted in 612..
thanks again..

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

better algorithm than O(N^2) ?!

Post by Sedefcho » Mon Jun 27, 2005 5:00 pm

Gary,

Why don't you delete this code as it is Accepted.
Now ( by being available here ) it is simply a spoiler.

I was wondering
IF
there's a better way of calculating the count of
inversions in a given string STR having a length of N
THAN
the obvious straightforward algorithm which has
an O (N^2) time complexity.

Apparently you use that O (N^2) algorithm and I guess there's
no better algorithm in terms of runnng time.

Does anyone know a better algorithm or no such
algorithm exists ?

User avatar
tuman
New poster
Posts: 24
Joined: Sat Oct 22, 2005 7:30 pm
Location: CUET
Contact:

612 -(Be Careful)(Hints)

Post by tuman » Fri Oct 28, 2005 2:30 am

Listen every body problem 612 DNA sorting is being updated.I am a sufferer.So i dont want to see anybody suffering from this problem.



// Code deleted after AC :lol:


If u had downloaded the problem set of acm 6 months ago.Then u need to think about redownloading ,Because i m also a sufferer.I was getting wrong answerwithout any reason.Finally i hv noticed that this problem needs a test case.It means this problem is being updated.

1 :o <------test case

10 6

AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
We the dreamer of the dreamy dream...

mars kaseijin
New poster
Posts: 22
Joined: Mon Sep 19, 2005 4:58 am
Contact:

Post by mars kaseijin » Sat Dec 10, 2005 4:56 pm

Greetings,
Are you saying we should wait until this problem is updated?
If so, how long should we wait?

Post Reply

Return to “Volume 6 (600-699)”