10981 - String Morphing

[mf]

This is how I'm doing it:

Code: Select all

/*
 *  which() -- determines the leftmost pair of characters, which can be
 *  multiplied, such that the character 'dst' still can be obtained from
 *  the resulting string.
 *
 *  Returns the offset of the first character in the pair, or -1 if
 *  the character 'dst' can't be obtained from the initial string.
 */
int which(int src[], int n, int dst)
{
    int can[16][16][4], first[16][16][4];

    /*
     *  can[offs][len][chr] = can the substring src[offs .. offs+len-1] be
     *  morphed to character chr?
     *
     *  If so, then first[offs][len][chr] = the smallest possible offset, at
     *  which the first multiplication may occur.
     */

    for (int i = 0; i < n; i++)
        for (int j = 0; j < 3; j++)
            can[i][1][j] = (j == src[i]);

    first[0][n][dst] = -1;
    for (int offs = n - 1; offs >= 0; offs--)
        for (int len = 2; offs + len <= n; len++) {
            for (int c = 0; c < 3; c++)
                can[offs][len][c] = 0;

            for (int k=1;k<len;k++) for(int c1=0;c1<3;c1++) for(int c2=0;c2<3;c2++) {
                if (!can[offs][k][c1] || !can[offs+k][len-k][c2])
                    continue;

                int f, c = mul[c1][c2];
                if (k > 1)
                    f = first[offs][k][c1];
                else if (len - k > 1)
                    f = first[offs+k][len-k][c2];
                else
                    f = offs;

                if (!can[offs][len][c] || f < first[offs][len][c]) {
                    can[offs][len][c] = 1;
                    first[offs][len][c] = f;
                }
            }
        }

    return first[0][n][dst];
}

[shanto86]

this N^4 code makes TLE. i think this looks same as mf's code (the function part)

Code: Select all

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

int array[200],target;
int ok[200][200][3];
int p[200][200][3];
int mul[5][5];

int POSSIBLE(int sz)
{
	int i,j,c,c1,c2,len,k,first;

	for(i=0;i<sz;i++)
		for(j=0;j<3;j++)
			ok[i][i][j]=(array[i]==j);

	for(len=2;len<=sz;len++)
		for(i=0;i<=sz-len;i++)
		{
			j=i+len-1;

			ok[i][j][0]=ok[i][j][1]=ok[i][j][2]=0;

			for(k=i;k<j;k++)
				for(c1=0;c1<3;c1++) if(ok[i][k][c1])
					for(c2=0;c2<3;c2++) if(ok[k+1][j][c2])
					{
						c=mul[c1][c2];

						if(k-i+1>1)
							first=p[i][k][c1];
						else if(j-k>1)
							first=p[k+1][j][c2];
						else 
							first=i;

						if(ok[i][j][c]==0 || p[i][j][c]>first)
						{
							p[i][j][c]=first;
							ok[i][j][c]=1;
						}

					}
		}

		if(ok[0][sz-1][target]==0) return -1;
		return p[0][sz-1][target];
}

int main()
{
	int ks,n,i,x,now,j;
	char word[300];
	char yy[10];

	mul[0][0]=1; mul[0][1]=1; mul[0][2]=0;
	mul[1][0]=2; mul[1][1]=1; mul[1][2]=0;
	mul[2][0]=0; mul[2][1]=2; mul[2][2]=2;

	scanf("%d",&ks);

	while(ks--)
	{
		scanf("%s%s",word,yy);
		n=strlen(word);
		target=yy[0]-'a';

		for(i=0;i<n;i++) array[i]=word[i]-'a';

		x=POSSIBLE(n);

		if(x==-1)
		{
			printf("None exist!\n");
			if(ks) printf("\n");
			continue;
		}

		printf("%s\n",word);

		now=n;
		for(i=2;i<=n;i++)
		{
			now--;
			array[x]=mul[array[x]][array[x+1]];
			word[x]=array[x]+'a';
			for(j=x+1;j<now;j++) 
			{
				array[j]=array[j+1];
				word[j]=array[j]+'a';
			}

			word[j]=0;

			printf("%s\n",word);

			x=POSSIBLE(now);
		}

		if(ks) printf("\n");

	}

	return 0;
}