Grooving Monkeys- Code Vita 8 | Pre-Qualifier Zonal Round

Grooving Monkeys

Problem Description

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 T, where T is the minimum number of seconds after which all the monkeys are in their
initial position.

Test Case

Example 1
Input
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.

Program:

#include <stdio.h>

int isequal(int x[],int m)
{
    int c1=0;
    for(int k=1;k<=m;k++)
    {
        if(x[k]==k)
        c1++;
    }
    return c1;
}
int main() {
int n,a[100],i,b[100],k,c[100],cnt,t;
scanf("%d",&t);
for(k=0;k<t;k++)
{
cnt=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=i;
}
z: for(i=1;i<=n;i++)
    c[a[i]]=b[i];
cnt++;
if(isequal(c,n)==n)
printf("%d\n",cnt);
else
{
    for(i=1;i<=n;i++)
    b[i]=c[i];
    goto z;
}
}
return 0;

}


You can also run it on an online IDE: https://ide.geeksforgeeks.org/IEgUyvHl1N

Your feedback are always welcome! If you have any doubt you can contact me or leave a comment!! Cheers!!!

Related Links:
Philaland Coin : https://codepiggy.blogspot.com/2020/03/philaland-coin-code-vita-8-pre.html

Philaland Coin - Code Vita 8 | Pre-Qualifier Zonal Round

Philaland Coin

Problem Description

The problem solvers have found a new Island for coding and named it as Philaland.

These smart people were given a task to make purchase of items at the Island easier by distributing various coins with different

value.

Manish has come up with a solution that if we make coins category starting from $1 till the maximum price of item present on

Island, then we can purchase any item easily. He added following example to prove his point.

Lets suppose the maximum price of an item is 5$ then we can make coins of {$1, $2, $3, $4, $5} to purchase any item ranging

from $1 till $5.

Now Manisha, being a keen observer suggested that we could actually minimize the number of coins required and gave following

distribution {$1, $2, $3}. According to him any item can be purchased one time ranging from $1 to $5. Everyone was impressed

with both of them.

Your task is to help Manisha come up with minimum number of denominations for any arbitrary max price in Philaland.

Constraints

1<=T<=100

1<=N<=5000

Input Format

First line contains an integer T denoting the number of test cases.

Next T lines contains an integer N denoting the maximum price of the item present on Philaland.

Output

For each test case print a single line denoting the minimum number of denominations of coins required.

Test Case

Example 1

Input

2

10

5

Output

4

3

Explanation

For test case 1, N=10.

According to Manish {$1, $2, $3,... $10} must be distributed.

But as per Manisha only {$1, $2, $3, $4} coins are enough to purchase any item ranging from $1 to $10. Hence minimum is 4.

Likewise denominations could also be {$1, $2, $3, $5}. Hence answer is still 4.

For test case 2, N=5.

According to Manish {$1, $2, $3, $4, $5} must be distributed.

But as per Manisha only {$1, $2, $3} coins are enough to purchase any item ranging from $1 to $5. Hence minimum is 3. Likewise

denominations could also be {$1, $2, $4}. Hence answer is still 3.

Program:

#include <stdio.h>

int sum(int x[],int l)

{

  int j,s1=0;

  for(j=1;j<=l;j++)

    s1=s1+x[j];

   return s1;

}

int main() {

int n,a[100],k=1,i,c,t,j;

scanf("%d",&t);

for(j=0;j<t;j++)

{

scanf("%d",&n);

a[1]=1;

c=0;

for(i=1;i<=n;i++)

{

    if(i>sum(a,k))

    {

        k++;

        a[i]=k;

    }

}

for(i=1;i<=k;i++)

{

    if(a[i]!=0)

    c++;

}

printf("%d\n",c);

for(i=1;i<=k;i++)

a[i]=0;

k=1;

}

return 0;

}

You can also run it on an online IDE: https://ide.geeksforgeeks.org/CqdZa41BMI

Your feedback are always welcome! If you have any doubt you can contact me or leave a comment!! Cheers!!!

Related Links:

Min Combinations: https://codepiggy.blogspot.com/2020/03/min-combinations-code-vita-8-pre.html

Min Combinations - Code Vita 8 | Pre-Qualifier Zonal Round

Min Combinations

Problem Description

Alexander The great, while roaming the stretch of Turkey, came across a wise man.
He asked the wise man, "Who is the greatest conqueror of all?". The wise man replied, "A person with great strength and
intelligence. Whosoever can solve my puzzle will go on to become the greatest!". The puzzle is as follows; Given two integers
'n1' and 'n2', select two integers 'a' and 'b', such as to solve the equation (n1 * a + n2 * b = x). But there is a catch, 'x' is the smallest
positive integer which satisfies the equation. Can you help Alexander become the greatest?

Constraints

1 <= T <= 1000
-10^7 <= a, b <= 10^7
0 <= n1, n2 <= 10^7

Input Format

The first line contains the number of Test cases T.
Next T lines contains two space-separated integers, n1 and n2.

Output

Print the value of x.

Test Case

Example 1

Input
1
34818 45632

Output
2

Explanation
Given n1 = 34818 and n2 = 45632, if we choose a = 3553 and b = -2711, we get
=> n1 * a + n2 * b = x
=> 34818 * 3553 + 45632 * (-2711)
=> 2
Note: No other value of a and b, within the range, will give smaller value than 2.

Program

#include <stdio.h> 

int gcd(int a, int b) 

{ 

if (b == 0) 

return a; 

return gcd(b, a % b); 

} 

int main() 

{ 

int a,b,t,i;

scanf("%d",&t);

for(i=0;i<t;i++)

{

scanf("%d %d",&a,&b);

printf("%d\n", gcd(a, b)); 

}

return 0; 

} 

You can also run it on an online IDE: https://ide.geeksforgeeks.org/OshEmrNKoJ

Your feedback are always welcome! If you have any doubt you can contact me or leave a comment!! Cheers!!!

Related Links:

Prime Counters: https://codepiggy.blogspot.com/2020/03/prime-counters-code-vita-round-1.html