306  Cipher
Moderator: Board moderators

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
It's strange, beacuase I use arrays only for 205 elements.... So I think, that you must have mistake in your code ...
Best regards
DM
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut
how can i use lcm in 306
i always get TLE,too
help...
help...

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
I think that's no upper limit for k.
You must find cycles and it's all ... If you still coudn't get Acc, you can send me your code, titid_gede ...
Best regards
DM
You must find cycles and it's all ... If you still coudn't get Acc, you can send me your code, titid_gede ...
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut
sorry for late reply. here is my code :
[c]
 cutted
[/c]
thank you very much.
with love & light,
titid
[c]
 cutted
[/c]
thank you very much.
with love & light,
titid
Last edited by titid_gede on Fri Aug 29, 2003 6:33 am, edited 1 time in total.
Kalo mau kaya, buat apa sekolah?
hi i got TL too. but i thing my algo i good. can cycle be larger then long int ?
here is my algo to find cycle:
[cpp]
long int euklid (long int x,long int y) /* biggest common factor. (this function is good i think */
{
long int g=1,t;
while ((x%2==0) && (y%2==0))
{
x/=2;
y/=2;
g*=2;
}
while (x>0)
{
if (x%2==0)
x/=2;
else if (y%2==0)
y/=2;
else
{
t=abs(xy)/2;
if (x>=y)
x=t;
else
y=t;
}
}
return g*y;
}
long int findcycle() /* function finding cycle*/
{
int wsk,wart,cycle=1,c1,c2,podz;
wart=tab[tab[1]];
while (wart!=tab[1])
{
wart=tab[wart];
++cycle;
}
for (wsk=2;wsk<=wielkosc_tab;++wsk)
{
c1=1;
wart=tab[tab[wsk]];
while (wart!=tab[wsk])
{
wart=tab[wart];
++c1;
}
podz=euklid(cycle,c1);
cycle=(int)((cycle*c1)/podz);
}
return cycle;
}
[/cpp]
here is my algo to find cycle:
[cpp]
long int euklid (long int x,long int y) /* biggest common factor. (this function is good i think */
{
long int g=1,t;
while ((x%2==0) && (y%2==0))
{
x/=2;
y/=2;
g*=2;
}
while (x>0)
{
if (x%2==0)
x/=2;
else if (y%2==0)
y/=2;
else
{
t=abs(xy)/2;
if (x>=y)
x=t;
else
y=t;
}
}
return g*y;
}
long int findcycle() /* function finding cycle*/
{
int wsk,wart,cycle=1,c1,c2,podz;
wart=tab[tab[1]];
while (wart!=tab[1])
{
wart=tab[wart];
++cycle;
}
for (wsk=2;wsk<=wielkosc_tab;++wsk)
{
c1=1;
wart=tab[tab[wsk]];
while (wart!=tab[wsk])
{
wart=tab[wart];
++c1;
}
podz=euklid(cycle,c1);
cycle=(int)((cycle*c1)/podz);
}
return cycle;
}
[/cpp]
Rafał Sokołowski

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
I don't use GCD (Greatest Common Divisor) in this problem , and my code has 1011 bytes in all (with all comments and so on ... )
I don't think that cycle length will be larger than range of long int ...
I simple find cycles (in O(N^2) time) and find right positions for every character in input with the same timecomplexity ....
HINT: cycle length couldn't be longer than 200
Best regards
DM
I don't think that cycle length will be larger than range of long int ...
I simple find cycles (in O(N^2) time) and find right positions for every character in input with the same timecomplexity ....
HINT: cycle length couldn't be longer than 200
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 New poster
 Posts: 44
 Joined: Wed Aug 14, 2002 3:02 am
