10226 - Hardwood Species
Moderator: Board moderators
10226 - Hardwood Species
It's unbelievable that I got TLE in this problem. I think I handle the multiinput data well and use qsort to reduce the running time.Could someone find out the bugs?
[c]
#include<stdio.h>
#include<string.h>
struct treedata
{
long n;
char *name;
};
int comp(const void *,const void *);
void main(void)
{
int x,count,n,y,max;
long total;
double t;
char s[31];
struct treedata tree[10000];
max=0;
for(x=0;x<10000;x++)
tree[x].name=NULL;
scanf("%d\n",&count);
for(x=0;x<count;x++)
{
if(x)
printf("\n");
n=total=0;
while(gets(s)!=NULL)
{
if(!strlen(s))
break;
total++;
for(y=0;y<n;y++)
if(strcmp(s,tree[y].name)==0)
{
tree[y].n++;
break;
}
if(y==n)
{
if(!tree[n].name)
tree[n].name=(char *)malloc(sizeof(char)*31);
strcpy(tree[n].name,s);
tree[n].n=1;
n++;
}
}
qsort(tree,n,sizeof(struct treedata),comp);
for(y=0;y<n;y++)
{
t=tree[y].n;
printf("%s %.4lf\n",tree[y].name,t/(double)total*100);
}
if(n>max)
max=n;
}
for(x=0;x<max;x++)
free(tree[x].name);
}
int comp(const void *a,const void *b)
{
return strcmp(((const struct treedata *)a)->name,((const struct treedata *)b)->name);
}
[/c]
[c]
#include<stdio.h>
#include<string.h>
struct treedata
{
long n;
char *name;
};
int comp(const void *,const void *);
void main(void)
{
int x,count,n,y,max;
long total;
double t;
char s[31];
struct treedata tree[10000];
max=0;
for(x=0;x<10000;x++)
tree[x].name=NULL;
scanf("%d\n",&count);
for(x=0;x<count;x++)
{
if(x)
printf("\n");
n=total=0;
while(gets(s)!=NULL)
{
if(!strlen(s))
break;
total++;
for(y=0;y<n;y++)
if(strcmp(s,tree[y].name)==0)
{
tree[y].n++;
break;
}
if(y==n)
{
if(!tree[n].name)
tree[n].name=(char *)malloc(sizeof(char)*31);
strcpy(tree[n].name,s);
tree[n].n=1;
n++;
}
}
qsort(tree,n,sizeof(struct treedata),comp);
for(y=0;y<n;y++)
{
t=tree[y].n;
printf("%s %.4lf\n",tree[y].name,t/(double)total*100);
}
if(n>max)
max=n;
}
for(x=0;x<max;x++)
free(tree[x].name);
}
int comp(const void *a,const void *b)
{
return strcmp(((const struct treedata *)a)->name,((const struct treedata *)b)->name);
}
[/c]
-
- New poster
- Posts: 17
- Joined: Fri May 31, 2002 6:30 pm
- Contact:
10226 use stl but get TLE
10226 use stl but get TLE
who can help? maybe 30s i can accept the problem but now is 10s only...
[cpp]
#include <iostream>
#include <string>
#include <map>
#include <iomanip>
using namespace std;
typedef map< string, int > treeType;
treeType treeList;
int main(){
string elem;
double count;
int caseNum, l;
char buf[500];
cin >> caseNum;
cin.getline(buf, sizeof(buf));
for( l = 0; l < caseNum; l++ ){
count = 0;
while( cin.getline(buf, sizeof(buf)) ){
if( int(buf[0]) == 0 )
break;
elem = buf;
count++;
treeList[elem]++;
}
treeType::iterator l = treeList.begin();
while( l != treeList.end() ){
cout.setf(ios::fixed);
cout.precision(4);
cout << (*l).first << " " << double((*l).second)/count*100.0 << endl;
l++;
}
}
return 0;
}
[/cpp]
who can help? maybe 30s i can accept the problem but now is 10s only...
![:cry:](./images/smilies/icon_cry.gif)
[cpp]
#include <iostream>
#include <string>
#include <map>
#include <iomanip>
using namespace std;
typedef map< string, int > treeType;
treeType treeList;
int main(){
string elem;
double count;
int caseNum, l;
char buf[500];
cin >> caseNum;
cin.getline(buf, sizeof(buf));
for( l = 0; l < caseNum; l++ ){
count = 0;
while( cin.getline(buf, sizeof(buf)) ){
if( int(buf[0]) == 0 )
break;
elem = buf;
count++;
treeList[elem]++;
}
treeType::iterator l = treeList.begin();
while( l != treeList.end() ){
cout.setf(ios::fixed);
cout.precision(4);
cout << (*l).first << " " << double((*l).second)/count*100.0 << endl;
l++;
}
}
return 0;
}
[/cpp]
10226 Hardwood species: can anybody help me
I can't understand why i got runtime error all the time . I think this is a multiple input problem and my array size ok. will anybody kindly see my code and tell me where i am wrong.thanks in advance.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
main()
{
char a[1000],b[10000][30],c[10000][30],temp[1000],f[10000][30];
long long int i,j,k,l,n,p,m,cnt,y,count,x;
float d[10000],z;
gets(a);
n=atoi(a);
gets(a);
for(x=0;x<n;x++)
{
j=p=0;
while(1)
{
if(gets(b[j])==NULL) {p=1;break;}
if(!strcmp(b[j],"")) break;
j++;
}
if(p) break;
count++;
for(i=0;i<j;i++)
for(k=i+1;k<j;k++)
{
if((strcmp(b[i],b[k]))>0)
{
strcpy(temp,b[i]);
strcpy(b[i],b[k]);
strcpy(b[k],temp);
}
}
m=cnt=y=0;k=0;
for(i=0;i<j;i++)
{
for(k=i;k<j;k++)
{
if(strcmp(b[i],b[k])==0) cnt++;
else break;
}
d[m++]=((float)cnt/j)*100.0000;
strcpy(f[y++],b[i]);
i=k-1;
cnt=0;
}
for(i=0;i<m;i++)
{
printf("%s %.4f\n",f[i],d[i]);
}
if(count!=(n-1)) printf("\n");
}
return 0;
}
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
main()
{
char a[1000],b[10000][30],c[10000][30],temp[1000],f[10000][30];
long long int i,j,k,l,n,p,m,cnt,y,count,x;
float d[10000],z;
gets(a);
n=atoi(a);
gets(a);
for(x=0;x<n;x++)
{
j=p=0;
while(1)
{
if(gets(b[j])==NULL) {p=1;break;}
if(!strcmp(b[j],"")) break;
j++;
}
if(p) break;
count++;
for(i=0;i<j;i++)
for(k=i+1;k<j;k++)
{
if((strcmp(b[i],b[k]))>0)
{
strcpy(temp,b[i]);
strcpy(b[i],b[k]);
strcpy(b[k],temp);
}
}
m=cnt=y=0;k=0;
for(i=0;i<j;i++)
{
for(k=i;k<j;k++)
{
if(strcmp(b[i],b[k])==0) cnt++;
else break;
}
d[m++]=((float)cnt/j)*100.0000;
strcpy(f[y++],b[i]);
i=k-1;
cnt=0;
}
for(i=0;i<m;i++)
{
printf("%s %.4f\n",f[i],d[i]);
}
if(count!=(n-1)) printf("\n");
}
return 0;
}
10226 Hardwood species: can anybody help me
I can't understand why i got runtime error all the time . I think this is a multiple input problem and my array size ok. will anybody kindly see my code and tell me where i am wrong.thanks in advance.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
main()
{
char a[1000],b[10000][30],c[10000][30],temp[1000],f[10000][30];
long long int i,j,k,l,n,p,m,cnt,y,count,x;
float d[10000],z;
gets(a);
n=atoi(a);
gets(a);
for(x=0;x<n;x++)
{
j=p=0;
while(1)
{
if(gets(b[j])==NULL) {p=1;break;}
if(!strcmp(b[j],"")) break;
j++;
}
if(p) break;
count++;
for(i=0;i<j;i++)
for(k=i+1;k<j;k++)
{
if((strcmp(b[i],b[k]))>0)
{
strcpy(temp,b[i]);
strcpy(b[i],b[k]);
strcpy(b[k],temp);
}
}
m=cnt=y=0;k=0;
for(i=0;i<j;i++)
{
for(k=i;k<j;k++)
{
if(strcmp(b[i],b[k])==0) cnt++;
else break;
}
d[m++]=((float)cnt/j)*100.0000;
strcpy(f[y++],b[i]);
i=k-1;
cnt=0;
}
for(i=0;i<m;i++)
{
printf("%s %.4f\n",f[i],d[i]);
}
if(count!=(n-1)) printf("\n");
}
return 0;
}
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
main()
{
char a[1000],b[10000][30],c[10000][30],temp[1000],f[10000][30];
long long int i,j,k,l,n,p,m,cnt,y,count,x;
float d[10000],z;
gets(a);
n=atoi(a);
gets(a);
for(x=0;x<n;x++)
{
j=p=0;
while(1)
{
if(gets(b[j])==NULL) {p=1;break;}
if(!strcmp(b[j],"")) break;
j++;
}
if(p) break;
count++;
for(i=0;i<j;i++)
for(k=i+1;k<j;k++)
{
if((strcmp(b[i],b[k]))>0)
{
strcpy(temp,b[i]);
strcpy(b[i],b[k]);
strcpy(b[k],temp);
}
}
m=cnt=y=0;k=0;
for(i=0;i<j;i++)
{
for(k=i;k<j;k++)
{
if(strcmp(b[i],b[k])==0) cnt++;
else break;
}
d[m++]=((float)cnt/j)*100.0000;
strcpy(f[y++],b[i]);
i=k-1;
cnt=0;
}
for(i=0;i<m;i++)
{
printf("%s %.4f\n",f[i],d[i]);
}
if(count!=(n-1)) printf("\n");
}
return 0;
}
-
- Experienced poster
- Posts: 128
- Joined: Fri Nov 15, 2002 7:45 am
- Location: Kyrgyzstan
I guess you misunderstood the problem. You think that there can be only 10000 lines in input, but according to the problem statement there can be up to 1000000 lines for one test. Therefore you can't keep all the input in one array (you used b[10000][30]). You should use a structure like sorted list that is updated for each new line of input. Well... perhaps there are better algorithms, but I did it this way. And another little bug in your program - name of a tree can be up to 30 characters - it's not enough to use arrays like b[...][30]. You should use b[...][31].
Try it and get AC.
Buy.
![:wink:](./images/smilies/icon_wink.gif)
Try it and get AC.
Buy.
-
- Experienced poster
- Posts: 128
- Joined: Fri Nov 15, 2002 7:45 am
- Location: Kyrgyzstan
Well, I'll try to explain the way I did it.
I used sorted list of structures { char *s; int count;}, that was sorted by s.
First let the list be empty.
Then for each line S of input you should:
1. Find out if S is in the list. As our list is sorted we can do it using binary search.
2. If S is in the list we increase count of the item.
3. If S is not in the list we insert new item so that the list remain sorted and set its count to be 1.
After reading in all the lines we have sorted list of trees and the number of appearances of each one.
Now it's easy to do the rest.
I tried to explain carefully, but my English is not well so ask me whatever you don't understand.
Good luck.
I used sorted list of structures { char *s; int count;}, that was sorted by s.
First let the list be empty.
Then for each line S of input you should:
1. Find out if S is in the list. As our list is sorted we can do it using binary search.
2. If S is in the list we increase count of the item.
3. If S is not in the list we insert new item so that the list remain sorted and set its count to be 1.
After reading in all the lines we have sorted list of trees and the number of appearances of each one.
Now it's easy to do the rest.
I tried to explain carefully, but my English is not well so ask me whatever you don't understand.
Good luck.
Same is the case with me
I also used STL for solving this problem. But getting a TLE. Is anything wrong with the input or our algo?
Can anybody help....
Can anybody help....
But it doesnt have anything to do with TLE
hi gvcormac:
But that doesnt have anything to do with TLE. if he is not "emptying" the map table then I think it should give a WA but not a TLE. I have actually modified the posted code into this:
[cpp]
#pragma warning(disable : 4786)
#include <iostream>
#include <string>
#include <map>
#include <iomanip>
#include <fstream>
using namespace std;
typedef map< string, int > treeType;
treeType treeList;
int main(){
string elem;
double count;
int caseNum, l;
cin >> caseNum;
getline(cin,elem);
getline(cin,elem);
for( l = 0; l < caseNum; l++ ){
count = 0;
treeList.clear();
while( getline(cin,elem) ){
if(elem=="")
break;
count++;
treeList[elem]++;
}
treeType::iterator l = treeList.begin();
while( l != treeList.end() ){
cout.setf(ios::fixed);
cout.precision(4);
cout << (*l).first << " " <<(double((*l).second)/count)*100.0 << endl;
l++;
}
}
return 0;
}
[/cpp]
But it still gives a TLE. There must be someother way to do this.
But that doesnt have anything to do with TLE. if he is not "emptying" the map table then I think it should give a WA but not a TLE. I have actually modified the posted code into this:
[cpp]
#pragma warning(disable : 4786)
#include <iostream>
#include <string>
#include <map>
#include <iomanip>
#include <fstream>
using namespace std;
typedef map< string, int > treeType;
treeType treeList;
int main(){
string elem;
double count;
int caseNum, l;
cin >> caseNum;
getline(cin,elem);
getline(cin,elem);
for( l = 0; l < caseNum; l++ ){
count = 0;
treeList.clear();
while( getline(cin,elem) ){
if(elem=="")
break;
count++;
treeList[elem]++;
}
treeType::iterator l = treeList.begin();
while( l != treeList.end() ){
cout.setf(ios::fixed);
cout.precision(4);
cout << (*l).first << " " <<(double((*l).second)/count)*100.0 << endl;
l++;
}
}
return 0;
}
[/cpp]
But it still gives a TLE. There must be someother way to do this.
10226 compile error from <algorithm> sort
Anyone knows what the compile error means when you try to compile this following program of mine for 10226? It has to do with calling the function sort from <algorithm>. I get the same error when calling sort on another program, this time giving a comparator function as 3rd argument. Any hint on getting rid of the compile error would be much appreciated.
THANKS.
[cpp]#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
#include <map>
#include <iomanip>
int main()
{
string input;
map<string, int> names;
map<string, int>::iterator itor, b, e;
int count=0;
while(true)
{
getline(cin, input);
if(cin.eof())
break;
if(names.find(input) == names.end())
names[input] = 1;
else names[input]++;
count++;
b = names.begin();
e = names.end();
sort(b,e);
cout.setf(ios::fixed);
cout << setprecision(4);
itor=names.begin();
while(itor != names.end())
{
cout << (*itor).first << " " << (*itor).second << "\n";
}
}
return 0;
}[/cpp]
THANKS.
[cpp]#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
#include <map>
#include <iomanip>
int main()
{
string input;
map<string, int> names;
map<string, int>::iterator itor, b, e;
int count=0;
while(true)
{
getline(cin, input);
if(cin.eof())
break;
if(names.find(input) == names.end())
names[input] = 1;
else names[input]++;
count++;
b = names.begin();
e = names.end();
sort(b,e);
cout.setf(ios::fixed);
cout << setprecision(4);
itor=names.begin();
while(itor != names.end())
{
cout << (*itor).first << " " << (*itor).second << "\n";
}
}
return 0;
}[/cpp]
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
10226 TLE
I can't believe I am having so many problems with this simple problem. I submitted at least 10 times and still get TLE. I have tried having 256 separate maps (one for each treename starting with a different ascii value character), or 256x256 (depending on ascii value of first 2 characters), and finally with 64x64 maps.
Could anyone please kindly tell me how you solved the problem w/o TLE? THANKS so much.
[cpp]
#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
#include <map>
#include <iomanip>
int main()
{
int numcases;
cin >> numcases;
string temp, input;
getline(cin, temp);
getline(cin, temp);
cout.setf(ios::fixed);
cout << setprecision(4);
for(int i=0; i<numcases; i++)
{
int count=0;
map<string, int> names[64][64];
map<string, int> group;
map<string, int>::iterator itor;
while(true)
{
if(cin.peek() == '\n')
{
getline(cin, temp);
break;
}
if(cin.eof())
break;
getline(cin, input);
if(input.length() == 1)
(names[input[0]/64][0])[input]++;
else (names[input[0]/64][input[1]/64])[input]++;
count++;
}
for(int i=0; i<64; i++)
{
for(int j=0; j<64; j++)
{
group = names[j];
itor = group.begin();
while(itor != group.end())
{
cout << (*itor).first << " ";
cout << (*itor).second * 100.0 / (double)count << "\n";
itor++;
}
}
}
cout << "\n";
}
return 0;
}[/cpp]
Could anyone please kindly tell me how you solved the problem w/o TLE? THANKS so much.
[cpp]
#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
#include <map>
#include <iomanip>
int main()
{
int numcases;
cin >> numcases;
string temp, input;
getline(cin, temp);
getline(cin, temp);
cout.setf(ios::fixed);
cout << setprecision(4);
for(int i=0; i<numcases; i++)
{
int count=0;
map<string, int> names[64][64];
map<string, int> group;
map<string, int>::iterator itor;
while(true)
{
if(cin.peek() == '\n')
{
getline(cin, temp);
break;
}
if(cin.eof())
break;
getline(cin, input);
if(input.length() == 1)
(names[input[0]/64][0])[input]++;
else (names[input[0]/64][input[1]/64])[input]++;
count++;
}
for(int i=0; i<64; i++)
{
for(int j=0; j<64; j++)
{
group = names[j];
itor = group.begin();
while(itor != group.end())
{
cout << (*itor).first << " ";
cout << (*itor).second * 100.0 / (double)count << "\n";
itor++;
}
}
}
cout << "\n";
}
return 0;
}[/cpp]