10391 - Compound Words

[brianfry713]

Less than 30.

[bunnyxl]

Hi. I got WA for this question. But I think I have removed the case that one word can be fromed in different ways. Can anyone tell some special cases for this problem ? Thanks

And below is my code

Code: Select all

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

char *r;
char *f;
int MAX;

class Lnode{
public:
	Lnode(){comp=0;isword=false; for(int i=0; i<26; i++)l[i]=0;}
	void add();
	void travle(int idx);
	void find(int idx);
	bool match(char *s);
	void disout(int idx);
private:
	bool isword;
	int comp;
	Lnode *l[26];
	static int len;
};

Lnode *root;

void Lnode::disout(int idx){
	if(comp==1){
		r[idx]=0;	
		printf("%s\n", r);
	}
	for(int i=0; i<26; i++){
		if(l[i]){
			r[idx] = 'a'+i;
			l[i]->disout(idx+1);
		}
	}
}

void Lnode:: add(){
	char c;
	int idx;
	if((c=getchar())=='\n'){
		isword=true;
		if(len> MAX)
			MAX=len;
		len=0;
		return;
	}
	len++;
	idx = c-'a';
	if(!l[idx])
		l[idx] = new Lnode;
	l[idx]-> add();
}

void Lnode:: find(int idx){
	if(isword){
		f[idx]=0;
		if(idx>0 && strcmp(r,f) &&root->match(f)){
			comp++;
		}
	}
	for(int i=0; i<26; i++){
		if(l[i]){
			f[idx]= i+'a';
			l[i]->find(idx+1);
		}
	}
}

bool Lnode:: match(char *s){
	if(!(*s)){
		return isword;
	}
	int idx= *s-'a';
	if(!l[idx])
		return false;
	return l[idx]-> match(s+1);
}

void Lnode:: travle(int idx){
	if(isword){
		r[idx]=0;
		find(0);		
	}
	for(int i=0; i<26; i++){
		if(l[i]){
			r[idx]= 'a'+i;	
			l[i]->travle(idx+1);
		}
	}
}

int Lnode:: len=0;

int main(){
	root = new Lnode;
	MAX=0;
	while(cin.peek()!=EOF){
		root-> add();
	}
	r = new char[MAX+1];
	f = new char[MAX+1];
	root->travle(0);
	root->disout(0);
	return 0;
}

[bunnyxl]

Well I've just AC this problem and I think the problem statement has some problem so I write down in case you meet the same problem in the further.

"A two-word compound word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary"

The word exactly has no use here. The output will still have cases that
1. one word is the concatenation of the same word
2. one word is the concatenation of different combinations of words
And also, it seems that two-letter word in the output will be rejected... I don't why
Finally, please fix if there is any multiple lines in your output

See if this can help

[usamamaqbool]

//#include <fstream>
#include <iostream>
#include<string>
using namespace std;


class hash
{
private:
string *p;
int size;
int *flag;
int key;
string var;
public:
hash()
{
size=120,000;
key=0;
var='\0';
}
hash(int size,string name,int key)
{
this->size=size;
this->key=key;
this->var=var;
}
void setName(string var)
{
this->var=var;
}
string getVar()
{
return var;
}
void setKey(int key)
{
this->key=key;
}
int getKey()
{
return key;
}
void setSize(int size)
{
this->size=size;
}
int getSize()
{
return size;
}
void createArray()
{

if(size>0)
{
p=new string[size];
this->size=size;
flag=new int[size];
this->size=size;
for(int i=0;i<size;i++)
p='\0';
for(int i=0;i<size;i++)
flag=0;
}
}
void hashFunc(string var)
{
int temp=0,sum=0;
for(unsigned int i=0; i<(var.length());i++)
{
temp=var-'0';
sum=sum+temp;
}
key=sum%size;
setKey(key);

}
void insert(string var)
{

hashFunc(var);
int a=getKey();
if(flag[a]==0)
{
p[a]=var;
flag[a]=1;
}

else
{
while(flag[a]!=0 && flag[a]<size && a+1<size )
{
a=a+1;
a=a%size;
}
if(flag[a]==0)
{
p[a]=var;
flag[a]=1;
}
else
{
cout<<"Memory Full";
}
}


}
void search()
{
for(int i=0;i<size;i++)
{
if(flag==1)
{

for(int j=0;j<size;j++)
{
if(flag[j]==1&& i!=j)
{
string c=p+p[j];
for(int z=0;z<size;z++)
{
if(c==p[z])
{
cout<<p[z]<<endl;
}


}

}
}
}

}
}


};


int main()
{
hash h;
int size=0;
string var;
h.createArray();
//ifstream infile;
//infile.open ("example.dat",ios::app);
//while(!infile.eof()) // To get you all the lines.
//{
// infile>>var;
// h.insert(var);

//}
while((getline(cin,var)) !=NULL)
{
h.insert(var);

}
h.search();
//infile.close();
return 0;
}





why is this code not accepted

[usamamaqbool]

Everytime I read through getline or cin or a file it gives WRONG ANSWER

[brianfry713]

Read from stdin, write to stdout, not from/to a file.
http://uva.onlinejudge.org/index.php?op ... &Itemid=30

Try solving it using a set instead of a hash.

Maybe change the line

Code: Select all

size=120,000;

to:

Code: Select all

size=120000;

[usamamaqbool]

#include <iostream>
#include<stdio.h>
#include<string>


using namespace std;

int main()
{
string *p;
string var;
int *flag;
int a=0;
int size=120000;
p=new string[size];
flag=new int[size];
for(int i=0;i<size;i++)
{
p="NULL";
flag=0;
}

while((getline(cin,var)) !=NULL)
{
int temp=0,sum=0;
for(unsigned int i=0; i<(var.length());i++)
{
temp=var-'0';
sum=sum+temp;
}
a=sum%size;
if(flag[a]==0)
{
p[a]=var;
flag[a]=1;
}

else
{
while(flag[a]!=0 && flag[a]<size && a+1<size )
{
a=a*2;
a=a%size;
}
if(flag[a]==0)
{
p[a]=var;
flag[a]=1;
}
}
}
for(int i=0;i<a;i++)
{
if(flag==1)
{
for(int j=0;j<a;j++)
{
if(flag[j]==1 && i!=j)
{
string c=p+p[j];
int z=0;
while(z<a)
{
if(c==p[z] && flag[z]==1)
{
flag[z]=0;
cout<<p[z]<<"\n";
}
z++;
}


}


}
}
}
return 0;
}

Read from stdin, write to stdout, not from/to a file.
http://uva.onlinejudge.org/index.php?op ... &Itemid=30

Try solving it using a set instead of a hash.

Maybe change the line

Code: Select all

size=120,000;

to:

Code: Select all

size=120000;

[usamamaqbool]

Thanks brianfry713 ...

Kindly Check Its now giving TLA????

[brianfry713]

It doesn't match the sample I/O.

Use the code blocks when posting code so the indentation is preserved.

[Muftee_Ruet]

what is the output of the following input?

Code: Select all

a
ali
alien
en
lien

[brianfry713]

http://www.uvatoolkit.com/problemssolve.php