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

Date Time | Code Vita 2018 | round 1

Date Time

Problem Description

Arun and his sister Usha are challenging each other with some mathematical puzzles. Usha, the cleverer one, has come up with the idea of givingArun 12 distinct digits from 0 to 9, and have him form the largest date time in 2018 with them. Arun is a little nervous, and asks you to help him with a computer program.

Usha will give Arun 12 distinct digits. He needs to create a date time combination in the year 2018: the date in the MM/DD form (all four digits must be present), and the time in the format HH:MM (all four digits must be present). The date may be from 01/01 to 12/31 and the time may be from 00:00 to 23:59 (in the 24 hour format). The digits provided may be used only once in the answer that Arun gives.

If more than one date time combination may be formed, Arun needs to give the latest valid date time possible in the year 2018.

Constraints

Single digits (any of 0-9)

Input Format

A line consisting of a sequence of 12 (not necessarily distinct) single digits (any of 0-9) separated by commas. The sequence will be non-decreasing.

Output

The maximum possible valid date time in the year 2018. The output must be in the format

MM/DD HH:MM

If no date time can be constructed, the output should be 0

Explanation

Example1 :

Input

0,0,1,2,2,2,3,5,9,9,9,9

Output

12/30 22:59

Explanation

The 12 digits to be used by Arun are given.

The maximum valid date time using only the digits given, and with each digit used at most once is

12/30 22:59

This is the output.

Example 2

Input

3,3,3,3,3,3,3,3,3,3,3,3

Output

0

Explanation

As no digit less than 3 is present in the input, a valid month cannot be formed. Hence no valid Date time can be formed with the input digits.

Program

#include<stdio.h>
int isLeapYear(int y)
{
    if(y % 4 == 0)
    {
        if(y % 100 == 0)
        {
            if(y % 400 == 0)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
        else
        {
            return 1;
        }
    }
    
    return 0;
}

int is_valid_date_time(int date_time_arr[], int n)
{
    int month;
    if(n >= 2)
    {
        month = date_time_arr[0] * 10 + date_time_arr[1];
        if(!(month >= 1 && month <= 12))
        {
            return 0;
        }
    }
    
    if(n >= 4)
    {
        int days_in_each_month[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        days_in_each_month[1] += isLeapYear(2018);
        
        int day = date_time_arr[2] * 10 + date_time_arr[3];
        if(!(day >= 1 && day <= days_in_each_month[month - 1]))
        {
            return 0;
        }
    }
    
    if(n >= 6)
    {
        int hour = date_time_arr[4] * 10 + date_time_arr[5];
        if(!(hour >= 0 && hour <= 23))
        {
            return 0;
        }
    }
    
    if(n >= 8)
    {
        int min = date_time_arr[6] * 10 + date_time_arr[7];
        if(!(min >= 0 && min <= 59))
        {
            return 0;
        }
    }
    
    return 1;
}

int isFound = 0;
int max_time_in_2018[8] = {0};

int is_max(int inp_arr[])
{
    for(int i = 0; i < 8; i ++)
    {
        if(max_time_in_2018[i] == inp_arr[i])
        {
            continue;
        }
        else if(max_time_in_2018[i] >inp_arr[i])
        {
            return 0;
        }
        else 
        {
            return 1;
        }
    }
    
    return 0;
}

void time_computing(int inp_arr[], 
                    int date_time_arr[], int sel_cnt,
                    int used[])
{
    if(!is_valid_date_time(date_time_arr, sel_cnt)) 
    {
        return;
    }
    
    if(sel_cnt == 8)
    {
        if(is_valid_date_time(date_time_arr, sel_cnt))
        {
            isFound = 1;
            if(is_max(date_time_arr))
            {
                for(int i = 0; i < 8; i++)
                {
                    max_time_in_2018[i] = date_time_arr[i];
                }
            }
        }
        
        return;
    }
    
    // Select current item
    for(int i = 0; i< 12; i++)
    {
        if(used[i] == 1)
        {
            continue;
        }
        
        date_time_arr[sel_cnt] = inp_arr[i];
        used[i] = 1;
        time_computing(inp_arr,date_time_arr, sel_cnt + 1, used);
        used[i] = 0;
    }              
}

int main()
{
    int inp_arr[12], date_time_arr[8];
    scanf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d",
          &inp_arr[0],&inp_arr[1],&inp_arr[2],&inp_arr[3],
          &inp_arr[4],&inp_arr[5],&inp_arr[6],&inp_arr[7],
          &inp_arr[8],&inp_arr[9],&inp_arr[10],&inp_arr[11]);

    int used[12] = {0};
    
    time_computing(inp_arr, date_time_arr, 0, used);
    if(isFound == 1)
    {
        printf("%d%d/%d%d %d%d:%d%d",
         max_time_in_2018[0],max_time_in_2018[1],max_time_in_2018[2],max_time_in_2018[3],
         max_time_in_2018[4],max_time_in_2018[5],max_time_in_2018[6],max_time_in_2018[7]);
    }
    else
    {
        printf("0");
    }
    
    return 0;

}

Output

0,0,1,2,2,2,3,5,9,9,9,9

12/30 22:59

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

Your comments and feedback are welcomed!! If you have any doubts do contact me! Cheers!

Related Links: Parallelograms 2018