10391 - Compound Words
Moderator: Board moderators
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10391 - Compound Words
Less than 30.
Check input and AC output for thousands of problems on uDebug!
10391 - Compound Words
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
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;
}
Re: 10391 - Compound Words
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
"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
-
- New poster
- Posts: 4
- Joined: Mon Dec 31, 2012 12:19 pm
10391 compound words : wrong answer
//#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
#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
-
- New poster
- Posts: 4
- Joined: Mon Dec 31, 2012 12:19 pm
Re: 10391 compound words : wrong answer
Everytime I read through getline or cin or a file it gives WRONG ANSWER
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10391 compound words : wrong answer
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 lineto:
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;
Code: Select all
size=120000;
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 4
- Joined: Mon Dec 31, 2012 12:19 pm
Re: 10391 compound words : wrong answer
#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;
}
#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;
}
brianfry713 wrote: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 lineto:Code: Select all
size=120,000;
Code: Select all
size=120000;
-
- New poster
- Posts: 4
- Joined: Mon Dec 31, 2012 12:19 pm
Re: 10391 compound words : wrong answer
Thanks brianfry713 ...![:)](./images/smilies/icon_smile.gif)
Kindly Check Its now giving TLA????
![:)](./images/smilies/icon_smile.gif)
Kindly Check Its now giving TLA????
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10391 compound words : wrong answer
It doesn't match the sample I/O.
Use the code blocks when posting code so the indentation is preserved.
Use the code blocks when posting code so the indentation is preserved.
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 10
- Joined: Fri Sep 16, 2011 6:36 am
Re: 10391 - Compound Words
what is the output of the following input?
Code: Select all
a
ali
alien
en
lien
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10391 - Compound Words
Check input and AC output for thousands of problems on uDebug!