Tag: Implementaion

Manasa and Stones

Problem Statement

Manasa is out on a hike with friends. She finds a trail of stones with numbers on them. She starts following the trail and notices that two consecutive stones have a difference of either a or b. Legend has it that there is a treasure trove at the end of the trail and if Manasa can guess the value of the last stone, the treasure would be hers. Given that the number on the first stone was 0, find all the possible values for the number on the last stone.

Note: The numbers on the stones are in increasing order.

Input Format
The first line contains an integer T, i.e. the number of test cases. T test cases follow; each has 3 lines. The first line contains n (the number of stones). The second line contains a, and the third line contains b.

Output Format
Space-separated list of numbers which are the possible values of the last stone in increasing order.

Constraints
1≤T≤10
1≤n,a,b≤103

Sample Input

2
3 
1
2
4
10
100

Sample Output

2 3 4 
30 120 210 300

Explanation

All possible series for the first test case are given below:

  1. 0,1,2
  2. 0,1,3
  3. 0,2,3
  4. 0,2,4

Hence the answer 2 3 4.

Series with different number of final steps for second test case are the following:

  1. 0, 10, 20, 30
  2. 0, 10, 20, 120
  3. 0, 10, 110, 120
  4. 0, 10, 110, 210
  5. 0, 100, 110, 120
  6. 0, 100, 110, 210
  7. 0, 100, 200, 210
  8. 0, 100, 200, 300

Hence the answer 30 120 210 300.

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int t,n,a,b,i;
    cin>>t;
    while(t--)
    {
        cin>>n>>a>>b;
        if(b<a){
            int temp=a;
            a=b;
            b=temp;
            
        }
        //cout<<a<<" "<<b<<endl;
        if(a==b)
        {
            cout<<(n-1)*a<<endl;
            
        }
        else 
        {
            for(i=0;i<=n-1;i++)
            {
                cout<<(n-1-i)*a+(i)*b<<" ";
            
            }
        cout<<endl;
        }   
    }
    return 0;
}

Cavity Map

Problem Statement

You are given a square map of size n×n. Each cell of the map has a value denoting its depth. We will call a cell of the map a cavity if and only if this cell is not on the border of the map and each cell adjacent to it has strictly smaller depth. Two cells are adjacent if they have a common side (edge).

You need to find all the cavities on the map and depict them with the uppercase character X.

Input Format

The first line contains an integer, n, denoting the size of the map. Each of the following n lines contains n positive digits without spaces. Each digit (1-9) denotes the depth of the appropriate area.

Constraints
1≤n≤100

Output Format

Output n lines, denoting the resulting map. Each cavity should be replaced with character X.

Sample Input

4
1112
1912
1892
1234

Sample Output

1112
1X12
18X2
1234

Solution

  
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        String line;
        int n,i,j;
        n = sc.nextInt();
        char [][]CharArray = new char[n][n];
        for(i=0;i<n;i++){
            line = sc.next();
            CharArray[i]= line.toCharArray();
        }
        for(i=1;i<n-1;i++){
            for(j=1;j<n-1;j++){
                if(CharArray[i][j] > CharArray[i][j-1] & CharArray[i][j] > CharArray[i][j+1] & CharArray[i][j] > CharArray[i-1][j] & CharArray[i][j] > CharArray[i+1][j])
                    CharArray[i][j] = 'X';
            }
        }
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                System.out.print(CharArray[i][j]);
            }
            System.out.println();
        }
    }
}

Chocolate Feast

Problem Statement

Little Bob loves chocolate, and he goes to a store with $N in his pocket. The price of each chocolate is $C. The store offers a discount: for every M wrappers he gives to the store, he gets one chocolate for free. How many chocolates does Bob get to eat?

Input Format:
The first line contains the number of test cases, T.
T lines follow, each of which contains three integers, N, C, and M.

Output Format:
Print the total number of chocolates Bob eats.

Constraints:
1≤T≤1000
2≤N≤105
1≤C≤N
2≤M≤N

Sample input

3
10 2 5
12 4 4
6 2 2

Sample Output

6
3
5

Explanation
In the first case, he can buy 5 chocolates with $10 and exchange the 5 wrappers to get one more chocolate. Thus, the total number of chocolates is 6.

In the second case, he can buy 3 chocolates for $12. However, it takes 4 wrappers to get one more chocolate. He can’t avail the offer and hence the total number of chocolates remains 3.

In the third case, he can buy 3 chocolates for $6. Now he can exchange 2 of the 3 wrappers and get 1 additional piece of chocolate. Now he can use his 1 unused wrapper and the 1 wrapper of the new piece of chocolate to get one more piece of chocolate. So the total is 5.

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int t,n,c,m,total,brought;
    cin>>t;
    while(t--){
        cin>>n>>c>>m;
        int ans=0;
        // Computer answer
        brought = n/c;
        total = brought +(brought-1)/(m-1);
        cout<<total<<endl;
    }
    return 0;
}

