Forest Fire problem

 source: https://prepinsta.com/tcs-codevita/java-program-for-forest-fire-problem/

Problem Statement:

Roco is an island near Africa which is very prone to forest fire. Forest fire is such that it destroys the complete forest. Not a single tree is left.This island has been cursed by God , and the curse is that whenever a tree catches fire, it passes the fire to all its adjacent tree in all 8 directions,North, South, East, West, North-East, North-West, South-East, and South-West.And it is given that the fire is spreading every minute in the given manner, i.e every tree is passing fire to its adjacent tree.Suppose that the forest layout is as follows where T denotes tree and W denotes water.

Your task is that given the location of the first tree that catches fire, determine how long would it take for the entire forest to be on fire. You may assume that the lay out of the forest is such that the whole forest will catch fire for sure and that there will be at least one tree in the forest

Input Format:

• First line contains two integers, M, N, space separated, giving the size of the forest in terms of the number of rows and columns respectively.
• The next line contains two integers X,Y, space separated, giving the coordinates of the first tree that catches the fire.
• The next M lines, where ith line containing N characters each of which is either T or W, giving the position of the Tree and Water in the  ith row of the forest.

Output Format:

Single integer indicating the number of minutes taken for the entire forest to catch fire

Constrains:

• 3 ≤ M ≤ 20
• 3 ≤ N ≤ 20

 

Sample Input 1:

3 3

1 2

W T T
T W W
W T T
Sample Output 1:

5

Explanation:
In the second minute,tree at (1,2) catches fire,in the third minute,the tree at (2,1) catches fire,fourth minute tree at (3,2) catches fire and in the fifth minute the last tree at (3,3) catches fire.

Sample Input 2:
6 6
1 6
W T T T T T
T W W W W W
W T T T T T
W W W W W T
T T T T T T
T W W W W W

Sample Output 2:

16

SOLUTION:

#include <stdio.h>

#include <stdbool.h>

int f[20][20];

int r[100],c[100],listCursor=0,len=0,m,n;

bool burnit(int i, int j, int v) {

    if(i<0 || j<0 || i>=m || j>=n)

        return false;

    if(f[i][j] == 0) {

        f[i][j] = v+1;

        r[len]=i;

        c[len]=j;

        len++;

        return true;

    }

    return false;

}

int bfs() {

    int i,j;

    while(listCursor < len){

        i=r[listCursor];

        j=c[listCursor];

        // printf("%d %d is fired\n", r[listCursor], c[listCursor]);

        listCursor++;

        burnit(i-1,j-1,f[i][j]);

        burnit(i-1,j,f[i][j]);

        burnit(i-1,j+1,f[i][j]);

        burnit(i,j+1,f[i][j]);

        burnit(i+1,j+1,f[i][j]);

        burnit(i+1,j,f[i][j]);

        burnit(i+1,j-1,f[i][j]);

        burnit(i,j-1,f[i][j]);

    }

    return f[i][j];

}

int main()

{

    char temp;

    int i,j,r1,c1;

    scanf("%d %d %d %d\n", &m, &n, &i, &j);

    for(r1=0;r1<m;r1++){

        for(c1=0;c1<n;c1++){

            scanf("%c", &temp);

            if(temp=='W')

                f[r1][c1] = 500;

            else

                f[r1][c1] = 0;

        }

        scanf("\n");

    }

    // check for correct input pattern

    // for(r1=0;r1<m;r1++){

    //     for(c1=0;c1<n;c1++){

    //         printf("%d ", f[r1][c1]);

    //     }

    //     printf("\n");

    // }

    r[0] =i-1;

    c[0] =j-1;

    len++;

    f[i-1][j-1] = 1;

    printf("total is: %d", bfs());

}

Maneuvering a Cave Problem

Problem Description 

The task is to count all the possible paths from top left to bottom right of a m x n matrix with the constraints that from each cell you can either move only to right or down. 

Input: 

First line consists of T test cases. First line of every test case consists of N and M, denoting the number of rows and number of columns respectively. 

Output: 

Single line output i.e count of all the possible paths from top left to bottom right of a m x n matrix.. 

Constraints: 

1<=T<=100 

1<=N<=100 

1<=M<=100 

