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

Prime Counters - Code Vita 2017 | Round 1

Prime Counters

Problem : 

Given a number N, let CP(N) denote the number of primes between 1 and N (inclusive of N). We call N a prime counter if CP(N) is a prime (N need not be a prime).  For example, CP(3) = 2, CP(4) = 2, CP(5) = 2, CP(7) = 4.

Input Format:  

An integer T, number of test cases  T lines each containing two positive integers L, R separated by space

Output Format:  

T lines containing the number of prime counters between L and R (both inclusive) in the ith test case (or NONE is no prime counter exists in that range)

Constraints:  

L ≤ R ≤ 106

Example 1 

 Input  1

  1 10

Output 
 4

Explanation 
CP(1) = 0, CP(2) = 1, CP(3) = 2, CP(4) = 2, CP(5) = 3, CP(6) = 3, CP(7) = 4= CP(8) = CP(9) = CP(10)   Hence there are 4 prime counters, 3, 4, 5, 6 in the range 1 to 10.

Example 2  

Input  2

 2 20  3 30 

Output  

  8
 8

Explanation  
Upto 10, we have 4 prime counters. Between 11 and 20 the prime counters are 11, 12, 17, 18 and hence the count is 8. Between 21 and 30, we have no prime counters.

Program:

#include <stdio.h>
int prime(int n)
{
    int k,j,p=0;
    for(k=2;k<=n;k++)
    {
        int c=0;
        for(j=1;j<=k;j++)
            if(k%j==0)
            c++;
       if(c==2)
        p++;
    }
    return p;
}
int main() 
{
int l,t,r,i,cp[1000],k,f,c=0,j,count;
scanf("%d",&t);
for(int z=1;z<=t;z++)
{
count=0;
scanf("%d %d",&l,&r);
for( i=l;i<=r;i++)
   cp[i]=prime(i);
for(j=l;j<=r;j++)
{
    c=0;
    for (k = 1;k<=cp[j]*cp[j];k++) 
    {
          if (cp[j] % k == 0) 
            c++;
        }
        if (c == 2) 
        count++;
}
printf("%d\n",count);
}
return 0;

}

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

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

Related Links:
Air in the balloon: https://codepiggy.blogspot.com/2020/03/air-in-balloons.html

Air in the Balloons - Code Vita 2017 | Round 1

 Air in the balloons

 Problem:

You have been given 'N' number of spherical Balloons of different radius when filled. You have to fill one balloon per day and the last balloon will be filled on Nth day. There is some rate of air reduction 'K' per day from each balloon. Fill the balloons in such an order so that the sum of the volume of all the balloons is maximum on the day when all the balloons are filled.

Input Format:  First Line is an integer N giving the number of balloons.  Second line gives space separated N positive real numbers with up to 1 decimal place giving the radii of the balloons.   Third line gives K, the rate of reduction in the volume of air as a percentage.

Output Format:  Maximum sum of volumes of all the balloons on the Nth day when all the balloons are filled. Take 3.14 as the value of PI and give the answer to two decimal places (truncated by ignoring all the decimals from third onwards). Note that the truncation should happen only after computing the volume of all the balloons on the final day to maximum precision.

Constraints: 

 Number of balloons <= 10  Radius of balloons <=200

Example 1  

Input  

5
 8 4 6 10 3  1 0

Output 

 7117.88

Explanation  
If we fill the balloons in the order 3, 4, 6, 8, 10, their volumes on the fifth day are respectively  7 4.165544  1 95.33312  7 32.4992 1929.216  4 186.666667  A nd their sum is 7117.880531. Truncating the value two decimal places, we obtain 7117.88

Example 2  

Input  

7
3 .5 9 4 6.6 7 11 9.1  1 2.5

Output  

12555.35

Explanation  
If we inflate the balloons in the order 3.5 4 6.6 7 9 9.1 11, their volumes on the seventh day would be respectively  8 0.56025567  1 37.4322396 705.5574848  9 62.0256771  2 336.74875  2 760.581763 5572.453333 The sum of these volumes is 12555.3595 and truncating to two decimal places, we obtain 12555.35

Program

#include <stdio.h>
double rate(double y,float m,int k)
{
    for(int i=k;i>=1;i--)
    {
     y=y-y*(m/100);
    }
return y;
}
int main() {
int n,i,j;
double v,b[1000],t,v1,sum=0;
float a[1000],x;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%f ",&a[i]);
scanf("%f ",&x);
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(a[i]>a[j])
{
   t=a[i];
   a[i]=a[j];
   a[j]=t;
}
for(i=0;i<n;i++)
{
v=0;
v=(4*3.14*a[i]*a[i]*a[i])/3;
b[i]=rate(v,x,n-(i+1));
}
for(i=0;i<n;i++)
sum=sum+b[i];
printf("%.2f ",sum);
return 0;

}

You can also run it online 
IDE: https://ide.geeksforgeeks.org/iNcfre3Isa

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

Related Links 
One Egg :https://codepiggy.blogspot.com/2019/05/one-egg-code-vita-2017-round-2.html