Cut the sticks

Problem Statement

You are given N sticks, where the length of each stick is a positive integer. A cut operation is performed on the sticks such that all of them are reduced by the length of the smallest stick.

Suppose we have six sticks of the following lengths:

5 4 4 2 2 8

Then, in one cut operation we make a cut of length 2 from each of the six sticks. For the next cut operation four sticks are left (of non-zero length), whose lengths are the following:

3 2 2 6

The above step is repeated until no sticks are left.

Given the length of N sticks, print the number of sticks that are left before each subsequent cut operations.

Note: For each cut operation, you have to recalcuate the length of smallest sticks (excluding zero-length sticks).

Input Format
The first line contains a single integer N.
The next line contains N integers: a0, a1,…aN-1 separated by space, where ai represents the length of ith stick.

Output Format
For each operation, print the number of sticks that are cut, on separate lines.

Constraints
1 ≤ N ≤ 1000
1 ≤ ai ≤ 1000

Sample Input #00

6
5 4 4 2 2 8

Sample Output #00

6
4
2
1

Sample Input #01

8
1 2 3 4 3 3 2 1

Sample Output #01

8
6
4
1

Explanation

Sample Case #00 :

sticks-length        length-of-cut   sticks-cut
5 4 4 2 2 8             2               6
3 2 2 _ _ 6             2               4
1 _ _ _ _ 4             1               2
_ _ _ _ _ 3             3               1
_ _ _ _ _ _           DONE            DONE

Sample Case #01

sticks-length         length-of-cut   sticks-cut
1 2 3 4 3 3 2 1         1               8
_ 1 2 3 2 2 1 _         1               6
_ _ 1 2 1 1 _ _         1               4
_ _ _ 1 _ _ _ _         1               1
_ _ _ _ _ _ _ _       DONE            DONE

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define max 1000
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int l,i,j,num[max],min=1000,count=0;
    cin>>l;
    for(i=0;i<l;i++){
        cin>>num[i];
        if(num[i]<min)
            min=num[i];
    }
    sort(num,num+l);
    for(j=0;j<l;j++)
    {
        count=0;
        if(num[l-1]==0)
            break;
        for(i=0;i<l;i++){
            if(num[i]>=min){
                num[i]-=min;
                count++;
            }
        }
        cout<<count<<endl;
        min=1000;
        for(i=0;i<l;i++){
            if(num[i]!=0 & num[i]<min)
                min=num[i];
        }    
    }
    return 0;
}

Service Lane

Problem Statement

Calvin is driving his favorite vehicle on the 101 freeway. He notices that the check engine light of his vehicle is on, and he wants to service it immediately to avoid any risks. Luckily, a service lane runs parallel to the highway. The length of the service lane is N units. The service lane consists of N segments of equal length and different width.

Calvin can enter to and exit from any segment. Let’s call the entry segment as index i and the exit segment as index j. Assume that the exit segment lies after the entry segment (i≤j) and 0≤i. Calvin has to pass through all segments from index i to index j (both inclusive).

Paradise Highway

Calvin has three types of vehicles – bike, car, and truck – represented by 1, 2 and 3, respectively. These numbers also denote the width of the vehicle.

You are given an array width of length N, where width[k] represents the width of the kth segment of the service lane. It is guaranteed that while servicing he can pass through at most 1000 segments, including the entry and exit segments.

  • If width[k]=1, only the bike can pass through the kth segment.
  • If width[k]=2, the bike and the car can pass through the kth segment.
  • If width[k]=3, all three vehicles can pass through the kth segment.

Given the entry and exit point of Calvin’s vehicle in the service lane, output the type of the largest vehicle which can pass through the service lane (including the entry and exit segments).

Input Format

The first line of input contains two integers, N and T, where N denotes the length of the freeway and T the number of test cases. The next line has N space-separated integers which represent the width array.

T test cases follow. Each test case contains two integers, i and j, where i is the index of the segment through which Calvin enters the service lane and j is the index of the lane segment through which he exits.

Constraints
2≤N≤100000
1≤T≤1000
0≤i<j<N
2≤j−i+1≤min(N,1000)
1≤width[k]≤3,where 0≤k<N

Output Format

For each test case, print the number that represents the largest vehicle type that can pass through the service lane.

Note: Calvin has to pass through all segments from index i to index j (both inclusive).

Sample Input

8 5
2 3 1 2 3 2 3 3
0 3
4 6
6 7
3 5
0 7

Sample Output

