Grooving Monkeys

 Grooving Monkeys

N monkeys are invited to a party where they start dancing. They dance in a circular formation, very similar to a Gujarati Garba or a Drum Circle. The dance requires the monkeys to constantly change positions after every 1 second.

The change of position is not random & you, in the audience, observe a pattern. Monkeys are very disciplined & follow a specific pattern while dancing.

Consider N = 6, and an array monkeys = {3,6,5,4,1,2}.

This array (1-indexed) is the dancing pattern. The value at monkeys[i], indicates the new of position of the monkey who is standing at the ith position.

Given N & the array monkeys[ ], find the time after which all monkeys are in the initial positions for the 1st time.

Constraints

  • 1<=t<=10 (test cases)
  • 1<=N<=10000 (Number of monkeys)

Input Format

  • First line contains single integer t, denoting the number of test cases.Each test case is as follows:
  • Integer N denoting the number of monkeys.
  • Next line contains N integer denoting the dancing pattern array, monkeys[].

Output

  • t lines
  • Each line must contain a single integer S, where S is the minimum number of seconds after which all the monkeys are in their initial position.

Example Input 1

1
6
3 6 5 4 1 2

Output

6

Explanation

  • Consider N = 6, and an array monkeys = {3,6,5,4,1,2}
  • Suppose monkeys are a,b,c,d,e,f & Initial position (at t = 0) -> a,b,c,d,e,f
  • At t = 1 -> e,f,a,d,c,b,  a will move to 3rd position, b will move to 6th position, c will move to 5th position, d will move to 4th position, e will move to 1st position and f will move to 2nd position.
  • Thus from a,b,c,d,e,f at t =0, we get e,f,a,d,c,b at t =1. Recursively applying same transpositions, we get following positions for different values of t.
  • At t = 2 -> c,b,e,d,a,f
  • At t = 3 -> a,f,c,d,e,b
  • At t = 4 -> e,b,a,d,c,f
  • At t = 5 -> c,f,e,d,a,b
  • At t = 6 -> a,b,c,d,e,f

Since at t = 6, we got the original position, therefore the answer is 6.



Grooving Monkeys

N monkeys are invited to a party where they start dancing. They dance in a circular formation, very similar to a Gujarati Garba or a Drum Circle. The dance requires the monkeys to constantly change positions after every 1 second.

The change of position is not random & you, in the audience, observe a pattern. Monkeys are very disciplined & follow a specific pattern while dancing.

Consider N = 6, and an array monkeys = {3,6,5,4,1,2}.

This array (1-indexed) is the dancing pattern. The value at monkeys[i], indicates the new of position of the monkey who is standing at the ith position.

Given N & the array monkeys[ ], find the time after which all monkeys are in the initial positions for the 1st time.

Constraints

  • 1<=t<=10 (test cases)
  • 1<=N<=10000 (Number of monkeys)

Input Format

  • First line contains single integer t, denoting the number of test cases.Each test case is as follows:
  • Integer N denoting the number of monkeys.
  • Next line contains N integer denoting the dancing pattern array, monkeys[].

Output

  • t lines
  • Each line must contain a single integer S, where S is the minimum number of seconds after which all the monkeys are in their initial position.

Example Input 1

1
6
3 6 5 4 1 2

Output

6

Explanation

  • Consider N = 6, and an array monkeys = {3,6,5,4,1,2}
  • Suppose monkeys are a,b,c,d,e,f & Initial position (at t = 0) -> a,b,c,d,e,f
  • At t = 1 -> e,f,a,d,c,b,  a will move to 3rd position, b will move to 6th position, c will move to 5th position, d will move to 4th position, e will move to 1st position and f will move to 2nd position.
  • Thus from a,b,c,d,e,f at t =0, we get e,f,a,d,c,b at t =1. Recursively applying same transpositions, we get following positions for different values of t.
  • At t = 2 -> c,b,e,d,a,f
  • At t = 3 -> a,f,c,d,e,b
  • At t = 4 -> e,b,a,d,c,f
  • At t = 5 -> c,f,e,d,a,b
  • At t = 6 -> a,b,c,d,e,f

Since at t = 6, we got the original position, therefore the answer is 6.



Solution:

from math import gcd

def lcm(x,y):

    return(int((x*y)/gcd(x,y)))

T=int(input())

while(T):

    T=T-1

    n=int(input())

    m=list(map(int,input().split()))

    t=1

    for p in range(n):

        c=0 

        while(m[p]!=0):

            h=p 

            p=m[p]-1

            m[h]=0 

            

            c+=1

        if(c!=0):

            t=lcm(t,c) 

    print(int(t))

Comments

Post a Comment

Popular posts from this blog

Efficient Janitor

  The janitor of a high school is insanely efficient. By the end of the day, all of the waster from the trash cans in the school has been shifted into plastic bags which can carry waster weighting between 1.01 pounds and 3.00 pounds. All of the plastic bags must be dumped into the trash cans outside the school. The janitor can carry at most 3.00 pounds at once. One trip is described as selecting a few bags which together don't weigh more than 3.00 pounds, dumping them in the outdoor trash can and returning to the school. The janitor wants to make minimum number of trips to the outdoor trash can. Given the number of plastic bags, n and the weights of each bag, determine the minimum number of trips if the janitor selects bags in the optimal way. For example, given  n=5 , plastic bags weighing weights  [1.01, 1.99, 2.5, 1.5, 1.01] , the janitor can carry all of the trash out in 3 trips:  [1.01+1.99, 2.5, 1.5+1.01] Constraints 1 <= n <= 1000 1.01 <= weight <=...
Read more

Right Arrow Pattern

Write a program to print the Right Arrow Pattern. Input Format: Take an input Integer which is from stdin. Output Format: print Right Arrow pattern Example Input: 5 Output: ***** **** *** ** * ** *** **** ***** SOLUTION: n=int(input()) for i in range(n):     for j in range(2*i):      #for spaces as each i th row has 2*i spaces         print(" ",end="")     for k in range(n-i):     #for stars as each i th row has n-i stars         print("*",end="")          print("")                     # half pattern is completed here for i in range(2,n+1):     #range started from 2 as the single star at middle is already                                         ...
Read more

X Pattern

  Write a program to take String if the length of String is odd print X pattern otherwise print INVALID. Input Format: Take a String as input from stdin. Output Format: print the desired Pattern or INVALID. Example Input: edyst Output: e t d s y d s e t SOLUTION: s=input() l=len(s) if(l%2 != 0): for i in range(0,l): j=l-i-1 for k in range(0,l): if(k==i or k==j): print(s[k],end="") else: print(end=" ") print("") else: print("INVALID")
Read more