The Hare and the Tortoise race

The Hare and the Tortoise race 

We all have heard the story of the hare and the tortoise. Last time the hare lost the race to the tortoise because of his laziness. Since then the hare has been requesting the tortoise for a rematch numerous times and the tortoise has been always declining his request. Just a couple of days before the tortoise has agreed for a rematch on the condition that he will decide the route of the match.

A race between a hare and the tortoise has to happen on the hills of the Nilgiri forest. Nilgiri forest has N hills numbered from 1 to N. Some of these hills are connected by paths called forest paths. Since these paths can have sharp corners which can lead to two animals bumping into each other if they come from opposite directions, so the forest government have made them one-way.

You  are given the time taken by the tortoise and the hare to move along a road for every forest road. Nilgiri has total M forest roads which are unidirectional.

The race can start from any hill but it should also end on the same hill. In other words, the path of the race should be cyclic.

The tortoise is now thinking of the route to take which involves the minimum number of roads and the tortoise is strictly faster than the hare on this route. If there are multiple such routes, the tortoise will choose the one which leads to the tortoise winning by the biggest margin (so that the hare doesn't dare to challenge the tortoise again in future).

It is guaranteed that such a route always exists.

Input Format

The first line contains 2 space-separated integers N and M representing the number of hills and the number of forest roads.

Next follows M lines. The ith line contains 4 integers ui, vi, ti, hi - ui and vi represents the starting and ending hills of a forest road respectively, ti and hi represents the time taken to cross this road by the tortoise and the hare respectively.

Constraints

2 <= N <= 4

2 <= M <= N(N-1)

1 <= ui, vi <= N  (ui != vi)

0 <= ti, hi <= 1000,000,000

Output Format

You have to print two space-separated integers - the first one is the minimum number of roads in the chosen path, and the second one is the biggest margin by which the tortoise can win the race on the chosen route.

Sample TestCase 1

Input

4 5
1 2 2 10
2 3 4 400
3 4 8 100
4 3 2 5
3 1 1 1000

Output

2 95

Explanation

You can see, the best route is 3 ---> 4 ----> 3 which consists of 2 roads only. The margin by which the tortoise wins = (100 + 5) - (8 + 2) = 105 - 10 = 95.

PROGRAM IN C:

#include<stdio.h>

int main()

{

     int arr[10][10],value[10],count=0,q=0,result=0,v=0,array1,array2;

scanf("%d",&array2); scanf("%d",&array1); for(int i=1;i<=array1;i++) { for(int j=1;j<=array2;j++) { scanf("%d",&arr[i][j]); } } for(int k=0;k<array1;k++) { if((arr[k][1]==arr[k+1][2])&&(arr[k][2]==arr[k+1][1])) { value[v]=k; count+=2; v++; } } for(int z=0;z<v;z++)

{ q=value[z]; result=result+(arr[q][4]+arr[q+1][4])-(arr[q][3]+arr[q+1][3]);

} printf("%d %d",count,result); return 0;

}

Kth largest factor of N

               kth largest factor of N 

A positive integer d is said to be a factor of another positive integer N if when N is divided by d, the remainder obtained is zero. For example, for number 12, there are 6 factors 1, 2, 3, 4, 6, 12. Every positive integer k has at least two factors, 1 and the number k itself. Given two positive integers N and k, write a program to print the kth largest factor of N. 

Input Format: The input is a comma-separated list of positive integer pairs (N, k)

Output Format: The kth highest factor of N. If N does not have k factors, the output should be 1.

Constraints: 1<N<10000000000. 1<k<600. You can assume that N will have no prime factors which are larger than 13.

Example 1

• Input: 12,3
• Output: 4

Explanation: N is 12, k is 3. The factors of 12 are (1,2,3,4,6,12). The highest factor is 12 and the third-largest factor is 4. The output must be 4

Example 2

• Input: 30,9
• Output: 1

Explanation: N is 30, k is 9. The factors of 30 are (1,2,3,5,6,10,15,30). There are only 8 factors. As k is more than the number of factors, the output is 1.

Program in C:

#include <stdio.h>
int main()
{
    int num,position,a[50],n=0;
    char ch;
    scanf("%d%c%d",&num,&ch,&position);
    for (int i=1;i<=num;i++)
       {
           if(num%i==0)
           {
               a[n]=i;
               n++;
           }
           
       }
       if(n>=position)
        printf("%d",a[position]);
       else
        printf("1");
    return 0;
}

counting rock samples

Counting Rock Samples

Juan Marquinho is a geologist and he needs to count rock samples in order to send it to a chemical laboratory. He has a problem: The laboratory only accepts rock samples by a range of its size in ppm (parts per million).

Juan Marquinho receives the rock samples one by one and he classifies the rock samples according to the range of the laboratory. This process is very hard because the number of rock samples may be in millions.

Juan Marquinho needs your help, your task is to develop a program to get the number of rocks in each of the ranges accepted by the laboratory.

Input Format:

An positive integer S (the number of rock samples) separated by a blank space, and a positive integer R (the number of ranges of the laboratory); A list of the sizes of S samples (in ppm), as positive integers separated by space R lines where the ith line containing two positive integers, space-separated, indicating the minimum size and maximum size respectively of the ith range.

Output Format:

R lines where the ith line containing a single non-negative integer indicating the number of the samples which lie in the ith range.

Constraints: 10 ≤ S ≤ 10000 1 ≤ R ≤ 1000000 1≤size of each sample (in ppm) ≤ 1000

Example 1

Input: 10 2

           345 604 321 433 704 470 808 718 517 811

           300 350

           400 700

Output: 2 4

Program in C:

#include <stdio.h>

int main()
{
     int m,n,a[50],b[10][1],c[10];               // m= number of rocks collected
   char ch;                                                 //n= number of labs
   scanf("%d%c%d",&m,&ch,&n);         //ch to read space
   printf("\n");                                          //a[50] = diff sizes of rocks collected
   for(int i=0;i<m;i++)                            //b[10][1]= to store min and max sizes of
      scanf("%d",&a[i]);                                           //labs in two dimentional array
    for (int j=0;j<n;j++)                           //c[10]= to sore the number of rocks that
                                                                                //are suitable to labs
scanf("%d%c%d",&b[j][0],&ch,&b[j][1]);         
      for (int k=0;k<n;k++)
          c[k]=0;
    for(int l=0;l<n;l++)
    {
        for (int x=0;x<m;x++)
        {
        if(a[x]>=b[l][0] && a[x]<=b[l][1])
            c[l]++;
        }
    }
   for (int y=0;y<n;y++)
         printf("%d ",c[y]);
    return 0;

}

pattern program 3

To Print The Following Pattern 

Program in C:

#include <stdio.h>

int main()
{
  int star = 0, space = 5;
  for (int i=1;i<=9;i++)
  {
  if(i<=5)
  {
  space--;
  star++;
  }
  else
  {
  space++;
  star--;
  }
  for (int j=1;j<=space;j++)
  printf(" ");
  for (int k=1;k<=star;k++)
  printf("*");
  for(int l=1;l<=8;l++)
  {
  if(i<=3 || i>6)
  printf(" ");
  else
  printf("*");
  }
  for (int m=1;m<=star;m++)
  printf("*");
  printf("\n");
  }
    return 0;
}

Program in JAVA:

public class Pattern {
  public static void main(String [] args)
  {
  int star = 0, space = 5;
  for (int i=1;i<=9;i++)
  {
  if(i<=5)
  {
  space--;
  star++;
  }
  else
  {
  space++;
  star--;
  }
  for (int j=1;j<=space;j++)
  System.out.print(" ");
  for (int k=1;k<=star;k++)
  System.out.print("*");
  for(int l=1;l<=8;l++)
  {
  if(i<=3 || i>6)
  System.out.print(" ");
  else
  System.out.print("*");
  }
  for (int m=1;m<=star;m++)
  System.out.print("*");
  System.out.println(" ");
  }
  }
}

pattern program 2

                                         Print The Following Pattern

Program in C:

#include <stdio.h>
int main()
{
    for(int i=1;i<=5;i++)
    {
      for(int j=5;j>i;j--)
          printf(" ");
      for(int l=1;l<2*i;l++)
          printf("*");
      printf("\n");   
    }

    return 0;
}

Program in JAVA:

public class Pattern
{
public static void main(String[] args)
{
   for(int i=1;i<=5;i++)
         {
              for(int j=5;j>i;j--)
                 System.out.print(" ");
              for(int l=1;l<2*i;l++)
                 System.out.print("*");
             System.out.println();   
           }
}
}

pattern program 1

Program to print the following pattern

Program in C:


#include <stdio.h>
int main()
{
    for(int i=1;i<=5;i++)
    {
      for(int j=1;j<=i;j++)
          printf("*");
      for(int k=(10-2*i);k>=1;k--)
          printf(" ");
      for(int l=1;l<=i;l++)
          printf("*");
      printf("\n");   
    }

    return 0;
}


Program in JAVA:

public class Pattern1
{
public static void main(String[] args)
{
    for(int i=1;i<=5;i++)
             {
                for(int j=1;j<=i;j++)
                      System.out.print("*");
               for(int k=(10-2*i);k>=1;k--)
                      System.out.print(" ");
               for(int l=1;l<=i;l++)
                     System.out.print("*");
             System.out.println(); 
           }
}
}

Converting the candies shape

Question from TechGig:

Converting the candies shape
An Annual learning competition was organised by a college in its various branches. Various students enrolled their name in the competition for their participation. Children are assigned a task on the spot about a puzzle which they have to solve in a very limited duration of time. They have been given a right isosceles triangle made of n > 0 lines containing 1, 3, . . . , 2n − 1 identical candies, respectively. They have to find out the minimum number of candies that will be needed to move these candies to create a square made up of all the candies given in the triangle. The student who solves this puzzle first will be awarded first and so on..

You have to return the minimum number of candies that is needed to move to convert the isosceles triangle into square made up of all the candies.


For example, assuming the number of lines of candies in the triangle is 3.

                                                                                         

Hence, the minimum number of candies that is needed to move to convert the isosceles triangle into square will be 2.

Input Format
Total number of lines of candies in the triangle.

Constraints
0 < N <=10000

Output Format
The minimum number of candies that are needed to move to convert the isosceles triangle into a square.

Sample TestCase 1
Input
3
Output
2

PROGRAM IN C:

#include<stdio.h>

int main(int argc, char *a[])

{

int i,number,result1,result2;

printf("Give the value of heigh");
scanf("%d",&number);

number=(number-1)/2;

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

result1=result1+i;

result2=result1*2;

printf("%d",result2);

return 0;  

}

PROGRAM IN JAVA:

import java.util.Scanner; public class Main

{

  public static void main(String [] args)    {     int number,result1=0,result2=0;     System.out.println("Give the value of height");     Scanner input = new Scanner(System.in); number = input.nextInt(); number=(number-1)/2; for(int i=1;i<=number;i++) result1=result1+i; result2=result1*2; System.out.println(result2); } }