1
2
3
2
1

Explanation

Below is the representation of the lane:

   |HIGHWAY|Lane|    ->    Width

0: |       |--|            2
1: |       |---|           3
2: |       |-|             1
3: |       |--|            2
4: |       |---|           3
5: |       |--|            2
6: |       |---|           3
7: |       |---|           3
  1. (0, 3): Because width[2] = 1, only the bike can pass through it.
  2. (4, 6): Here the largest allowed vehicle which can pass through the 5th segment is the car and for the 4th and 6th segment it’s the truck. Hence the largest vehicle allowed in these segments is a car.
  3. (6, 7): In this example, the vehicle enters at the 6th segment and exits at the 7th segment. Both segments allow even trucks to pass through them. Hence the answer is 3.
  4. (3, 5): width[3] = width[5] = 2. While the 4th segment allows the truck, the 3rd and 5th allow up to a car. So 2 will be the answer here.
  5. (0, 7): The bike is the only vehicle which can pass through the 2nd segment, which limits the strength of the whole lane to 1.

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define max 100000
using namespace std;

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int l,t,i,a,b,min,width[max];
    cin>>l>>t;
    for(i=0;i>width[i];
    while(t--){
        cin>>a>>b;
        min = 3;
        for(i=a;i<=b;i++)
        {
           if(width[i]<min)
               min=width[i];
        }
        cout<<min<<endl;
    }
    return 0;
}

Sherlock And Squares

Problem Statement

Watson gives two integers (A and B) to Sherlock and asks if he can count the number of square integers between A and B (both inclusive).

Note: A square integer is an integer which is the square of any integer. For example, 1, 4, 9, and 16 are some of the square integers as they are squares of 1, 2, 3, and 4, respectively.

Input Format
The first line contains T, the number of test cases. T test cases follow, each in a new line.
Each test case contains two space-separated integers denoting A and B.

Output Format
For each test case, print the required answer in a new line.

Constraints
1≤T≤100
1≤A≤B≤109

Sample Input

2
3 9
17 24

Sample output

2
0

Explanation
Test Case #00: In range [3,9], 4 and 9 are the two square numbers.
Test Case #01: In range [17,24], there are no square numbers.

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    long int t,n1,n2;
    cin>>t;
    while(t--)
        {
        cin>>n1>>n2;
        cout<<floor(sqrt(n2))-ceil(sqrt(n1))+1<<endl;
    }
    return 0;
}

Find Digits

Problem Statement

You are given an integer N. Find the digits in this number that exactly divide N (division that leaves 0 as remainder) and display their count. For N=24, there are 2 digits (2 & 4). Both of these digits exactly divide 24. So our answer is 2.

Note

  • If the same number is repeated twice at different positions, it should be counted twice, e.g., For N=122, 2 divides 122 exactly and occurs at ones’ and tens’ position. So for this case, our answer is 3.
  • Division by 0 is undefined.

Input Format

The first line contains T (the number of test cases), followed by T lines (each containing an integer N).

Constraints
1≤T≤15
0<N<1010

Output Format

For each test case, display the count of digits in N that exactly divide N in a separate line.

Sample Input

2
12
1012

Sample Output

2
3

Explanation

2 digits in the number 12 divide it exactly. The first digit, 1, divides it exactly in twelve parts, and the second digit, 2 divides 12 equally in six parts.

1 divides 1012 exactly (and it occurs twice), and 2 also divides it exactly. Division by 0 is undefined, therefore it will not be counted.

This challenge was part of Pragyan 12.

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    vector vec;
    int t,n,a,count;
    cin>>t;
    while(t--)
        {
        count = 0;
        cin>>n;
        a=n;
        while(n!=0)
            {
            int temp = n%10;
            vec.push_back(temp);
            n/=10;
            }
        reverse(vec.begin(),vec.end());
        for(std::vector::iterator it = vec.begin(); it != vec.end(); ++it)
            {
                if(*it==0);
                else if((a%*it)==0)
                   count++;
                   
            }
        cout<<count<<endl;
        vec.clear();
    }
    return 0;
}

Utopian Tree

Problem Statement

The Utopian Tree goes through 2 cycles of growth every year. The first growth cycle occurs during the spring, when it doubles in height. The second growth cycle occurs during the summer, when its height increases by 1 meter.

Now, a new Utopian Tree sapling is planted at the onset of spring. Its height is 1 meter. Can you find the height of the tree after N growth cycles?

Input Format

The first line contains an integer, T, the number of test cases.
T lines follow; each line contains an integer, N, that denotes the number of cycles for that test case.

Constraints
1≤T≤10
0≤N≤60

Output Format

For each test case, print the height of the Utopian Tree after N cycles. Each line thus has to contain a single integer, only.

