TCS CodeVita

DEATH BATTLE:

In a crossover fantasy universe, Houin Kyoma is up in a battle against a powerful monster Nomu that can kill him in a single blow. However being a brilliant scientist Kyoma found a way to pause time for exactly M seconds. Each second, Kyoma attacks Nomu with certain power, which will reduce his health points by that exact power. Initially Nomu has H Health Points. Nomu dies when his Health Points reach 0, Normally Kyoma performs Normal Attack with power A. Besides from Kyoma’s brilliance, luck plays a major role in events of this universe. Kyomas Luck L is defined as probability of performing a super attack. A super attack increases power of Normal Attack by C. Given this information calculate and print the probability that Kyoma kills Nomu and survives. if Kyoma dies print "RIP"

Constraints

0<T<=50

1<=A, H, C, L1, L2<=1000

1<=M<=20

L1<=L2

Input Format

First line in Integer T denoting number of test cases.

Each test case consists of single line with space separated numbers A H L1 L2 M C where luck L is defined as L1/L2. Other numbers are, as described above.

Output Format

Print probability that Kyoma kills Nomu In form P1/P2 where P1<=P2 and gcd(P1,P2)=1. If impossible, print "RIP" without quotes.

Timeout

1

Explanation

Example 1

Input

2

10 33 7 10 3 2

10 999 7 10 3 2

Output

98/125

RIP

Click Here for Solution

SOLUTION IN C:

#include<stdio.h>

#include<math.h>

int gcd(int,int);

int probability(int,int);

int factorial(int);

int main(){

    int a,sa,h,l1,l2,m,c,i,j,g,num,den;

    scanf("%d %d %d %d %d %d",&a,&h,&l1,&l2,&m,&c);

    num=0;

    den=pow(l2,m);

    if(m*(a+c)<h){

        printf("RIP");

    }else{

        j=0;

        sa=m*a;

        while(sa<h){

            sa+=c;

            j++;

        }

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

            if(i==0)

                num+=(int)pow(l2-l1,m);

            else if(i==m)

                num+=pow(l1,i);

            else

                num+=(int)(pow(l1,i)*pow(l2-l1,m-i)*probability(m,i));

        }

        g=gcd(num,den);

        printf("%d/%d",num/g,den/g);

    }

    return 0;

}

int gcd(num,den){

    if(den==0)

        return num;

    else

        return gcd(den,num%den);

}

int probability(int m,int i){

    return factorial(m)/(factorial(m-i)*factorial(i));

}

int factorial(int n){

    if(n<=1)

        return 1;

    else

        return n*factorial(n-1);

}

HOLES AND BALLS:

A man is doing a something experiment with the device that he built newly. The structure of the device is shown as below diagram

B to E is a sloping surface with n holes, labeled H₁, H₂, H₃... H_n, on it. Holes are of different diameters & depths. The man is releasing m number of balls of different diameters from the point B one after the other. He wants to find the positions of each ball after the experiment.  The specialties of the device are as follow:

1.      A ball will fall into a hole, if and only if its diameter is less than or equal to the diameter of the hole. 

2.      A hole H_i will become Non-empty i.e Full, if i no. of balls fall into it. For ex hole labeled as H3 will become full if THREE balls fall into it.

3.      If a hole is full then no more balls can fall into that hole.

4.      A ball will reach the bottom point E from B, only if it is not falling into any 1 of the holes.

Please help him in finding the eventual position of the balls. If a ball is in hole Pi, then take its position as i. If a ball reached the bottom point E, then take its position as 0. 

Constraints

• 0 < N <= 50
• 0 < Diameter of holes <= 10^9
• 0 < M <= 1000
• 0 < M <= 1000

Input Format

Line 1: total number of holes, N

Line 2: N space separated integers denoting the diameters of N holes, from bottom to top

Line 3: total number of balls, M 

Line 4: M space separated integers denoting the diameters of balls in the order of release. 

Output 

Line 1: Positions of each ball in the order of ball release separated by space 

Explanation 

Input

3

21 3 6 

11 

20 15 5 7 10 4 2 1 3 6 8

Output

1 0 3 0 0 3 3 2 2 0 0

Click Here for Solution

SOLUTION IN C:

#include<stdio.h>

int main(){

    int h,hd[50],b,bd[50],ans[50],noofballs[3]={0},flag=0,i,j;

    scanf("%d",&h);

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

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

    scanf("%d",&b);

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

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

    for(i=0;i<b;i++){

        flag=0;

        for(j=h-1;j>=0;j--){

            if(bd[i]<=hd[j] && noofballs[j]!=j+1){

                flag=1;

                break;

            }

        }

        if(flag==1){

            noofballs[j]+=1;

            ans[i]=j+1;

        }

        else{

            ans[i]=0;

        }

    }

    for(i=0;i<b;i++){

        printf("%d",ans[i]);

        if(i<b-1)

            printf(" ");

    }

}

SIMILAR CHAR:

Tahir and Mamta are working in a project in TCS. Tahir being a problem solver came up with an interesting problem for his friend Mamta. Problem consists of a string of length N and contains only small case alphabets.

It will be followed by Q queries, in which each query will contain an integer P (1<=P<=N) denoting a position within the string.

Mamta’s task is to find the alphabet present at that location and determine the number of occurrence of same alphabet preceding the given location P. Mamta is busy with her office work. Therefore, she asked you to help her.

Constraints
1<=N<=500000
S consisting of small case alphabets
1<=Q<=10000
1<=P<=N
Sample Input:
9
abacsddaa
2
9
3
Sample Output:
3
1

Explanation

Here Q is equal to 2 

For P=9, character at Ninth location is "a". Number of occurrences of 'a' before P i.e., 9 is 3.

Similarly for P=3, Third character is 'a'. Number of occurrences of 'a' before P. i.e., 3 is 1.

Click Here for Solution

SOLUTION IN C:

#include<stdio.h>

#include<string.h>

int main() {

    char a[50];

    int i,j,n,noofq,q[50],c;

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

    if(n<1 || n>500000)

        return 0;

    gets(a);

    for(i=0;i<strlen(a)-1;i++)

        if(a[i]<'a' || a[i]>'z')

            return 0;

    scanf("\n%d",&noofq);

    if(noofq<1 || noofq>10000)

        return 0;

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

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

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

        if(q[i]<1 || q[i]>n)

            return 0;

    for(i=0;i<noofq-1;i++){

        for(j=i+1;j<noofq;j++){

            if(a[q[i]-1]==a[q[j]-1])

                q[j]--;

        }

    }

    for(i=0;i<noofq;i++){

        c=0;

        for(j=0;j<strlen(a);j++){

            if(j+1!=q[i] && a[j]==a[q[i]-1])

                c++;

        }

        if(c!=0)

            printf("%d",c);

        else

            printf("%d",c+1);

        if(i<noofq-1)

            printf("\n");

    }

}