## 306 - Cipher

Moderator: Board moderators

DemonCris
New poster
Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan
I always get TLE ><

my alg. is as follows:
1. get the period of the string-change.
if the string is as the same as original
one after some changing order.
finally, I get a cycle to reduce the computing time. But I still get TLE ><

2. after the failure of the first alg., I get another alg. to solve this problem:
first, I get each cycle of each character when that appear twice. finally, I still get TLE ><...

I have enough. I hate this problem. Can someone tell me a good alg. ? Thank you very much^^

pochmann
New poster
Posts: 28
Joined: Sat Jan 26, 2002 2:00 am
Contact:
No need to hate it. In fact, I think it's a very beautiful one.

In your second algorithm: When you've found the cycle of the first position, what do you do with the other positions in the cycle? Do you search their cycles again or use the information already obtained?

Stefan

DemonCris
New poster
Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan
Thank you very much ^^

After getting one cycle, I search again^^|||

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

### 306 What that means???

Code: Select all

``````Your program has died with signal 8 (SIGFPE). Meaning:

Floating point exception

Before crash, it ran during 0.002 seconds.
``````
Can somebody what that means? My code is:

[c]
#include <stdio.h>
#include <string.h>

#define max 201

main()
{ int n,i,j,a;
int x[max][max];
char s[max],s1[max];
scanf("%d",&n);

while (n)
{ for (i=1;i<=n;i++)
{ x=i;
scanf("%d",&x);
}
for (i=1;i<=n;i++)
{ j=1;
while (x[j]!=x)
{ a=x[j];
j++;
x[j]=x[a];
}
x=j;
}
scanf("%d ",&a);
while (a)
{ gets(s);
for (i=strlen(s);i<=n;i++)
{ s=' ';
s[i+1]='\0';
}
strcpy(s1,s);
for (i=0;i<strlen(s);i++)
if (x[i+1]!=1)
{ j=a%x[i+1];
if (j!=0)
{ j=x[i+1][j]-1;
s1[j]=s;
}
}
printf("%s\n",s1);
scanf("%d ",&a);
}
scanf("%d",&n);
}
}
[/c]

Thanx

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
j=a%x[i+1];

this would obviously fail if x[i+1] is zero.

SilVer DirectXer
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

### ACM 306

[c]
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void convert(int k,int times,char []);
int num,times,k,i,a,j;
char string,dummy;
void main(void)
{

do{

scanf("%d",&times);
if (times==0)
{
feof(stdin);
break;
}
for (i=0;i<times;i++)
{
scanf("%d",num+i);
}
do
{
scanf("%d",&k);
if (k==0)
{
printf("\n");
break;
}
scanf("%c",&dummy);
gets(string);
a=strlen(string);
if (a<times)
{
for (j=a;j<=times-1;j++)
string[j]=' ';
}
string[times]='\0';

convert(k,times,string);
}while(1);

}while(1);

}

void convert(int k,int times,char string[])
{
int i,j;
char result;
for (i=0;i<k;i++)
{
for (j=0;j<times;j++)
{
result[num[j]-1]=string[j];
}
strncpy(string,result,times);
}
printf("%s\n",string);
}
[/c]
I got TLE,is that really my logic is running too long or....something other make my stopped at somewhere?
Thanks!

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
I didn't run through your code closely, but I guess it has to do with your algorithm. Note that k can be as big as possible (ignoring integer overflow) and yet your program should run in time... jasemty
New poster
Posts: 2
Joined: Sat Jan 11, 2003 11:07 am
Location: Hong Kong

### How large can K be?

junjieliang wrote:I didn't run through your code closely, but I guess it has to do with your algorithm. Note that k can be as big as possible (ignoring integer overflow) and yet your program should run in time... Will k be as large as the type "long"?
Thanks. SilVer DirectXer
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

### 306TLE

[cpp]
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int convert(int k,int times,char []);
int num,times,i,a,j,index;
long k;
char string,dummy,ostring;

int main(void)
{
int repeat;
char temp;
do{
scanf("%d",&times);
if (times==0)
return 0;
for (i=0;i<times;i++)
{
scanf("%d",num+i);
}

do
{
for (i=0;i<times;i++)
num--;
scanf("%d",&k);
if (k==0)
{
printf("\n");
break;
}
scanf("%c",&dummy);
gets(string);
a=strlen(string);
if (a<times)
{
for (j=a;j<=times-1;j++)
string[j]=' ';
}
string[times]='\0';
strncpy(ostring,string,strlen(string));
repeat=convert(k,times,string);
for (i=0;i<times;i++)
temp=string[index];
temp[strlen(string)]='\0';
printf("%s\n",temp);
for (i=0;i<times;i++)
num++;
}while(1);

}while(1);

}

int convert(int k,int times,char string[])
{
int i,j,KO=1;
int result;
for (i=0;i<times;i++)
{
index=i;
}
for (i=0;i<k;i++)
{
for (j=0;j<times;j++)
{
result[num[j]]=index[j];
}
for (j=0;j<times;j++)
{
index[j]=result[j];
}

}
return 0;
}
[/cpp]
Help....

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

### 306 - Cipher

always get TLE for this problem. is there any good method?
my algo is :
1. simulate it until find cycle. at each step i store the result in a big array.
2. after find cycle. i use mod, so that not to search again.
but TLE.
i'm pretty sure that there must be another way, since many solve this < 1 sec, even 1 solved this prob in 0:00 !

with love & light,

titid
Kalo mau kaya, buat apa sekolah?

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
When you do by this method, a cycle can repeat after n! permutations, which is too big. A hint, think of how you can make use of lcm...

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I used the same algorithm as you, titd_gede, and got Acc in 0.301 sec ...
Maybe you have some mistakes in your code?

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)

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
i do not know. but i think jungjeliang was right. that a cycle can repeat after n!. here is my main code :
[c]
strcpy (allresult, data);
for (i = 0; i < k; i++) {
for (j = 0; j < n; j++)
temp[key[j]-1] = allresult[j];
temp[n] = '\x0';
strcpy (allresult[i+1], temp);
if (!strcmp (temp, allresult))
break;
}
[/c]
i store all in variable allresult, and it will stop after k reached or cycle found, which come first.

with love & light,

titid
Kalo mau kaya, buat apa sekolah?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Maybe you do something like this: look for a cycle for every data in block?
I do it only once at beginning of block ... maybe it's your mistake ?

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)

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
yes, i look for cycle for each data.
now i change it, but now i got Memory limit Exceeded (for big array) since if i reduce size got Run time Error (sigsev)
must look for another way.

with love & light,

titid
Kalo mau kaya, buat apa sekolah?