ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1024. Permutations

xdex HINT if u use gcd in calculation of lcm [5] // Problem 1024. Permutations 28 Mar 2003 23:19
in pascal i used
  lcm := a*b div gcd(a,b);

i got WA

i changed line to
  lcm := trunc(1.0*a*b / gcd(a,b));
and got AC
i think i had arithmetic overflow
Xieli ZhaoFu Re: HINT if u use gcd in calculation of lcm [4] // Problem 1024. Permutations 29 Mar 2003 05:48
Post your code please ....

I dont understand well in pascal but i want to know your algorithms ...

Using my code , i got Time Out .... below is my code :

#include<stdio.h>

int p[1000],tmp[1000];
int n;

int go(int t,int i){
  int j,v;

  v=p[i];
  for(j=1;j<t;j++)
    v=p[v-1];
  return v;
}


int checkout(int t){
  int i;

  for(i=0;i<n;i++){
    tmp[i]=go(t,i);
    if(tmp[i] != i+1)
      return checkout(t+1);
  }
  return t;
}

int main(){
  int i;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&p[i]);
  printf("%d\n",checkout(1));
  return 0;
}
xdex re : hints of solving 1024 [3] // Problem 1024. Permutations 30 Mar 2003 01:07
let consider following :
(a**b means a*a*a*...*a (b times))

p ** k1(1) = 1
p ** k2(2) = 2
...
p ** kN(n) = n

i.e. order of #i is ki.

the order of entire permutation is a number that is devided by k1,
k2, .., kN. The lowest such number is lcm(k1, k2, ... , kN);

but

lcm(a, b) * gcd(a, b) = a * b;
that is lcm(a, b) = a * b / gcd(a, b);
Xieli ZhaoFu Re: re : hints of solving 1024 // Problem 1024. Permutations 31 Mar 2003 20:30
Yep , That is realy a GOOD
Xieli ZhaoFu Re: re : hints of solving 1024 [1] // Problem 1024. Permutations 31 Mar 2003 20:30
Yep , that is a good idea ...
Sol Re: re : hints of solving 1024 // Problem 1024. Permutations 6 Jun 2004 13:36
OKey!