306 - Cipher

[mamun]

Thank you so much mf for your nice explanation. Examples describe things so nicely. Solved it now.

[IRA]

I got WA again!
I can't find the problem.
I use many input data to test my program.
Who can help me?
Thanks in advanced.

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n,k,i,j,key,id;
unsigned char word[201],temp[201],C[200][200],T[200];

int main(void){
	while(1){
		scanf("%d",&n);
		if(n){
			for(i=0;i<n;i++)scanf("%d",&T[i]);
			for(i=0;i<n;i++){
				for(j=1,id=i+1;j==1||id!=i+1;id=T[id-1]){
					C[i][j++]=id;
				}
				C[i][0]=j-1;
			}
			while(1){
				scanf("%d ",&k);
				if(k){
					gets(word);
					for(i=strlen(word);i<n;i++)word[i]=' ';
					for(i=0;i<n;i++){
						key=k%(C[i][0]);
						key=C[i][key+1];
						temp[key-1]=word[i];
					}
					temp[n]='\0';
					printf("%s\n",temp);
				}
				else break;
			}
			printf("\n");
		}
		else break;
	}
	return 0;
}

[little joey]

Please use one of the existing threads for this posting!

[AdamWG]

Hi all,

I'm getting Wrong Answer, but my output is correct for all the test cases I've found on the board. I can't think of any corner cases where my program will fail. Any suggestions?

[smap16501004]

Code: Select all

#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
int list[1000][300];
int main(void)
{
    int n,i,j,t,T,l,c;
    char str[1000],temp[1000];
    while(cin>>n && n!=0)
    {
        for(i=0;i<n;i++)
            cin>>list[0][i];
        t=1;
        c=0;
        
        while(t)
        {
            c++;
            for(i=0;i<n;i++)
                list[c][i]=list[c-1][list[0][i]-1];
            t=0;
            for(i=0;i<n;i++)
                if(list[c][i]!=list[0][i])
                {
                    t=1;
                    break;
                }
        }
         
        while(cin>>T && T!=0)
        {
            
            cin.get();
            cin.getline(str,n+1);
            l=strlen(str);
            for(i=l;i<n;i++)
                str[i]=' ';
            temp[n]='\0';
            
            if(c>0)
            {
                T=T%c-1;
                if(T<0)T=c-1;
            }
            for(i=0;i<n;i++)
                temp[list[T][i]-1]=str[i]; 
             
            cout<<temp<<endl;
        }
        cout<<endl;
    }
    return 0;
}

help please!!!

[tan_Yui]

I got many WA, but I could solve finally.
I missed out this part.

Next lines contain integer number k and one message of ascii characters separated by one space.

If you faced same problem as me, please try the following case.

Input:

Code: Select all

10
4 5 3 7 2 8 1 6 10 9
14 eccApted!!
12  Accepted!
16  hesAnTwer
0
10
2 8 7 6 5 10 4 3 1 9
9 0123456789
2  ob l emrP
8 /SI lpmaOe
7 secmua.av.
3   eahOpTMn
4  c!Haeon G
5     Ao It
6 l!Enlcxtee
31415  oeosvYdlu
1  nE e.hT d
10 tiuY_/na /
0
0

Output:

Code: Select all

Accepted!!
 Accepted!
The Answer

0123456789
Problem   
Sample I/O
acm.uva.es
On The Map
He can Go!
    A to I
Excellent!
You solved
  The End.
 tan_Yui//

Best regards.

[assasin]

I just cannot find the reason of getting TLE
I have checked for cycle if k is large enough to produce a cycle
Otherwise I just went through O(nk) times to print result
Is there any way to improve performance
please Help.

Code: Select all

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

int n,k;
int array[201];
char string[201];
char temp[201];
char permanent[201];
int mod,modTemp;
int modCheck;

void GiveAns( ){

	int i,j;
	int len = strlen(string);

	if(strcmp(string,permanent))
		if(len < n){
			for(i = len ; i < n ; i++)
				string[i] = ' ';
			string[i] = '\0';
		}

	
	
	strcpy(permanent,string);	
	strcpy(temp,string);

	
	if(!mod){
		for( i = 1 ; i <= k ; i++){

			for( j = 0 ; j < n ; j ++)
				string[array[j] - 1] = temp[j];

			strcpy(temp,string);
			if(!strcmp(string,permanent)){
				mod = i;
				modCheck = 1;
				break;
			}
		}	
		
		
	}

	if(mod){

		int loop;
		if( k < mod)
			loop = k;
		else loop = k % mod;

		for( i = 1 ; i <= loop ; i++){

			for( j = 0 ; j < n ; j ++)
				string[array[j] - 1] = temp[j];

			strcpy(temp,string);
		}
	}

	printf("%s\n",string);
	
}

