Thursday, July 19, 2018

Mockvita 2 (2018)

Count Bits

Problem Description

Given a sequence of distinct numbers a1, a2, ….. an, an inversion occurs if there are indices i<j such that ai > aj .
For example, in the sequence 2 1 4 3 there are 2 inversions (2 1) and (4 3).
The input will be a main sequence of N positive integers. From this sequence, a Derived derived sequence will be obtained using the following rule. The output is the number of inversions in the derived sequence.
Rule for forming derived sequence
The derived sequence is formed by counting the number of 1s bits in the binary representation of the corresponding number in the input sequence.
Thus, if the input is 3,4,8, the binary representation of the numbers are 11,100 and 1000. The derived sequence is the number of 1sin the binary representation of the numbers in the input sequence, and is 2,1,1

Constraints

N <= 50
Integers in sequence <= 107

Input Format

The first line of the input will have a single integer, which will give N.
The next line will consist of a comma separated string of N integers, which is the main sequence

Output

The number of inversions in the derived sequence formed from the main sequence.







Explanation







Example 1 



Input



5



55, 53, 88, 27, 33



Output



8



Explanation



The number of integers is 5, as specified in the first line. The given sequence is 55, 53, 88, 27, 33. 



The
 binary representation is 110111, 110101, 1011000, 11011, 100001and 
100001 . The derived sequence is 5,4,3,4,2, 4,3,4,2 (corresponding to 
the number of 1s bits). The number of inversions in this is 8, namely 
(5,4),(5,3),(5,4),(5,2),(4,3),(4,2),(3,2),(4,2). Hence the output is 8.



Example 2 



Input



8



120,21,47,64,72,35,18,98



Output



15



Explanation



The
 number of integers is 8. The given sequence is 
120,21,47,64,72,35,18,98. The corresponding binary sequence is 
1111000,10101,101111,1000000,1001000,100011, 10010,1100010. The derived 
sequence (number of 1s) is 4,3,5,1,2,3,2,3. The number of inversions is 
15, namely 
(4,3),(4,1),(4,2),(4,3),(4,2),(4,3),(3,1),(3,2),(3,2),(5,1),(5,2),(5,3),
 (5,2), (5,3),(3,2). Hence the output is 15.







Program: 



#include <stdio.h>



#include <stdio.h>



    int  main()



    {

        int decimal_num,remainder,base=1,



binary=0,no_of_1s=0,a[100],b[100],n,i,c=0,j;

        char ch;

        scanf("%d",&n);

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

        {

        scanf("%d", &a[i]);

        if(i<n-1)

        scanf("%c",&ch);

        }

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

        {

        decimal_num = a[i];



        while (a[i] > 0)



        {



            remainder = a[i] % 2;

            if (remainder == 1)



            {



                no_of_1s++;



            }



            binary = binary + remainder * base;



            a[i] = a[i] / 2;



            base = base * 10;



        }

        b[i]=no_of_1s;

        base=1;

        binary=0;

        no_of_1s=0;

        }

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

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

            {

                if(b[i]>b[j])

                    c++;

            }

        printf("%d",c);   

      return 0;

    }









Finding Sum





Problem Description







You
 are given a set of N positive integers and another integer P, where P 
is a small prime. You need to write a program to count the number of 
subsets of size (cardinality) 3, the sum of whose elements is divisible 
by P. Since the number K of such sets can be huge, output K modulo 10007
 1009 (the remainder when K is divided by 1009)







Constraints







N <= 500



P<50



All integers <=1000







Input Format







First line two comma separated integers N, P



The next line contains N comma separated integers 







Output







One integer giving the number of subsets the sum of whose elements is divisible by P. Give result modulo 1009













Explanation







Example 1 



Input



4,5



5,10,15,20



Output



4



Explanation



Every
 non empty subset of the given numbers has sum of its elements a 
multiple of 5. Since there are 4 subsets of size 3, the output is 4.



Example 2 



Input



