10126 - Zipf's Law

[Subeen]

why my program got W.A.?
help me plz...

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

int sort_function( const void *a, const void *b);

void main()
{
	char z[10005][50];
	char ara[50], temp[50];
	int n, i, j, k, l, cs=0, len, flag;

	while(scanf("%d", &n)==1)
	{
		cs++;
		if(cs!=1) printf("\n");
		i = 0;
		while(1)
		{
			scanf("%s", temp);
			if(!strcmp(temp, "EndOfText")) break;
         len = strlen(temp);
			for(j=0, k=0; j < len; j++)
				if(isalnum(temp[j]))
					ara[k++] = tolower(temp[j]);
			ara[k] = 0;
			temp[j] = 0;
         if(!k) continue;
			strcpy(z[i], ara);
         i++;
		}
		z[i][0] = 0;
		k = i;

		qsort((void *)z, k, sizeof(char)*50, sort_function);

      flag = 0;
		for(i=0; i<k; )
      {
      	strcpy(temp, z[i]);
         for(j=i, l=0; !strcmp(z[j], z[j+1]);j++, l++);
         if(++l==n)
         {
         	printf("%s\n", z[i]);
            flag = 1;
         }
         i = ++j;
      }
      if(!flag) printf("There is no such word.\n");
	}
}

int sort_function( const void *a, const void *b)
{
   return( strcmp((char *)a,(char *)b) );
}

[Neo]

I did not solve this problem. But who told you that English words are
of maximum size 50 chars? Try 200 and then search for other errors.

One more thing, the problem says:

Code: Select all

A word is a sequence of letters. Words are separated by non-letters.

I think digit is not a letter. Let me know if it is really.

[Kelompok 5]

I'm trying to solve problem no. 10126 which requires array of char [10000][a] with a at least 50, preferably 100. But it causes error message : array size too large. How should I declare this string?

[PMNOX]

maybe you should use dynamic memory??

char *A[100];
for( int i=0;i<100;i++)
A = malloc(10000 * sizeof(char));

i hope it will work, because i don't use C

[rfcotta]

Big arrays MUST be global. If you declare them locally you'll use the stack and will probably have problems.

Rafael Cotta

[PMNOX]

you could use string, but it doesn't work with c, c++ only:((

[rjhadley]

This problem seems straightforward, but I can't seem to get it accepted. Any thoughts as to what I am doing wrong?

Thanks.

[cpp]
#include <algorithm> // sort()
#include <cctype> // tolower()
#include <cstdio>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

int
main( void )
{
const string LETTERS( "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz" );
const string SENTINEL( "EndOfText" );
bool first( true );

while( true ) {
string line;
int targetFrequency; // aka n

// read target frequency
getline( cin, line );
if( cin.eof() || cin.fail() ) {
break;
} // if
sscanf( line.c_str(), "%d", &targetFrequency );


map< string, int > dictionary; // < word, frequency >
vector< string > wordList; // with target frequency
bool done( false );

// read text
while( ! done ) {
string::size_type pos1( 0 );
string::size_type pos2( 0 );
string token;
bool isWord( false );

getline( cin, line );
if( cin.eof() || cin.fail() ) {
break;
} // if

do {
// tokenize
if( isWord ) {
pos2 = line.find_first_not_of( LETTERS, pos1 );
} else {
pos2 = line.find_first_of( LETTERS, pos1 );
} // if

if( isWord ) {
if( pos2 == string::npos ) {
token = line.substr( pos1 );
} else {
token = line.substr( pos1, pos2 - pos1 );
} // if

if( token == SENTINEL ) {
done = true;
break;
} // if

for( string::iterator iter = token.begin();
iter != token.end(); iter++ ) {
(*iter) = tolower( *iter );
} // for
dictionary[ token ]++;
} // if

pos1 = pos2;
isWord = ( ! isWord );
} while( pos2 != string::npos );
} // while

// find the words with the target frequency and sort them
for( map< string, int >::const_iterator iter = dictionary.begin();
iter != dictionary.end(); iter++ ) {
if( (*iter).second == targetFrequency ) {
wordList.push_back( (*iter).first );
} // if
} // for
sort( wordList.begin(), wordList.end() );

// output results with blank separating cases
if( first ) {
first = false;
} else {
cout << endl;
} // if
if( wordList.size() > 0 ) {
for( vector< string >::const_iterator iter = wordList.begin();
iter != wordList.end(); iter++ ) {
cout << (*iter) << endl;
} // for
} else {
cout << "There is no such word." << endl;
} // if
} // while

return 0;
} // main()
[/cpp]

[stcheung]

Hmm, I have no idea why my code results in Time Limit Exceeded. I don't think it's really THAT inefficient. First of all, it calls getline() repeatedly and gives back the entire text string, stored in variable "text". Then it parses through the entire text string character by character in order to add each valid word in the text to a list<string> stored in variable "words". Then sort this list<string> "words". Now that identical words will be next to each other in "words", I just traverse through it to see how many times each word occurs, and output accordingly.


[cpp]#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <ctype.h>
#include <list>

int K;
list<string> words;

void output();

