Change position game

Time limit: 1 Sec Memory limit: 128 MB
Title description
N children (numbered 1 to N ) Is playing a game of changing positions. There are N stools (numbered from 1 to N, the leftmost is stool 1, and the rightmost is stool N). Each stool has a number (red number at the foot of the stool). Each number is different from each other and is a positive integer not exceeding N.
In each round of the game, each child will make the stool numbered by the number written on the stool, find the minimum number of rounds so that everyone can sit on the same stool as their own number;

Enter
Enter There are 2 rows.
The first line is an integer N (1≤N≤1000), which means the number of children participating in the game, and of course the number of stools.
Row 2 N different positive integers Ki (1≤Ki≤N, and 1≤i≤N), Ki represents the number at the foot of the i-th stool.

Output
There is 1 line of output.
Indicates the minimum number of rounds the children need to go through after changing positions and returning to the state of sitting on a stool before the game starts. Test number
It is guaranteed that the output result does not exceed 20000000.

Sample input
Copy sample data
3
1 2 3
Sample output
1

Prompt
Input yes 3 stools. The number at the foot of the No. 1 stool is 1, the number at the foot of the No. 2 stool is 2, and the number at the foot of the No. 3 stool is 3. After the first rotation, child 1 is still sitting on stool 1, child 2 is still sitting on stool 2, and child 3 is still sitting on stool 3. So after 1 round, it returns to the state before the game started.
For 60% of the data, 1≤N≤500, and the minimum number of rounds to be exchanged does not exceed 10,000.
For 100% data, 1≤N≤1000, and the minimum number of rounds that need to be exchanged does not exceed 20000000.

I use and check the collection to find how many collections there are. The number of elements in each collection is equivalent to the number of times the children in each collection need to exchange. Find the least common multiple of all collections.< /p>

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
 #include
#include
#include
using namespace std;
#define fore(i,a,b) for(int i= a;i<=b;i++)
#define forb(i,a,b) for(int i=a;i>=b;i--)
#define fir first
#define sec second
#define ABS(a) ((a)>0?(a):-(a))
typedef long long ll;
typedef long double ld;< br />const int MAXN=10005;
int nums[1005];
int fa[MAXN];
int all[MAXN];
int ans[MAXN];< br />int tot;

int get(int x){
 if(x==fa[x]) return x;
 return fa[x]=get( fa[x]);
}

void merge(int x,int y){
 fa[get(x)]=fa[get(y)];< br />}

long long gcd(long long x,long long y){
 if( y==0) return x;
 return gcd(y,x%y);
}

long long lcm(long long x,long long y){
 return x/gcd(x,y)*y;
}

int main(){
 int n;
 cin>>n;
 fore(i,1,n) fa[i]=i;
 fore(i,1,n) scanf("%d",&nums[i]),merge(nums[i],i );
 fore(i,1,n) all[get(i)]++;
 fore(i,1,n) if(all[i]) ans[++tot]= all[i];
 fore(i,2,tot) ans[i]=lcm(ans[i-1],ans[i]);
 cout< return 0;
}

[Topic] change position game

Change position game

Leave a Comment Cancel reply