5,5



3,7,12,13,15



Output



4



Explanation



There
 are 4 subsets of size 3 with sum a multiple of 5: {3, 7, 15}, {12, 13, 
15}, {7, 13, 15}, {3, 12, 15}, Hence the output is 4.









Program:



#include <stdio.h>

int c=0;

void combo(int arr[], int n,int m, int r)

{

    int data[r];

    pairs(arr, data, 0, n-1, 0, r,m);

}

void pairs(int arr[], int data[], int start, int end,

                     int index, int r,int m)

{

    int s=0;

    if (index == r)

    {

        for (int j=0; j<r; j++)

        {

            s+=data[j];

        }

        if(s%m==0)

        c++;

        return;

    }

    for (int i=start; i<=end && end-i+1 >= r-index; i++)

    {

        data[index] = arr[i];

        pairs(arr, data, i+1, end, index+1, r,m);

    }

}

int main()

{

    int arr[100],n,i,m;

    char ch;

    scanf("%d",&n);

    scanf("%c",&ch);

    scanf("%d",&m);

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

    {

        scanf("%d",&arr[i]);

        if(i<n-1)

        scanf("%c",&ch);

    }

    combo(arr, n,m, 3);

    printf("%d",c);

    return 0;

}







Array Product





Problem Description







You
 are given a list of N integers and another positive integer K. Write a 
program to compute the number of ways in which the product P of the 
given N integers can be expressed as a product of K positive integers 
(not necessarily distinct). The order of the factors in the expression 
is not important. For example, 1 x 2 x 3 and 2 x 3 x 1 are not counted 
as different ways of expressing 6 as a product of three integers.







Constraints







The product of the N integers <= 10^9



Each of the N integers <=5000







Input Format







First line contains two space separated integers, N and K



The next line contains N space separated integers







Output







One
 line containing the number of ways in which the product of the N 
integers can be expressed as a product of K positive integers













Explanation







Example 1 



Input



2 4



2 3



Output



2



Explanation



The product of the given integers is 6. This can be expressed as a product of 4 integers in 2 ways: 1x1x1x6, 1x1x2x3



Example 2 



Input



2 3



4 16



Output



7



Explanation



The product is 64. This can be expressed as a product of three integers in the following ways:



1 x 1 x 64



1 x 2 x 32



1 x 4 x 16



1 x 8 x 8



2 x 2 x 16



2 x 4 x 8



4 x 4 x 4







Program: 



#include <stdio.h>

int c=0;

void result(int k,int i,int m)

{

    int j;

    if(k==0)

    {

        if(i<=m)

        {

            printf("%d ",m);

            c++;

        return;

        }

    }

    else

    {

        if(i>m)

            return ;

        for(j=i;j<=m;j++)

        {

            if(m%j == 0)

                result(k-1,j,m/j);

        }

    }

}

int main()

{

   int n,k,a[10],m=1,i,j;

   scanf("%d%d",&n,&k);

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

   {

       scanf("%d",&a[i]);

       m=m*a[i];

   }

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

   {

      /* for(j=i;j<m;j++)

       {

           if(i*j==m)

                printf("\n%d * %d",i,j);

       }*/

        if(m%i==0)

            result(k-2,i,m/i);

   }

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

   return 0;

}







Bug Crawl





Problem Description













A
 cube has its 6 faces numbered from 1-6 (three of its faces are shown in
 the diagram). There are six possible orientations on the cube 
(U,D,N,E,W,S) as shown in the diagram, of which only 4 are possible on 
any one face (for example, on face 1, N and S are impossible 
orientations)



An electronic remote control bug 
is on a face of a cube at some orientation. On your command it can crawl
 around the cube. The possible commands are F,B,L,R.



Command F : it moves to the adjacent face in the same direction it is facing



.Command B : it turns around by 180° and moves forward by one face.



Command L: it turns left and moves forward by one face



Command R: it turns right and moves forward by one face.