SOLUTION (JAVA): 

import java.util.Scanner;
public class MyClass {
    static int count =0,m,n;
    public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      m= sc.nextInt();
      n= sc.nextInt();
      findWays(1,1);
      System.out.println(count);
    }
    
    static void findWays(int i, int j) {
        if(i>m || j>n)
            return;
        if(i==m && j==n){
            count++;
        }
        findWays(i, j+1);
        findWays(i+1,j);
    }
}

SOLUTION (C): 

#include <stdio.h>

int getPaths(int i, int j, int m, int n){
    if(i==m && j==n)
        return 1;
        
    if(i>m || j>n)
        return 0;
    
    return getPaths(i+1,j,m,n)+ getPaths(i,j+1,m,n);
}

int main()
{
    int m,n,i,j;
    scanf("%d %d", &m, &n);
    printf("total paths are : %d", getPaths(0,0,m-1,n-1));
    return 0;
}

MockVita 3 (2018)

Base 6

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 Sequence will be obtained using the following rule. The output is the number of inversions in the derived sequence.
Rule for forming derived sequence
An integer may be represented in base 6 notation. In base 6, 10305 is 1x64 + 3x62 + 5 =1409. Note that none of the digits in that representation will be more than 5.
The sum of digits in a base 6 representation is the sum of all the digits at the various positions in the representation. Thus for the number 1409, the representation is 10305, and the sum of digits is 1+0+3+0+5=9. The sum of digits may be done in the decimal system, and does not need to be in base 6
The derived sequence is the sum of the digits when the corresponding integer is represented in the base 6 form number will be expressed in base 6, and the derived sequence is the sum of the digits of the number in the base 6 representation.

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
2
Explanation
The number of integers is 5, as specified in the first line. The given sequence is 55, 53, 88, 27, 33.
The base 6 representation is 131, 125, 224, 43, 53 The derived sequence is 5,8,8,7,8 (corresponding to the sum of digits). The number of inversions in this is 2, namely (8, 7), (8, 7)
Example 2
Input

8

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

Output
11

Explanation
The base 6 representation of this is 320,33,115,144,200,55,30,242, and the derived sequence (sum of digits) is 5,6,7,9,2,10,3,8. The number of inversions is 11 (5,2), (5,3),(6,2) (6,3), (7,2), (7,3) (9,2),(9,3) (9,8),(10,3), (10,8)

Program:

#include<stdio.h>

#include<math.h>

int sum(int a)

{

    int s=0,r;

    while(a>0)

    {

       r=a%10;

       s+=r;

       a=a/10;

    }

    return s;

}

int main()

{

    int a[100],b[100],c[100],i,n,j,rem,s=0,cn=0;

    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++)

    {

        j=0;

        while(a[i]>0)

        {

            rem=a[i]%6;

            s=s+(rem*pow(10,j));

            a[i]=a[i]/6;

            j++;

        }

        b[i]=s;

        s=0;

    }

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

    {

    c[i]=sum(b[i]);

    }

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

    {

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

        {

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

                cn++;

        }

    }

    printf("%d",cn);

    return 0;

}

Digital Time

Problem Description

The objective is to form the maximum possible time in the HH:MM:SS format using any six of nine given single digits (not necessarily distinct)
Given a set of nine single (not necessarily distinct) digits, say 0, 0, 1, 3, 4, 6, 7, 8, 9, it is possible to form many distinct times in a 24 hour time format HH:MM:SS, such as 17:36:40 or 10:30:41 by using each of the digits only once. The objective is to find the maximum possible valid time (00:00:01 to 24:00:00) that can be formed using some six of the nine digits exactly once. In this case, it is 19:48:37.

Input Format

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

Output

The maximum possible time in a 24 hour clock (00:00:01 to 24:00:00) in a HH:MM:SS form that can be formed by using some six of the nine given digits (in any order) precisely once each. If no combination of any six digits will form a valid time, the output should be the word Impossible

Explanation

Example 1
Input
0,0,1,1,3,5,6,7,7
Output
17:57:36
The maximum valid time in a 24 hour clock that can be formed using some six of the 9 digits precisely once is 17:57:36
Example 2
Input
3,3,3,3,3,3,3,3,3
Output
Impossible
No set of six digits from the input may be used to form a valid time.