int main(){

	int i,j;
	char ch;
	int flag = 0;
	int block = 0;

	while(scanf("%d",&n) != EOF){

		if(n ==0)
			break;

		//if(block++)
			//printf("\n");

		for( i = 0 ; i < n ; i++ )
			scanf("%d",&array[i]);		
		
		while(1){
			
			scanf("%d",&k);

			if( k == 0)
				break;
				
			scanf("%c%[^\n]s",&ch,string);
			scanf("%c",&ch);
			GiveAns();
			flag = 1;
		}

		flag = 0;
		mod = 0;
		modCheck = 0;
		printf("\n");
	}

	return 0;
}

[mf]

Otherwise I just went through O(nk) times to print result

That's too slow.
Try to do it in O(n log k) or even O(n). That's possible, read past threads about this problem if you're stuck.

And next time please post in one of those threads, instead of creating a new thread.

I have checked for cycle if k is large enough to produce a cycle

Cycles can get very, very, very big.
Don't think you can find one by just brute forcing.

[hasibul2363]

I am always getting Compilation error, but it runs my computer without any problem. Pls help me abt that.
Here is my Code:

Thanks in Advance

Code: Select all

/********306*******/

#include<iostream>
#include<string>

using namespace std;


int main()
{


int lomba,key[202];
char d_char[202],c_char[202];

int len,koibar;
cin>>lomba;
for(int i=0;i<lomba;i++)
{
	cin>>key[i];
}
gets(d_char);

while(scanf("%d %[^\n]",&koibar,d_char)==2)
{

if(koibar ==0) break;

len = strlen(d_char);

if(len<lomba)
for(int m=len; m<lomba;m++)
{
	d_char[m] = 32;
}

koibar%=6;

if(koibar==0)
{
	cout<<d_char<<endl;
}
else
{

for(int j = 0;j<koibar;j++)
{

	for(i=0;i<lomba;i++)
	{
	c_char[key[i]-1] = d_char[i];
	}


c_char[lomba] = '\0';

strcpy(d_char,c_char);

}
cout<<c_char<<endl;
d_char[0] ='\0';
c_char[0] = '\0'; 


}
}
	return 0;
}

[porker2008]

Please look at this for-loop.
i is blinded.
You can't use it before declare it.

Code: Select all

   for(i=0;i<lomba;i++)
   {
   c_char[key[i]-1] = d_char[i];
   }

I suggest you change it like this way as you use before:

Code: Select all

   for(int i=0;i<lomba;i++)
   {
   c_char[key[i]-1] = d_char[i];
   }

Hope it helps.

[porker2008]

Maybe u are using VC6 as your compiler...

VC6 will not complain if you use a variable that had been declared but blinded.

However, gcc & g++ will complain.

[Nut_Boltu]

I m getting WA. please someone help.
Here's my code below:

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int Cycle[201][201];
int numofpos[201];

void findCycle(int N,int S[])
{
    int find[201],count,init;
    for(int j=0;j<N;j++)
    {
         init=j;
        for(int i=0;i<N;i++) find[i]=-1;
        for(count=0;count<N;count++)
        {
                Cycle[j][count]=S[init];
                init=S[init];
                if(!find[init]) break;
                else find[init]=0;

        }
        numofpos[j]=count;
    }

}
int main()
{

    int N,k;
    int Seq[201];
    char str[201],line[201];

    bool bline=false;
    while(cin>>N)
    {
        if(!N) break;
        if(bline) cout<<endl;
        bline=true;

        int temp;
        for(int i=0;i<N;i++) cin>>temp,Seq[i]=temp-1;

        findCycle(N,Seq);

        while(cin>>k)
        {
            if(!k) break;
            gets(str);

            int c=strlen(str)-1;
            memcpy(line, &str[1],c);
            for(int i=c;i<N;i++) line[i]=' ';
            line[N]='\0';

            for(int i=0;i<N;i++)
            {
                int fpos = Cycle[i][(k-1)%numofpos[i]];
               str[fpos]=line[i];
            }
            str[N]='\0';
            cout<<str<<endl;
        }


    }


    return 0;
}

[brianfry713]

Doesn't match the sample I/O.

[Nut_Boltu]

Thanks. i just skipped the line "After each block there is one empty line."
I printed empty line in between two blocks.

[hoimo]

i am getting time limit. plz help.

Code: Select all

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

int main()
{
    char str[201], rep[201];
    int i, j, n, k, seq[201];

    while(scanf("%d", &n) == 1)
    {
        if( n==0 )
            break;

        else
        {
            for( i=0; i<n; i++ )
                scanf("%d", &seq[i]);

            while( scanf("%d",&k) == 1 )
            {
                if( k!=0 )
                {
                    getchar();
                    gets(str);

                    if( strlen(str) != n )
                    {
                        for( i=strlen(str); i<=n; i++ )
                            str[i] = ' ';
                    }
                    str[strlen(str)+1] = '\0';

                    for( i=0; i<k; i++ )
                    {
                        for( j=0; j<n; j++ )
                        {
                            rep[seq[j]-1] = str[j];
                        }
                        rep[j] = '\0';
                        strcpy( str,rep );
                    }
                    puts(str);
                }
                else
                    break;
            }
            printf("\n");
        }
    }
}