306 - Cipher

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Thu Feb 02, 2006 9:37 pm

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

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

306 WA

Post by IRA » Thu May 04, 2006 2:27 pm

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;
}

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu May 04, 2006 3:22 pm

Please use one of the existing threads for this posting!

AdamWG
New poster
Posts: 3
Joined: Sun Jul 16, 2006 7:32 pm

Post by AdamWG » Wed Jul 26, 2006 6:26 pm

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
New poster
Posts: 3
Joined: Thu Jul 27, 2006 4:32 pm

306 why CE

Post by smap16501004 » Tue Aug 22, 2006 1:47 pm

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!!! :cry:

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui » Thu Sep 07, 2006 8:11 pm

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
New poster
Posts: 7
Joined: Wed Feb 13, 2008 3:59 pm
Location: Dhaka,Bangladesh

306 - Cipher getting TLE

Post by assasin » Mon Mar 24, 2008 5:02 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 306 - Cipher getting TLE

Post by mf » Mon Mar 24, 2008 5:56 pm

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.
assasin wrote: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
New poster
Posts: 1
Joined: Thu Nov 06, 2008 10:46 am

Help me about 306 (CE)

Post by hasibul2363 » Thu Nov 06, 2008 11:27 am

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
New poster
Posts: 21
Joined: Wed Oct 08, 2008 7:04 am

Re: Help me about 306 (CE)

Post by porker2008 » Thu Nov 06, 2008 7:21 pm

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. :D

porker2008
New poster
Posts: 21
Joined: Wed Oct 08, 2008 7:04 am

Re: Help me about 306 (CE)

Post by porker2008 » Fri Nov 07, 2008 6:27 am

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
New poster
Posts: 10
Joined: Wed Dec 12, 2012 7:47 pm

306 Cipher (WA)

Post by Nut_Boltu » Thu Jan 17, 2013 4:52 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 306 Cipher (WA)

Post by brianfry713 » Thu Jan 17, 2013 10:22 pm

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

Nut_Boltu
New poster
Posts: 10
Joined: Wed Dec 12, 2012 7:47 pm

Re: 306 Cipher (WA)

Post by Nut_Boltu » Fri Jan 18, 2013 1:05 pm

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

hoimo
New poster
Posts: 18
Joined: Sun Sep 23, 2012 3:43 am

Re: 306 Cipher (WA)

Post by hoimo » Mon Dec 02, 2013 12:05 pm

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");
        }
    }
}

Post Reply

Return to “Volume 3 (300-399)”