Program:

#include<stdio.h>

int main()

{

    int a[9],i,j,max,hr,mn,sc;

    char ch;

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

    {

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

        if(i<8)

        scanf("%c",&ch);

    }

    if(a[0]>2)

    {

        printf("Impossible");

        return 0;

    }

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

    {

        if(a[i]>2)

        {

            hr=a[i-1];

            for(j=i-1;j<8;j++)

                a[j]=a[j+1];

            break;

        }

    }

    if(i==9 && a[8]==0)

    {

        printf("Impossible");

        return 0;

    }

    else if(i==9)

        hr=a[8];

    if(hr==2)

    {

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

        {

            if(a[i]==4 && a[3]==0)

            {

                printf("24:00:00");

                return 0;

            }

           

            if(a[i]>3)

            {

            hr=(hr*10)+a[i-1];

            for(j=i-1;j<8;j++)

                a[j]=a[j+1];

            break;

            }

        }

        if(i==8)

            hr=(hr*10)+a[7];

    }

    else

        hr=(hr*10)+a[7];

    if(a[0]>5)

    {

        printf("Impossible");

        return 0;

    }

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

    {

        if(a[i]>5)

        {

            mn=a[i-1];

            for(j=i-1;j<6;j++)

                a[j]=a[j+1];

            break;

        }

    }

    if(i==7)

        mn=a[6];

    mn=(mn*10)+a[5];

    if(a[0]>5)

    {

        printf("Impossible");

        return 0;

    }

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

    {

        if(a[i]>5)

        {

            sc=a[i-1];

            for(j=i-1;j<4;j++)

                a[j]=a[j+1];

            break;

        }

    }

    if(i==5)

        sc=a[4];

    sc=(sc*10)+a[3];

    printf("%.2d:%.2d:%.2d",hr,mn,sc);

    return 0;

}

CODEVITA ROUND 2 (2013)

Isotope Fusion?

#include<stdio.h>

int main()
{
    int a[20],n,i,j,k,t,min=200,f=0;
    long int e=0;
    scanf("%d",&n);
    if(n<1 || n>10000)
    {
        printf("invalid input");
        return 0;
    }   
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]<1 || a[i]>198)
            f=1;
        if(min>a[i])
            min=a[i];
    }
    if(f==1)
    {
        printf("invalid input");
        return 0;
    }
    while(n!=1)
    {
        for(i=0;i<n;i++)
        {
            if(a[i]==min)
            {
                if(i==0)
                    j=1;
                else if(i==n-1)
                    j=n-2;
                else
                    j=(a[i+1] > a[i-1]) ? i+1 : i-1;
                e+=(a[i]*a[j]);
                t=(a[i]*a[j])%199;
                k=(i<j)? i : j;
                a[k++]=t;
                for(;k<n-1;k++)
                    a[k]=a[k+1];
                n--;
                i=n;
            }
        }
        min=a[0];
        for(i=1;i<n;i++)
            if(a[i]<min)
                min=a[i];
    }
    printf("%ld",e);
}

Brokerage?

 #include<stdio.h>

int main()
{
    float r,b,s,t,t1,t2,p,t3;
    int n;
    scanf("%f%f%f%d",&r,&b,&s,&n);
    if(r<0 || r>100 || b<0 || b>10000 || s<0 || s>10000 || n<0 || n>10000)
    {
        printf("invalid input");
        return 0;
    }
    p=(s-b)*n;
    t1=b*n;
    t1=(t1*r)/100;
    t3=t1*10.36/100;
    t1=t1+t3;
    t2=(s*n)*0.055/100;
    t2=t2+t3;
    t=t1+t2;
    t+=(b*n + s*n)*0.006/100;
    if(p>t)
    {
        printf("PROFIT\n%0.2f",p-t);
    }
    else
        printf("LOSS\n%0.2f",t-p);
    return 0;
}

Code vita Round 2(2014)