Sample Input

3
0
1
4

Sample Output

1
2
7

Explanation

There are 3 test cases.

In the first case (N=0), the initial height (1) of the tree remains unchanged.

In the second case (when N = 1, i.e. after the 1st cycle), the tree doubles its height as it’s planted at the onset of spring.

In the third case (N=4), the tree first doubles its height (2), then grows a meter (3), then doubles again (6), before growing another meter; at the end of the 4th cycle, its height is 7 meters.

Solution

  
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args)throws Exception {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int i,j,yr;
        int t = Integer.parseInt(br.readLine());
        while(t!=0){
            yr=1;
            int n=  Integer.parseInt(br.readLine());
            for(i=1;i<=n;i++){
                if(i%2==0)
                    yr++;
                else yr= yr *2;
            }
            System.out.println(yr);
            t--;
        }

    }
}

Sherlock and The Beast

Problem Statement

Sherlock Holmes is getting paranoid about Professor Moriarty, his arch-enemy. All his efforts to subdue Moriarty have been in vain. These days Sherlock is working on a problem with Dr. Watson. Watson mentioned that the CIA has been facing weird problems with their supercomputer, ‘The Beast’, recently.

This afternoon, Sherlock received a note from Moriarty, saying that he has infected ‘The Beast’ with a virus. Moreover, the note had the number N printed on it. After doing some calculations, Sherlock figured out that the key to remove the virus is the largest Decent Number having N digits.

A Decent Number has the following properties:

  1. 3, 5, or both as its digits. No other digit is allowed.
  2. Number of times 3 appears is divisible by 5.
  3. Number of times 5 appears is divisible by 3.

Meanwhile, the counter to the destruction of ‘The Beast’ is running very fast. Can you save ‘The Beast’, and find the key before Sherlock?

Input Format
The 1st line will contain an integer T, the number of test cases. This is followed by T lines, each containing an integer N. i.e. the number of digits in the number.

Output Format
Largest Decent Number having N digits. If no such number exists, tell Sherlock that he is wrong and print −1.

Constraints
1≤T≤20
1≤N≤100000

Sample Input

4
1
3
5
11

Sample Output

-1
555
33333
55555533333

Explanation
For N=1, there is no such number.
For N=3, 555 is the only possible number.
For N=5, 33333 is the only possible number.
For N=11, 55555533333 and all permutations of these digits are valid numbers; among them, the given number is the largest one.

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int t,n;
    cin>>t;
    while(t--)
    {
       cin>>n;
       string ks;
       for(int j=n;j>=0;j--)
       {
           if(j%3==0 && (n-j)%5==0)
           {
            ks="";
            for(int i=0;i<j;i++)
                ks+='5';
            for(int i=0;i<n-j;i++)
                ks+='3';
            break;   
            }
       }
       if(ks=="")
               cout<<-1<<endl;
       else 
               cout<<ks<<endl;
    }
    return 0;
}

Angry Professor

Problem Statement

The professor is conducting a course on Discrete Mathematics to a class of N students. He is angry at the lack of their discipline, and he decides to cancel the class if there are fewer than K students present after the class starts.

Given the arrival time of each student, your task is to find out if the class gets cancelled or not.

Input Format

The first line of the input contains T, the number of test cases. Each test case contains two lines.
The first line of each test case contains two space-separated integers, N and K.
The next line contains N space-separated integers, a1,a2,…,aN, representing the arrival time of each student.

If the arrival time of a given student is a non-positive integer (ai≤0), then the student enters before the class starts. If the arrival time of a given student is a positive integer (ai>0), the student enters after the class has started.

Output Format

For each testcase, print “YES” (without quotes) if the class gets cancelled and “NO” (without quotes) otherwise.

Constraints

  • 1≤T≤10
  • 1≤N≤1000
  • 1≤K≤N
  • −100≤ai≤100,where i∈[1,N]

Note
If a student enters the class exactly when it starts (ai=0), the student is considered to have entered before the class has started.

Sample Input

2
4 3
-1 -3 4 2
4 2
0 -1 2 1

Sample Output

YES
NO

Explanation

For the first test case, K=3, i.e., the professor wants at least 3 students to be in class but there are only 2 who have arrived on time (−3 and −1), hence the class gets cancelled.

For the second test case, K=2, i.e, the professor wants at least 2 students to be in class and there are 2 who have arrived on time (0 and −1), hence the class does not get cancelled.

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int t,n,k,i,count;
    cin>>t;
    while(t--){
        count=0;
        cin>>n>>k;
        for(i = 0; i < n; i++)
            { 
            int temp;
            cin>>temp;
            if(temp <= 0)
                count++;
        }
        if(count >= k)
            cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}