int main()
{
string word, line, text;
char ch;
while(true)
{
cin >> K;
text = "";
word = "";
words.clear();
if(cin.eof())
break;
while(true)
{
getline(cin, line);
if(line == "EndOfText")
break;
text = text + " " + line;
}

for(int i=0; i<text.length(); i++)
{
ch = text;
if(!isalpha(ch) && word != "")
{
words.push_back(word);
word = "";
}
else if(isalpha(ch))
word+=(tolower(ch));
}
if(words.size() == 0)
continue;
words.sort();
list<string>::iterator itor = words.begin();
/*
while(itor != words.end())
{
cout << *itor++ << "\n";
}
*/
output();
cout << "\n";
}
return 0;
}

void output()
{
int counter = 0;
string lastword, thisword;
list<string>::iterator itor = words.begin();
lastword = *itor;
while(true)
{
thisword = *itor++;
if(lastword == thisword)
counter++;
else
{
if(counter == 2)
cout << lastword << "\n";
counter = 1;
}
lastword = thisword;
if(itor == words.end())
{
if(counter == 2)
cout << lastword << "\n";
break;
}
}
}[/cpp]

[supermin]

I use binary tree to save the datas and "inorder" to print out the answers.
But I got W.A. .Could anyone will help me with my code,or send me the sample I missed.Thx.

Code: Select all

[c]
#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>

struct TREE{
	int count;
	char *alpha;
	struct TREE *left,*right;
};

int judgeanswer; /* judge if there is no answer */

void getstring(char*);
void inorder(struct TREE *node,int num);

int main()
{	
	char letter[200];
	int num;
	struct TREE *root,*ptr;
	int nl=0;

	while(scanf("%d",&num)!=EOF){
		judgeanswer=0;

		root=(struct TREE *)malloc(sizeof(struct TREE));
		root->left=root->right=NULL;
		getstring(letter);
		root->alpha=(char *)malloc(strlen(letter)+1);
		strcpy(root->alpha,letter);
		root->count=1;
		
		if(strcmp(letter,"endoftext")) {
			while(1){
				getstring(letter);
				if(!strcmp(letter,"endoftext")) break;
				
				ptr=root;			
				while(1){
					if(!strcmp(letter,ptr->alpha)){
						ptr->count++;							
						break;
					}
					else if(strcmp(letter,ptr->alpha)>0){
						if(ptr->right==NULL){								
							ptr->right=(struct TREE*)malloc(sizeof(struct TREE));
							ptr=ptr->right;
							ptr->left=ptr->right=NULL;
							ptr->alpha=(char *)malloc(strlen(letter)+1);								
							strcpy(ptr->alpha,letter);
							ptr->count=1;								
							break;
						}
						else
							ptr=ptr->right;					
					}
					else {
						if(ptr->left==NULL){
							ptr->left=(struct TREE*)malloc(sizeof(struct TREE));
							ptr=ptr->left;								
							ptr->left=ptr->right=NULL;
							ptr->alpha=(char *)malloc(strlen(letter)+1);
							strcpy(ptr->alpha,letter);
							ptr->count=1;								
							break;								
						}
						else
							ptr=ptr->left;						
					}/* end of else */
				}/* end of while(1) */				
			}/* end of while(1) */		
			inorder(root,num);
		}/* end of if(strcmp(letter,"endoftext")) */
		if(nl) printf("\n");
		else nl=1;
		if(!judgeanswer) printf("There is no such word.\n");
		
	}/* end of "while(scanf("%d",&num)!=EOF)" */
	return 0;
}

void getstring(char* letter){
	char ch;	
	int i=0,state=0;

	while((ch=getchar())!=EOF){
		if(isalpha(ch)) {
			ch=tolower(ch);
			letter[i++]=ch;
			state=1;
		}
		else if(state==1)
			break;
	}
	letter[i]='\0';	
}

void inorder(struct TREE *node,int num){
	if(node!=NULL){
		inorder(node->left,num);
		if(node->count==num) {
			printf("%s\n",node->alpha);	
			judgeanswer=1;
		}
		inorder(node->right,num);			
	}
}
[/c]

[saiqbal]

you are not printing blank line correctly.

[supermin]

blank line ??
I print a blank line between cases.

Code: Select all

if(nl) printf("\n"); 
else nl=1; 

Is there any wrong??
By the way,if there is only blank line's error and my answer is correct,the system should judge me P.E.

Anyway,thx.

[saiqbal]

i actually didn't analize your code but when i tried with some input i found your code sometimes prints blank line before an output and sometimes after output and after all it gets messed up. try the following input:

Code: Select all

2
abcd abcd
EndOfText
2
abcd
EndOfText
2
abcd abcd
EndOfText
2
abcd
EndOfText

hope its clear now.

and about P.E. your assumption is not always true. your case is the example

[junjieliang]

After seeing your test case, I'm really confused now...
Can someone explain to me the format of the input, and will EndOfText be case-sensitive?

Thanks.

[saiqbal]

im really sorry about the confusion i caused. it was my mistake really and i forgot the input specification. i changed the input accordingly.

hope it didn't cause too much trouble

thanx
-sohel

[supermin]

hmm..I test the input sample you modified.My ouput is following:

Code: Select all

abcd

There is no such word.

abcd

There is no such word.

Is it correct?