Cyclic Palindrome?

 #include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main()
{
    char s[100],d[100],b[100];
    int i,f[10]={1,1,1,1,1,1,1,1,1,1},j,n,k;
    scanf("%d",&n);
    for(k=0;k<=n;k++)
    {
    strcpy(s,"\0");
    gets(s);
    i=strlen(s);
    d[0]=s[i-1];
    d[1]='\0';
    s[i-1]='\0';
    strcat(d,s);
    for(j=0,i=i-1;i>=0;i--,j++)
    {
        b[j]=d[i];
    }
    b[j]='\0';
    f[k]=strcmp(d,b);
    }
    for(i=1;i<=n;i++)
    {
    if(f[i]==0)
    printf("1\n");
    else
    printf("-1\n");
    }
    return 0;
}

Codevita Round 1 (2013)

SEQUENCE?

#include<stdio.h>
int main()
{
    int a[100],i,j,k,max=0,n,maxi,f=0;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    maxi=0;
    for(i=0;i<n-1;i++)
    {
        f++;
        if(a[i] > a[i+1])
        {
            if(f>max)
            {
                max=f;
                maxi=i-f+1;
            }
            f=0;
        }
    }
    f++;
    if(f>max)
    {
        max=f;
        maxi=i-f+1;
    }
    for(i=maxi;i<maxi+max;i++)
    {
        printf("%d  ",a[i]);
    }
    return 0;
}

 

JUMBLE WITH NUMBERS? 

#include<stdio.h>

int john(int n)
{
    int i;
    for(i=0;i<=(n/2)+1;i++)
    {
        if((i*(i+1))/2 == n)
            return 1;
    }
    return 0;
}

int matthew(int n)
{
    int i;
    for(i=0;i<=(n/2)+1;i++)
    {
        if(i*(2*i-1) == n)
            return 1;
    }
    return 0;
}

int main()
{
    int a,i,t1,t2,c=0,c1;
    scanf("%d%d%d",&t1,&t2,&c1);
    if(t1<0 || t2<0 || c1<0 ||t1>10000 || t2>10000 || c1>10000)
    {
        printf("invalid input");
        return 0;
    }
    for(i=t1;i<=t2;i++)
    {
        a+=john(i) + matthew(i);
        if(a == 2)
        {
            c++;
        }
        a=0;
        if(c==c1)
        {
            printf("%d",i);
            break;
        }
    }
    if(c<c1)
        printf("no number is present at this index");
    return 0;
}

CodeVita Round 1 (2014)

Super Ascii String checker?

 #include<stdio.h>
#include<string.h>
int main()
{
    char str[100],ch,CH;
    int i,c[30]={0},A,a,j,k=0,flag=0,

s=0;
    scanf("%s",str);
    for(A=65,a=97,j=0;s<strlen(str);j++,A++,a++)
    {
        ch=a;
        CH=A;
    for(i=0;str[i]!='\0';i++)
    {
        if(CH==str[i]||ch==str[i])
        {
        c[j]++;
        flag=1;
        }
    }
    s+=c[j];
    if(flag==1)
    k++;
    flag=0;
    }
    for(i=0;i<j;i++)
    {
        if(c[i]!=i+1&&c[i]!=0)
        {
            flag=2;
            break;
        }
    }
    if(flag==2)
    printf("No");
    else
    printf("Yes");
return 0;
}

 

Stone Gamer? 

 

#include<stdio.h>
int main()
{
    int n,t=0,a[30],i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
  
    }
    for(i=0;i<n;i++)
    {
        t=0;
        while(a[i]>=4)
        {
            a[i]=a[i]-4;
            t++;
        }
        t=t+a[i];
        if(t%2==1)printf("Yes\n");
        else
        printf("No\n");
    }
    return 0;
}

 

Codevita Round 2 (2016)

The vita sum?

     #include <stdio.h>
    #include <conio.h>
    int main() {
        int n , r, ncr( int , int);
        int i=0,s=0;
           long double fact( int);
        scanf("%d%d",&n,&r);
        if(n>=r)
        {
        while( n>=i&&i<=r) {
            s+=ncr(n,i);
            i=i+2;
        }
        }
        printf("%d",s);
        return 0;
    }
    long double fact( int p) {
        long double facts = 1;
        int i;
        for ( i = 1; i<= p; i++)
          facts = facts * i;
        return( facts);
    }
    int ncr ( int n, int r) {
        return( fact( n) / (fact( r) * fact(n- r) ) ) ;
    }