10126 - Zipf's Law

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

Moderator: Board moderators

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

10126 - Zipf's Law

Post by 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
New poster
Posts: 3
Joined: Thu Jul 18, 2002 1:17 pm

Post by 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.
------------------------------------------------------------
Try this. If you still have problem write again. :wink:
Good Luck.
Neo

Kelompok 5
New poster
Posts: 1
Joined: Mon Dec 09, 2002 6:07 am

array size too large ?

Post by 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
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

Post by 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
New poster
Posts: 7
Joined: Mon Aug 12, 2002 12:13 am

Post by rfcotta »

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

Rafael Cotta

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

Post by PMNOX »

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

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by 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
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

10126 zipf's law Time Limit Exceeded

Post by 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
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:

10126 Zipf's Law (WA)

Post by 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]

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal »

you are not printing blank line correctly.

supermin
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:

Post by 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.

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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 :wink:
Last edited by saiqbal on Sun Mar 30, 2003 3:32 pm, edited 1 time in total.

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by 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.

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal »

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

hope it didn't cause too much trouble :-?

thanx
-sohel

supermin
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:

Post by 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?

Post Reply

Return to “Volume 101 (10100-10199)”