Page 3 of 3
Re: 10391 - Compound Words
Posted: Wed Jan 25, 2012 2:18 am
by brianfry713
Less than 30.
10391 - Compound Words
Posted: Fri Jun 29, 2012 6:48 am
by 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;
}
Re: 10391 - Compound Words
Posted: Fri Jun 29, 2012 12:42 pm
by 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
10391 compound words : wrong answer
Posted: Mon Dec 31, 2012 12:23 pm
by 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
Re: 10391 compound words : wrong answer
Posted: Mon Dec 31, 2012 12:24 pm
by usamamaqbool
Everytime I read through getline or cin or a file it gives WRONG ANSWER
Re: 10391 compound words : wrong answer
Posted: Tue Jan 01, 2013 3:16 am
by 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
to:
Re: 10391 compound words : wrong answer
Posted: Tue Jan 08, 2013 5:40 am
by 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;
}
Re: 10391 compound words : wrong answer
Posted: Tue Jan 08, 2013 5:41 am
by usamamaqbool
Thanks brianfry713 ...
Kindly Check Its now giving TLA????
Re: 10391 compound words : wrong answer
Posted: Tue Jan 08, 2013 9:20 pm
by brianfry713
It doesn't match the sample I/O.
Use the code blocks when posting code so the indentation is preserved.
Re: 10391 - Compound Words
Posted: Tue May 06, 2014 6:46 pm
by Muftee_Ruet
what is the output of the following input?
Re: 10391 - Compound Words
Posted: Wed May 07, 2014 9:23 pm
by brianfry713