306 - Cipher
Moderator: Board moderators
-
- New poster
- Posts: 10
- Joined: Mon Mar 14, 2005 7:35 am
I really don't know why I got TLE on p306
program p306;
type arr=array[1..500] of longint;
var n,i,k,r,j,y:longint;
a:arr;
w,get:array[1..500] of char;
ch:char;
function lcm(a,b:longint):longint;
var t:longint;
begin
if b=0 then lcm:=a else lcm:=lcm(b,a mod b);
end;
function circle(w:arr):longint;
var flag:array[1..500] of boolean;
i,k1,ans,p,e:longint;
begin
fillchar(flag,sizeof(flag),false);
ans:=1;
repeat
k1:=0;
for i:=1 to n do
if not flag then begin
k1:=i;
break;
end;
if k1<>0 then begin
p:=k1;e:=0;flag[p]:=true;
while a[p]<>k1 do begin
inc(e);
p:=a[p];
flag[p]:=true;
end;
e:=e+1;
if ans>e then ans:=ans*e div lcm(ans,e) else ans:=ans*e div lcm(e,ans);
end;
until k1=0;
circle:=ans;
end;
begin
repeat
readln(n);
if n<>0 then begin
fillchar(a,sizeof(a),0);
for i:=1 to n do read(a);
y:=circle(a);
readln;
repeat
read(k);
if k<>0 then begin
read(ch);r:=0;
fillchar(w,sizeof(w),' ');
fillchar(get,sizeof(get),' ');
while not eoln do begin
read(ch);
inc(r);
w[r]:=ch;
end;
readln;
for i:=1 to k mod y do begin
for j:=1 to n do get[j]:=w[j];
for j:=1 to n do w[a[j]]:=get[j];
end;
for i:=1 to n do write(w);
writeln;
end;
until k=0;
readln;
end;
writeln;
until n=0;
end.
type arr=array[1..500] of longint;
var n,i,k,r,j,y:longint;
a:arr;
w,get:array[1..500] of char;
ch:char;
function lcm(a,b:longint):longint;
var t:longint;
begin
if b=0 then lcm:=a else lcm:=lcm(b,a mod b);
end;
function circle(w:arr):longint;
var flag:array[1..500] of boolean;
i,k1,ans,p,e:longint;
begin
fillchar(flag,sizeof(flag),false);
ans:=1;
repeat
k1:=0;
for i:=1 to n do
if not flag then begin
k1:=i;
break;
end;
if k1<>0 then begin
p:=k1;e:=0;flag[p]:=true;
while a[p]<>k1 do begin
inc(e);
p:=a[p];
flag[p]:=true;
end;
e:=e+1;
if ans>e then ans:=ans*e div lcm(ans,e) else ans:=ans*e div lcm(e,ans);
end;
until k1=0;
circle:=ans;
end;
begin
repeat
readln(n);
if n<>0 then begin
fillchar(a,sizeof(a),0);
for i:=1 to n do read(a);
y:=circle(a);
readln;
repeat
read(k);
if k<>0 then begin
read(ch);r:=0;
fillchar(w,sizeof(w),' ');
fillchar(get,sizeof(get),' ');
while not eoln do begin
read(ch);
inc(r);
w[r]:=ch;
end;
readln;
for i:=1 to k mod y do begin
for j:=1 to n do get[j]:=w[j];
for j:=1 to n do w[a[j]]:=get[j];
end;
for i:=1 to n do write(w);
writeln;
end;
until k=0;
readln;
end;
writeln;
until n=0;
end.
-
- Learning poster
- Posts: 91
- Joined: Tue May 31, 2005 2:01 pm
- Location: Russia
306 Cipher
Hi all!
I have got many times WA in this problem, but i don't know where is the mistake
Could you give me the test cases please and check up my results.
I have got many times WA in this problem, but i don't know where is the mistake
![:(](./images/smilies/icon_frown.gif)
Result:10
4 5 3 7 2 8 1 6 10 9
1 Hello Bob
2 Hello Bob
3 Hello Bob
4 Hello Bob
5 Hello Bob
6 Hello Bob
0
10
4 3 7 5 6 1 8 9 10 2
1 acm.uva.es
2 acm.uva.es
3 acm.uva.es
4 acm.uva.es
5 acm.uva.es
6 acm.uva.es
7 acm.uva.es
8 acm.uva.es
9 acm.uva.es
10 acm.uva.es
11 acm.uva.es
12 acm.uva.es
0
0
BolHeol b
lelBo Hob
HolleoB b
BelHo lob
lolBeoH b
Hello Bob
vsca.uma.e
uesva.cma.
..euvascma
aa..uvescm
vmaa.u.esc
ucmva.a.es
.scuvama.e
aes.uvcma.
v.ea.uscma
ua.va.escm
.mauva.esc
acm.uva.es
-
- Learning poster
- Posts: 91
- Joined: Tue May 31, 2005 2:01 pm
- Location: Russia
306 any efficient algo?
Hi!
Anyone knows how to speed-up this algo??
Here's my TLE code:
Regards!
Anyone knows how to speed-up this algo??
Here's my TLE code:
Code: Select all
#include <stdio.h>
#include <string.h>
class asd{
public:
char sign;
int value;
};
int main()
{
int n,k;
while(scanf("%d",&n)==1 && n)
{
int key[n];
char line[n];
asd szyfr[n];
for(int i = 0; i < n; i++)
scanf("%d",&key[i]);
while(scanf("%d",&k)==1 && k)
{
gets(line);int len = strlen(line);
if(strlen(line)<n)
{
for(int i = strlen(line); i < n; i++)
line[i] = ' ';
line[n] = '\0';
}
k %= len;
for(long x = 0; x < k; x++){
for(int i = 0; i < n; i++)
{
szyfr[i].sign = line[i];
szyfr[i].value = key[i];
}
for(int i = 1; i <= n; i++)
{
for(int j = 0; j < n; j++)
if(szyfr[j].value == i)
{
line[i-1] = szyfr[j].sign;
break;
}
}}
printf("%s\n",line);
line[0] = '\0';
}
printf("\n");
}
return 0;
}
Last edited by jaracz on Sun Aug 14, 2005 1:50 am, edited 2 times in total.
keep it real!
I am getting WA, could some one post some test cases.
The previous cases could be wrong as it was asked when the author was getting WA.
The previous cases could be wrong as it was asked when the author was getting WA.
Last edited by shamim on Fri Jul 15, 2005 11:54 am, edited 1 time in total.
Input:
My output:
Code: Select all
10
4 5 3 7 2 8 1 6 10 9
65540 CERC
1 ABCDEFGHIJ
2 ABCDEFGHIJ
3 ABCDEFGHIJ
4 ABCDEFGHIJ
5 ABCDEFGHIJ
6 ABCDEFGHIJ
7 ABCDEFGHIJ
8 ABCDEFGHIJ
9 ABCDEFGHIJ
10 ABCDEFGHIJ
11 ABCDEFGHIJ
12 ABCDEFGHIJ
13 ABCDEFGHIJ
14 ABCDEFGHIJ
15 ABCDEFGHIJ
0
0
Code: Select all
CER C
GECABHDFJI
DBCGEFAHIJ
AECDBHGFJI
GBCAEFDHIJ
DECGBHAFJI
ABCDEFGHIJ
GECABHDFJI
DBCGEFAHIJ
AECDBHGFJI
GBCAEFDHIJ
DECGBHAFJI
ABCDEFGHIJ
GECABHDFJI
DBCGEFAHIJ
AECDBHGFJI
Find the k-th permutation of the values first. The rest is simple.
![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
Ami ekhono shopno dekhi...
HomePage
HomePage
Actually, your suggestion gives TLE too
there is 2kn operations to get the final sequence and than print them
maybe you did it in better way??
I tried to speed up it several times but it must be k-permutaion, otherwise i get WA;(
anyway here is my code
Any other suggestions??
there is 2kn operations to get the final sequence and than print them
maybe you did it in better way??
I tried to speed up it several times but it must be k-permutaion, otherwise i get WA;(
anyway here is my code
Code: Select all
#include <stdio.h>
#include <string.h>
int main()
{
int n,k,counter = 0;char line[201];
while(scanf("%d",&n)==1 && n)
{
if(counter)printf("\n");
else counter = 1;
int key[n],seq[n],pom[n];
for(int i = 0; i < n; i++)scanf("%d",&key[i]);
while(scanf("%d ",&k)==1 && k)
{
gets(line);
if(strlen(line)<n)
{
for(int i = strlen(line); i < n; i++)
line[i] = ' ';
line[n] = '\0';
}
for(int i = 0; i < n; i++)pom[i] = i+1;
for(int c = 0; c < k; c++)
{
for(int i = 0; i < n; i++)seq[key[i]-1] = pom[i];
for(int i = 0; i < n; i++)pom[i] = seq[i];
}
for(int i = 0; i < n; i++)
printf("%c",line[seq[i]-1]);
printf("\n");
}
}
return 0;
}
keep it real!
Code: Select all
#include<cstdio>
#include<cstring>
int main()
{
int n,i,j,ciclo,t,k;
int T[210][210];
int A[210];
char S[210],S2[210];
char c;
for( i = 0; i < 210; ++i )
{
T[0][i] = i;
}
for( ; ; )
{
scanf( "%d", &n );
if( n == 0 )
{
break;
}
for( i = 0; i < n; ++i )
{
scanf( "%d", &A[i] );
}
/*problematic part
for( i = 1; ; ++i )
{
for( j = 0; j < n; ++j )
{
T[i][ A[j] - 1 ] = T[ i - 1 ][j];
}
for( j = 0; j < n; ++j )
{
if( T[i][j] != j )
{
break;
}
}
if( j == n )
{
break;
}
}*/
ciclo = i;
for( ; ; )
{
scanf( "%d%c", &k,&c );
if( k == 0 && c == '\n' )
{
break;
}
gets( S );
for( i = strlen( S ); i < n; ++i )
{
S[i] = ' ';
}
S[i] = '\0';
t = k % ciclo;
for( i = 0; i < n; ++i )
{
S2[i] = S[ T[t][i] ];
}
S2[i] = '\0';
puts( S2 );
}
putchar( '\n' );
}
}
RTE
Oh! This is irritating! RTE.
From other posts, I think I can take it for sure that the cycle is less than 200. But I'm getting RTE.
I use gets() to read input. So I consider the input is as exactly as in the description, ie. n is given in one line, the n integers in next line, k and a message in each line and a 0 in last line of each block. And there is no blank line. I think I should better post my code. Any help is greatly appreciated.
From other posts, I think I can take it for sure that the cycle is less than 200. But I'm getting RTE.
I use gets() to read input. So I consider the input is as exactly as in the description, ie. n is given in one line, the n integers in next line, k and a message in each line and a 0 in last line of each block. And there is no blank line. I think I should better post my code. Any help is greatly appreciated.
Code: Select all
Wrong method!
Last edited by mamun on Thu Feb 02, 2006 9:39 pm, edited 1 time in total.
Input:
Output:
Code: Select all
28
2 1 4 5 3 7 8 9 10 6 12 13 14 15 16 17 11 19 20 21 22 23 24 25 26 27 28 18
2006 microsoft.com
0
0
Code: Select all
miroc.soft com
I guess, by cycle of a permutation pi, you meant the smallest integer c>0, such that for all x, pi^c (x) = x. This number is usually called order of permutation, and in this problem it could be as large as 24067258815600.
There are several correct ways to solve this problem.
1. You can use the fact, that composition of permutations is associative, and binary exponentiation to get O(n log k) algorithm.
2. Write permutation in cyclic notation (if you don't know what it is, look in google.) If an element x is in a cycle of length c, then pi^k (x) = pi^{k mod c} (x). You can use this to compute pi^k in O(n) time.
For example, in the sample input, you are given a permutation pi=(1 4 7)(2 5)(3)(6 8)(9 10). How do you compute, say pi^1995 (5) from it? Element 5 is in a cycle of length 2, so after every 2 applications of pi it returns to its original place, so pi^1995 (5) = pi^(1995 mod 2) (5) = pi^1 (5) = 2. Hence, after 1995 encodings of CERC, the 5th character (a space) is put to position 2.
There are several correct ways to solve this problem.
1. You can use the fact, that composition of permutations is associative, and binary exponentiation to get O(n log k) algorithm.
2. Write permutation in cyclic notation (if you don't know what it is, look in google.) If an element x is in a cycle of length c, then pi^k (x) = pi^{k mod c} (x). You can use this to compute pi^k in O(n) time.
For example, in the sample input, you are given a permutation pi=(1 4 7)(2 5)(3)(6 8)(9 10). How do you compute, say pi^1995 (5) from it? Element 5 is in a cycle of length 2, so after every 2 applications of pi it returns to its original place, so pi^1995 (5) = pi^(1995 mod 2) (5) = pi^1 (5) = 2. Hence, after 1995 encodings of CERC, the 5th character (a space) is put to position 2.