my prog got tLE too, my algorithm same as algorithm above, find the cycle first then mod the loop form input..
here's my code
[c]#include<stdio.h>
#include<string.h>
int same(char text[], int n)
{
int i;
for(i=0;i<n;i++)
if(text!=i+1) return 0;
return 1;
}
main()
{
int nkey, key[200], loop, lp, idx;
int i, j, len, ptr1, ptr2;
char text[2][210], temp[210];
#ifndef ONLINE_JUDGE
freopen("306.in","r",stdin);
freopen("306.out","w",stdout);
#endif
while(scanf("%d",&nkey)==1)
{
if(nkey==0) break;
for(i=0;i<nkey;i++) scanf("%d",&key);
/* check the min loop */
for(i=0;i<nkey;i++)
text[0]=i+1;
text[0]='\0';
ptr1=0;
ptr2=1;
for(i=0; ;i++)
{
for(j=0;j<nkey;j++)
text[ptr2][key[j]1]=text[ptr1][j];
ptr1^=ptr2^=ptr1^=ptr2;
if(same(text[ptr1], nkey)) break;
}
lp=i+1;
while(scanf("%d ",&loop)==1)
{
if(loop==0) break;
loop%=lp;
gets(temp);
len=strlen(temp);
for(i=len;i<nkey;i++) temp=' ';
temp='\0';
strcpy(text[0],temp);
text[0]='\0';
text[1]='\0';
ptr1=0;
ptr2=1;
for(i=0;i<loop;i++)
{
for(j=0;j<nkey;j++)
text[ptr2][key[j]1]=text[ptr1][j];
ptr1^=ptr2^=ptr1^=ptr2;
}
printf("%s\n",text[ptr1]);
}
}
return 0;
}[/c]
here's my code
[c]#include<stdio.h>
#include<string.h>
int same(char text[], int n)
{
int i;
for(i=0;i<n;i++)
if(text!=i+1) return 0;
return 1;
}
main()
{
int nkey, key[200], loop, lp, idx;
int i, j, len, ptr1, ptr2;
char text[2][210], temp[210];
#ifndef ONLINE_JUDGE
freopen("306.in","r",stdin);
freopen("306.out","w",stdout);
#endif
while(scanf("%d",&nkey)==1)
{
if(nkey==0) break;
for(i=0;i<nkey;i++) scanf("%d",&key);
/* check the min loop */
for(i=0;i<nkey;i++)
text[0]=i+1;
text[0]='\0';
ptr1=0;
ptr2=1;
for(i=0; ;i++)
{
for(j=0;j<nkey;j++)
text[ptr2][key[j]1]=text[ptr1][j];
ptr1^=ptr2^=ptr1^=ptr2;
if(same(text[ptr1], nkey)) break;
}
lp=i+1;
while(scanf("%d ",&loop)==1)
{
if(loop==0) break;
loop%=lp;
gets(temp);
len=strlen(temp);
for(i=len;i<nkey;i++) temp=' ';
temp='\0';
strcpy(text[0],temp);
text[0]='\0';
text[1]='\0';
ptr1=0;
ptr2=1;
for(i=0;i<loop;i++)
{
for(j=0;j<nkey;j++)
text[ptr2][key[j]1]=text[ptr1][j];
ptr1^=ptr2^=ptr1^=ptr2;
}
printf("%s\n",text[ptr1]);
}
}
return 0;
}[/c]
I've just got TLE on this problem 3rd time. Can you explain your algorithm? I don't see a way to do this problem fast enough without using GCD.Dominik Michniewski wrote:I don't use GCD (Greatest Common Divisor)
HINT: cycle length couldn't be longer than 200
If you are given a string : "a {48 spaces} b {49 spaces} ";
transformantions:
1>2 //// 50>51
2>3 //// 51>52
........ //// ...........
49>1 //// 99>50
The cycle length will be 49*50 = 2450 > 200;
It's possible to show that cycle length can be REALLY big for this problem.
PLEASE, anybody who solved this problem, let me know how to do it.
thx.
306 cipher rte!!!
i read at forum that the maximum cycle is 200, so could somebody explain me why does this get rte ? i think this could get wa or tle but not rte. i hope somebody can help.
Code: Select all
#include<cstdio>
#include<cstring>
int main()
{
int n,m,i,j;
int A[200];
char T[202][201];
for( ; ; )
{
scanf( "%d", &n );
if( n == 0 )
{
break;
}
for( i = 0; i < n; ++i )
{
scanf( "%d", &A[i] );
A[i];
}
for( ; ; )
{
scanf( "%d", &m);
if( m == 0 )
{
break;
}
scanf( " " );
gets( T[0] );
for( j = strlen( T[0] ); j < n; ++j )
{
T[0][j] = ' ';
}
T[0][n] = '\0';
for( i = 1; ; ++i )
{
for( j = 0; j < n; ++j )
{
T[i][ A[j] ] = T[i  1][j];
}
T[i][n] = '\0';
if( strcmp( T[0], T[i] ) == 0 )
{
break;
}
}
puts( T[m % i] );
}
putchar( '\n' );
}
}
 Ali Arman Tamal
 Learning poster
 Posts: 76
 Joined: Sat Jan 15, 2005 5:04 pm
 Location: Dhaka
 Contact:
