## 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:
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

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,temp,C,T;

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]=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]);
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Please use one of the existing threads for this posting!
AdamWG
New poster
Posts: 3
Joined: Sun Jul 16, 2006 7:32 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

Code: Select all

``````#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
int list;
int main(void)
{
int n,i,j,t,T,l,c;
char str,temp;
while(cin>>n && n!=0)
{
for(i=0;i<n;i++)
cin>>list[i];
t=1;
c=0;

while(t)
{
c++;
for(i=0;i<n;i++)
list[c][i]=list[c-1][list[i]-1];
t=0;
for(i=0;i<n;i++)
if(list[c][i]!=list[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
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
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

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;
char string;
char temp;
char permanent;
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

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)

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;
char d_char,c_char;

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';
c_char = '\0';

}
}
return 0;
}

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

### Re: Help me about 306 (CE)

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

### Re: Help me about 306 (CE)

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)

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;
int numofpos;

void findCycle(int N,int S[])
{
int find,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;
char str,line;

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,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)

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)

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)

i am getting time limit. plz help.

Code: Select all

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

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

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