The faces 4,5,6 are opposite to faces 1,2,3 respectively. 



For
 example, if it has orientation U on face 1, on command L, it goes to 
face 5 and has orientation N, and from there on command F , it will move
 to face 4 and will have orientation E.



Given a 
sequence of commands, and the final position (face and orientation) of 
the bug (after executing the commands in the sequence), we need to 
determine the initial position (face and orientation) of the bug. 







Constraints







The length of the string of command letters <=50







Input Format







One
 string of 2 characters giving the face and orientation of the bug after
 it executes the instructions. The first character is a number between 1
 and 6, denoting the face, and the second character is the orientation 
(from the set {U, D, N, S, E, W}) of the bug after executing the 
commands



One string of command letters. This is a sequence of letters from the set of valid commands {F, B, L, R}







Output







One
 string of two characters denoting the position of the bug before it 
executes the instructions. The first character gives the face number 
(1,2,3,...,6) and the second giving the orientation (E,W,U,D,N,S ) the 
bug was facing before it executed the instructions













Explanation







Example 1 



Input



1U



FFF



Output



3N



Explanation



If
 the bug starts at 3N, it will move to 4D, 6S and 1U if a command F is 
given at each position. Hence, if it starts at 3N, after 3 consecutive F
 commands, it will be at 1U, which is the given final position. Hence 
the output is 3N.



Example 2 



Input



4W



LRB



Output



3E



Explanation



If
 the bug starts at 3E, after the L command, it goes to 4D, and after the
 R command, it goes to 2S. From there, on the B command, it goes to 4W, 
which is the end position. Hence the output is 3E.







Program: 

#include<stdio.h>

#include<string.h>



int main()

{

    char c1,c2,a[6],com[]={"WDSEUNWDSEUN"},s[51],b[10];

    int i=0,j,k,t,n;

    scanf("%c%c",&c1,&c2);

    scanf("%s",s);

    n=strlen(s);

    t=c1-48;

    for(i=n-1;i>=0;i--)

    {

        for(j=t-1,k=0;j<t+4;j++,k++)

            a[k]=com[j];

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

        {

            if(c2==a[j])

            {

                c2=com[t+1];

                if(s[i]=='B')

                    c2=com[t+4];

                t=t+j+1;

                if(t>6)

                    t-=6;

                if(s[i]=='R' || s[i]=='L')

                {

                    if(s[i]=='R')

                    {

                        switch(c2)

                        {

                            case 'U':   strcpy(b,"WSUEND"); break;

                            case 'D':   strcpy(b,"ENDWSU"); break;

                            case 'E':   strcpy(b,"UENDWS"); break;

                            case 'W':   strcpy(b,"DWSUEN"); break;

                            case 'S':   strcpy(b,"SDENUW"); break;

                            case 'N':   strcpy(b,"NUWSDE"); break;

                        }

                    }

                    else if(s[i]=='L')

                    {

                        switch(c2)

                        {

                            case 'D':   strcpy(b,"WSUEND"); break;

                            case 'U':   strcpy(b,"ENDWSU"); break;

                            case 'W':   strcpy(b,"UENDWS"); break;

                            case 'E':   strcpy(b,"DWSUEN"); break;

                            case 'N':   strcpy(b,"SDENUW"); break;

                            case 'S':   strcpy(b,"NUWSDE"); break;

                        }

                    }

                c2=b[t-1];

                }

                break;   

            }

        }

    }

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

    return 0;

}







Building Blocks





Problem Description







The
 Mathematics teacher wanted to introduce a new competition to the 
students to sharpen their skills in optimization. He drew a rectangular M
 ×N grid on the ground and filled it with some non-negative integers on 
each cell of the grid. The cell named (i,j) is at the intersection of i 
th row and j th column. He gave the following challenge to the students:



1. On each cell of the grid, you can pile any number of cube blocks.



2. Each layer must be rectangular (with no gaps) and rest p supported completely by the immediate below layer.



