Mock vita 1 (2018)

Triangles

Problem Description

Constraints

N<=50

-89 <= angle for any line <=90

Input Format

The first line of the input consists of a single integer, N.

The next line consists of a series of integers (positive, zero or negative), each corresponding to a separate line, and giving the angle that it makes with the x axis (measured in degrees and in anticlockwise direction).

Output

The output is a single integer giving the number of triangles formed by the lines

Test Case

TestCase 1
8,3
D,C,E,F,G,H
C,A,E
D,C,B,E

A,B

TestCase 2
8,3
D,C,E,F,G,H
C,A,B,E
D,B

N/A

Explanation

Example 1

Input

5

20,-20,0,50,50

Output

7

Explanation

There are 5 lines, with angles at 20,-20,0, 50 and 50 degrees with the x axis. The figure looks like this

There are 7 triangles, those formed by (L1,L2,L3),(L1,L2,L5), (L1,L2,L4), (L1,L3,L4), (L1,L3,L5), (L2,L3,L5), (L2,L3,L4). Hence the output is 7.

Example 2

Input

5

50,-50,50,-50,50

Output

0

Explanation

There are 5 lines with angles 50,-50,50,-50 and 50 degrees. The figure looks like this

As L1,L3 and L5 are parallel, and L2 and L4 are parallel, no triangles are formed by any set of three lines. Hence, the output is 0.

Program:-

#include<stdio.h>

int main()

{

    int n,a[100],i,k,j,count=0;

   char b[50];

     scanf("%d",&n);

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

      {

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

        if(i!=n-1)

           scanf("%c",&b);

      }

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

     {

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

         {

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

           {

               if(a[i]!=a[j]&&a[i]!=a[k]&&a[k]!=a[j])

                  count++;

             

           }

         }

     }

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

  return 0;

}

Finding Product

Problem Description

You are given a set of N positive integers and two small prime numbers P and Q (not necessarily distinct). You need to write a program to count the number of subsets of the set of N numbers whose product is divisible by PQ (the product of P and Q). Since the number K of such sets can be huge, output K modulo 1009 (the remainder when K is divided by 1009).

Constraints

N <= 300

P,Q <=50

The integers are <= 10000

Input Format

First line three comma separated integers N, P,Q

The next line contains N comma separated integers

Output

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

Test Case

TestCase 1
8,3
D,C,E,F,G,H
C,A,E
D,C,B,E

A,B

TestCase 2
8,3
D,C,E,F,G,H
C,A,B,E
D,B

N/A

Explanation

Example 1

Input

4,5,7

5,49,10,27

Output

6

Explanation

N is 4, P is 5, Q is 7. We need to find subsets of the numbers given so that the product of the elements is divisible by 35 (the product of 5 and 7). These subsets are (5,49),(5,49,10),(5,49,27),(5,49,10,27), (49,10),(49,10,27). There are 6 subsets, and the output is 6.

Example 2

Input

4,11,13

3,7,12,13

Output

0

Explanation

N is 4, P is 11, Q is 13. We need to find subsets of the numbers given so that the product of the elements is divisible by 143 (the product of 11 and 13).As none of the N numbers is divisible by 11 (a prime number), there are no subsets for which the product of the elements is divisible by 143. Hence the output is 0.

 

Program:

#include <stdio.h>
int t;
static int count=0;
void combinationUtil(int arr[], int n, int r,
                     int index, int data[], int i);
void printCombination(int arr[], int n, int r)
{
    int data[r];
    combinationUtil(arr, n, r, 0, data, 0);
}
void combinationUtil(int arr[], int n, int r, int index,
                     int data[], int i)
{
    long int s;
    if (index == r) {
        s=1;
        for (int j = 0; j < r; j++)
        {
            s=s*data[j];
        }
        if(s%t==0)
        count++;
        return;
    }
    if (i >= n)
        return;
    data[index] = arr[i];
    combinationUtil(arr, n, r, index + 1, data, i + 1);
    combinationUtil(arr, n, r, index, data, i + 1);
}
int main()
{
    int arr[100],n,p,q,i;
    char ch;
    scanf("%d",&n);
    scanf("%c",&ch);
    scanf("%d",&p);
    scanf("%c",&ch);
    scanf("%d",&q);
    for(i=0;i<n;i++)
    {
    scanf("%d",&arr[i]);
    if(i<n-1)
    scanf("%c",&ch);
    }
    t=p*q;
    for(i=2;i<=n;i++)
    printCombination(arr, n, i);
    printf("%d ",count);
    return 0;
}

Largest Integer

#include<stdio.h>
int main()
{
    int a[20][20],i,j,m,n,f=0,c=0,r,p,

k;
    char ch;
    scanf("%d%c%d",&m,&ch,&n);
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            scanf("%d",&a[i][j]);
            if(j<n-1)
            scanf("%c",&ch);
           
        }
    }
   
    while(f!=1)
    {
        j=n-1;c=-1;
     for(k=m-1;k>=0;k--)
     {
        if(a[k][j]>c)
        {
            c=a[k][j];
            r=k;
          
        }
       
     }
     for(p=j;p>0;p--)
     {
         a[r][p]=a[r][p-1];
     }
     a[r][p]=-1;
     if(c!=-1)
     printf("%d",c);
     else
     break;
    }
}