for( i = 1; ; ++i )
{
for( j = 0; j < n; ++j )
{
T[ A[j] ] = T[j];
}
T[n] = '\0';
if( strcmp( T[0], T ) == 0 )
{
break;
}
}
The external cycle here ...
for( i = 1; ; ++i )
It may iterate many many times thus giving you a value for I which
is far beyond 201 ( you declare T as int[202][201] )
Don't you think so ?
Actually you try to simulate the process they describe
in the problem statement, but I am pretty sure this is
not the right approach for that problem.
You should try to find the numbers of steps S after which the
permutation of the N integers given ( in the second line of
each input test case ) goes/maps back to itself without
simulating the process ( applying A, then again A, then again A
and so on until you get a permutation equal to the first one ).
Reading some introduction to Group Theory
( even the first few pages ) should be enough.
That is my personal opinion of course about this
problem. I haven't tried it yet. I think it is not fully
about simulation.
{
for( j = 0; j < n; ++j )
{
T[ A[j] ] = T[j];
}
T[n] = '\0';
if( strcmp( T[0], T ) == 0 )
{
break;
}
}
The external cycle here ...
for( i = 1; ; ++i )
It may iterate many many times thus giving you a value for I which
is far beyond 201 ( you declare T as int[202][201] )
Don't you think so ?
Actually you try to simulate the process they describe
in the problem statement, but I am pretty sure this is
not the right approach for that problem.
You should try to find the numbers of steps S after which the
permutation of the N integers given ( in the second line of
each input test case ) goes/maps back to itself without
simulating the process ( applying A, then again A, then again A
and so on until you get a permutation equal to the first one ).
Reading some introduction to Group Theory
( even the first few pages ) should be enough.
That is my personal opinion of course about this
problem. I haven't tried it yet. I think it is not fully
about simulation.
306 RE help
i always get RE,if i enlarge the cycle[][],i get TLE,could someone tell me what's wrong with my code ?thanks.
Code: Select all
#include "stdafx.h"
#include <iostream>
using namespace std;
#include <cstring>
int main()
{
char cycle[205][205];
int ci;
int sq[205];
int n;
int sum;
int ts;
char f[205];
char tf[205];
int len;
int i,j;
int cnt;
while(cin>>n && n!=0)
{
for(i=0;i<n;i++)
cin>>sq[i];
while(cin>>sum && sum!=0)
{
cin.get();
cin.getline(f,205);
len=strlen(f);
if(len<n)
{
for(i=len;i<n;i++)
f[i]=' ';
f[i]='\0';
}
ci=0;
strcpy(cycle[ci++],f);
tf[n]='\0';
ts=sum;
cnt=0;
while(sum)
{
for(i=0;i<n;i++)
{
tf[sq[i]1]=f[i];
}
for(j=0;j<ci;j++)
{
if(!strcmp(tf,cycle[j]))
break;
}
if(j!=ci)
break;
strcpy(cycle[ci++],tf);
strcpy(f,tf);
cnt++;
}
if(sum>0)
{
cout<<cycle[j+(tscnt)%(cij)1]<<endl;
}
else
cout<<f<<endl;
}
cout<<endl;
}
return 0;
}