3. The number of blocks on each cell should not exceed the number written on the cell on the ground.



4. In each layer, the cell above (1,1) must be covered.



The challenge is to pile up the maximum number of blocks subject to the above conditions.



For example if the bottom grid was as follows:


 
 

 
   1 
   1 
   0 
  


 
   1 
   1 
   1 
  


 
   1 
   1 
   0 
  

 


the maximum number of blocks you can pile is 6 with one layer covering all the cells from (1,1) to (3,2).





Constraints







1 <= M,N <= 50



Maximum value in each cell is 50







Input Format







The
 first line will contain two comma separated integers M,N giving the 
size of the grid, where M is the number of rows and N is the number of 
columns. 



The next M lines will each contain comma separated N non-negative integers giving the numbers in the grid cells.







Output







One line containing the number of blocks that can be piled according to the rules.













Explanation







Example 1: 



Input:



3,4



5,4,9,3



4,3,5,6



2,2,1,1



Output:



32



Explanation:



One example of the maximum number of blocks that could be piled on the grid is shown below:


 
 

 
   5 
   4 
   4 
   3 
  


 
   3 
   3 
   3 
   3 
  


 
   1 
   1 
   1 
   1 
  

 




The total number of blocks is 32. Hence the output is 32.



Example 2: 



Input



4,7



27,26,28,14,15,38,0



38,40,35,2,20,43,39



18,48,43,2,47,18,26



38,2,29,23,14,31,32



Output



242



Explanation



The number of rows is 4. The number of columns is 7. The values in the cells of the grid are


 
 

 
   27 
   26 
   28 
   14 
   15 
   38 
   0 
  


 
   38 
   40 
   35 
   2 
   20 
   43 
   39 
  


 
   18 
   48 
   43 
   2 
   47 
   18 
   26 
  


 
   38 
   2 
   29 
   23 
   14 
   31 
   32 
  

 




One possible maximal placing of the blocks is


 
 

 
   27 
   26 
   26 
   2 
   2 
   2 
   0 
  


 
   27 
   26 
   26 
   2 
   2 
   2 
   0 
  


 
   18 
   18 
   18 
   2 
   2 
   2 
   0 
  


 
   2 
   2 
   2 
   2 
   2 
   2 
   0 
  

 




As there are 242 blocks in this maximal placing, the output is 242.







Program: 



#include<stdio.h>

int a[10][10];

void del(int i,int j,int s,int f,int r,int c)

{

    int k,l;

    if(s==0)

    {

        for(k=0;k<r;k++)

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

                a[k][l]=f-1;

    }   

    else

    {

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

            for(l=0;l<c;l++)

                a[k][l]=f-1;

    }

}

int rsum(int i,int j,int r,int c)

{

    int k,l,s=0;

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

        for(l=0;l<c;l++)

            s+=a[k][l];

    return s;       

}

int csum(int i,int j,int r,int c)

{

    int k,l,s=0;

    for(k=0;k<r;k++)

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

            s+=a[k][l];

    return s;

}

int main()

{

    int i,j,k,r,c,max=0,r1,c1,s,t1,t2,sum=0;

    char ch;

    scanf("%d%c%d",&r,&ch,&c);

    r1=r;

    c1=c;

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

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

        {

            scanf("%d",&a[i][j]);

            if(j<c-1)

            scanf("%c",&ch);

            if(a[i][j] > max)

                max=a[i][j];

        }

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

    {

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

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

            {

                if(a[i][j] < k)

                {

                    t1=rsum(i,j,r1,c1);

                    t2=csum(i,j,r1,c1);

                    s=(t1 > t2) ? 1 : 0;

                    del(i,j,s,k,r1,c1);

                    if(s==1)

                        r1=i;

                    else

                        c1=j;

                }

            }

    }

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

    {

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

        sum+=a[i][j];    

    }

    printf("%d",sum);

    return 0;

}






























on







































4 comments:































        

      









Subscribe to:
Post Comments (Atom)