Sorry to bother you again..Per wrote:There are four errors. The answer for the first case is "NO", the answer for the last YES should be NO, the answer for the second and sixth from the end should be YES.
For instance, for the second last case:
a -> baaabbababbaaa
b -> ababbaaaa
with starting string aabbbabab, we can get to aabab by just applying the b-rule once.
Thank you so very much for your help! With that simple little line, I realised that my understanding of the problem was completely wrong.Per wrote:Ah! Now (after having spent 20 minutes patching what I thought was a bug in my solution) I remember! I'm sorry to say that I have (unwillingly) tricked you.
The thing I thought not completely obvious from the problem statement (that I had forgotten) is that you apply both the a-rule and the b-rule at the same time. Thus, for your last example, we get
aba... -> aabaabaaaaabbabaaaaabaabaaaaab...
and so on, which never leads to more than two consecutive b's (since we must apply the rules to every character of the string). Or doing the reverse mapping, there simply is no way to get to bbbbb with the rules given.
Code: Select all
ab
/ \
aab abb
/ \ / \
aaaab aabb aabb abbbb
ecc ecc.
Per wrote:The thing I thought not completely obvious from the problem statement [...] is that you apply both the a-rule and the b-rule at the same time
My accepted program says "YES".wahab wrote:Can anyone tell what is the correct output for this problem for the following input:
baabbbbaabaaaaa
aabbababbbaaa
b
abb
That's not this judge's solution. It gets WA.but according to the judge solution in this link it is problem c it get
NO
Code: Select all
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
#define sqr(x) ((x) * (x))
#define abs(x) ((x) > 0 ? (x) : -(x))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define fill(x, y) memset((x), (y), sizeof(x))
#define PI 3.141592653589793238463
const int maxlen=30;
const int maxhash=70000;
const int maxstate=70000;
char u[maxlen], v[maxlen], goal[maxlen];
char st[maxstate][maxlen];
int goal_len, xxx;
bool vis[16][maxstate];
int hash(char *buf)
{
int val=0;
int len=strlen(buf);
for (int i=0;i<=strlen(buf)-1;i++) if (buf[i]=='a') val=val+(1<<(len-1-i));
return val;
}
bool try_to_insert(char *buf)
{
int h=hash(buf);
int len=strlen(buf);
if (vis[len][h]) return false;
vis[len][h]=true;
return true;
}
void bfs()
{
int front=1, rear=1;
while (front <= rear)
{
char tmp[maxlen]="\0";
strcpy(tmp,st[front]);
for (int i=0;i<=strlen(tmp)-1;i++)
if (tmp[i]=='a')
{
char buf[maxlen]="\0";
strncpy(buf,tmp,i);
strcat(buf,u);
strcat(buf,tmp+i+1);
// if (strstr(buf,goal)!=NULL) { printf("YES\n"); return; }
if (strlen(buf)<=goal_len)
{
if (try_to_insert(buf))
{
rear++;
strcpy(st[rear],buf);
if (vis[goal_len][xxx]) { printf("YES\n"); return; }
}
}
else
{
for (int j=0;j<=strlen(buf)-goal_len;j++)
{
char buf2[maxlen]="\0";
strncpy(buf2,buf+j,goal_len);
if (try_to_insert(buf2))
{
rear++;
strcpy(st[rear],buf2);
if (vis[goal_len][xxx]) { printf("YES\n"); return; }
}
}
}
}
else if (tmp[i]=='b')
{
char buf[maxlen]="\0";
strncpy(buf,tmp,i);
strcat(buf,v);
strcat(buf,tmp+i+1);
// if (strstr(buf,goal)!=NULL) { printf("YES\n"); return; }
if (strlen(buf)<=goal_len)
{
if (try_to_insert(buf))
{
rear++;
strcpy(st[rear],buf);
if (vis[goal_len][xxx]) { printf("YES\n"); return; }
}
}
else
{
for (int j=0;j<=strlen(buf)-goal_len;j++)
{
char buf2[maxlen]="\0";
strncpy(buf2,buf+j,goal_len);
if (try_to_insert(buf2))
{
rear++;
strcpy(st[rear],buf2);
if (vis[goal_len][xxx]) { printf("YES\n"); return; }
}
}
}
}
front++;
}
// if (vis[goal_len][xxx]) printf("YES\n");
// else printf("NO\n");
printf("rear=%d\n",rear);
printf("NO\n");
}
int main()
{
freopen("yy2.in","r",stdin);
freopen("yy.out","w",stdout);
while (gets(u)!=NULL)
{
gets(v); gets(st[1]); gets(goal);
goal_len=strlen(goal);
xxx=0;
for (int i=0;i<=goal_len-1;i++) if (goal[i]=='a') xxx=xxx+(1<<(goal_len-1-i));
if (strstr(st[1],goal)!=NULL) printf("YES\n");
else
{
fill(vis,false);
try_to_insert(st[1]);
bfs();
}
}
return 0;
}