August, 2015 | Ajinkya Wavare

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

Sample Output

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

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: a₀, a₁,…a_N-1 separated by space, where a_i represents the length of i^th stick.

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

Constraints
1 ≤ N ≤ 1000
1 ≤ a_i ≤ 1000

Sample Input #00

6
5 4 4 2 2 8

Sample Output #00

Sample Input #01

8
1 2 3 4 3 3 2 1

Sample Output #01

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 k^th 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 k^th segment.
If width[k]=2, the bike and the car can pass through the k^th segment.
If width[k]=3, all three vehicles can pass through the k^th 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

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

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

Class

Problem Statement

Class is the C++ equivalent of struct. Along with storing multiple data in a common block, it also assigns some functions (known as methods) to manipulate/access them. It serves as the building block of Object Oriented Programming.

It also has access specifiers, which restrict the access of member elements. The primarily used ones are the following:

public: Public members (variables, methods) can be accessed from anywhere the code is visible.
private: Private members can be accessed only by other member functions, and it can not be accessed outside of class.

Class can be represented in the form of

class ClassName {
    access_specifier1:
        type1 val1;
        type2 val2;
        ret_type1 method1(type_arg1 arg1, type_arg2 arg2,...)
        ...
    access_specifier2:
        type3 val3;
        type4 val4;
        ret_type2 method2(type_arg3 arg3, type_arg3 arg3,...)
        ...
};

It’s a common practice to make all variables private, and set/get them using public methods. For example:

class SampleClass {
    private:
        int val;
    public:
        void set(int a) {
            val = a;
        }
        int get() {
            return val;
        }
};

We can store details related to a student in a class consisting of his age (int), first_name (string), last_name (string) and standard (int).

You have to create a class, named Student, representing the student’s details, as mentioned above, and store the data of a student. Create setter and getter functions for each element; that is, the class should at least have following functions:

get_age, set_age
get_first_name, set_first_name
get_last_name, set_last_name
get_standard, set_standard

Also, you have to create another method to_string() which returns the string consisting of the above elements, separated by a comma(,). You can refer to stringstream for this.

Input Format

Input will consist of four lines.
The first line will contain an integer, representing the age. The second line will contain a string, consisting of lower-case Latin characters (‘a’-‘z’), representing the first_name of a student.
The third line will contain another string, consisting of lower-case Latin characters (‘a’-‘z’), representing the last_name of a student.
The fourth line will contain an integer, representing the standard of student.

Note: The number of characters in first_name and last_name will not exceed 50.

Output Format

The code provided by HackerRank will use your class members to set and then get the elements of the Student class.

Sample Input

15
john
carmack
10

Sample Output

15
carmack, john
10

15,john,carmack,10

Solution

  
#include <cmath>
#include <cstdio>
#include <string>
#include <iostream>
#include <sstream>
using namespace std;

/*
Enter code for class Student here.
Read statement for specification.
*/
class Student{
    private:
    int age;
    string first_name;
    string last_name;
    int standard;
    public:
    
    void set_age(int a)
        {
        age=a;
    }
    void set_first_name(string f)
        {
        first_name= f;
    }
    void set_last_name(string l){
        last_name=l;
    }
    void set_standard(int s)
       {
        standard= s;
    }
    int get_age()
        {
        return age;
    }
    int get_standard(){
        return standard;
    }
    string get_first_name(){
        return first_name;
    }
    string get_last_name(){
        return last_name;
    }
   string to_string(){
       return std::to_string(age)+","+first_name+","+last_name+","+std::to_string(standard)+"\n";
    }
};

int main() {
    int age, standard;
    string first_name, last_name;
    
    cin >> age >> first_name >> last_name >> standard;
    
    Student st;
    st.set_age(age);
    st.set_standard(standard);
    st.set_first_name(first_name);
    st.set_last_name(last_name);
    
    cout << st.get_age() << "\n";
    cout << st.get_last_name() << ", " << st.get_first_name() << "\n";
    cout << st.get_standard() << "\n";
    cout << "\n";
    cout << st.to_string();
    
    return 0;
}

Structs

Problem Statement

struct is a way to combine multiple fields to represent a composite data structure, which further lays the foundation for Object Oriented Programming. For example, we can store details related to a student in a struct consisting of his age (int), first_name (string), last_name (string) and standard (int).

struct can be represented as

struct NewType {
    type1 value1;
    type2 value2;
    .
    .
    .
    typeN valueN;
};

You have to create a struct, named Student, representing the student’s details, as mentioned above, and store the data of a student.

Input Format

Input will consist of four lines.
The first line will contain an integer, representing age.
The second line will contain a string, consisting of lower-case Latin characters (‘a’-‘z’), representing the first_name of a student.
The third line will contain another string, consisting of lower-case Latin characters (‘a’-‘z’), representing the last_name of a student.
The fourth line will contain an integer, representing the standard of student.

Note: The number of characters in first_name and last_name will not exceed 50.

Output Format

Output will be of a single line, consisting of age, first_name, last_name and standard, each separated by one white space.

P.S.: I/O will be handled by HackerRank.

Sample Input

15
john
carmack
10

Sample Output

15 john carmack 10

Solution

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

/*
    add code for struct here.
*/
struct Student{
    int age;
    string first_name;
    string last_name;
    int standard;
};

int main() {
    Student st;
    
    cin >> st.age >> st.first_name >> st.last_name >> st.standard;
    cout << st.age << " " << st.first_name << " " << st.last_name << " " << st.standard;
    
    return 0;
}

StringStream

Problem Statement

stringstream is a stream class to operate on strings. It basically implements input/output operations on memory (string) based streams. stringstream can be helpful in different type of parsing. The following operators/functions are commonly used here

Operator >> Extracts formatted data.
Operator << Inserts formatted data.
Method str() Gets the contents of underlying string device object.
Method str(string) Sets the contents of underlying string device object.

Its header file is sstream.

One common use of this class is to parse comma-separated integers from a string (e.g., “23,4,56”).

stringstream ss("23,4,56");
char ch;
int a, b, c;
ss >> a >> ch >> b >> ch >> c;  // a = 23, b = 4, c = 56

You have to complete the function vector parseInts(string str). str will be a string consisting of comma-separated integers, and you have to return a vector of int representing the integers.

Input Format

The first and only line consists of n comma-separated integers.

Output Format

Print the integers after parsing it.

P.S.: I/O will be automatically handled. You need to complete the function only.

Sample Input

23,4,56

Sample Output

23
4
56

Solution

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

vector parseInts(string str) {
   // Complete this function
    stringstream ss(str);
    char ch;
    int temp;
    vector res;
    while(ss>>temp)
    { 
        res.push_back(temp);  
        if (ss.peek() == ',')
        ss.ignore();
    }
    return res;
     
}

int main() {
    string str;
    cin >> str;
    vector integers = parseInts(str);
    for(int i = 0; i < integers.size(); i++) {
        cout << integers[i] << "\n";
    }
    
    return 0;
}

Strings

Problem Statement

C++ provides a nice alternative data type to manipulate strings, and the data type is conveniently called string. Some of its widely used features are the following:

Declaration:
```
string a = "abc";
```
Size:
```
int len = a.size();
```

Concatenate two strings:

string a = "abc";
string b = "def";
string c = a + b; // c = "abcdef".

Assessing ith element:

string s = "abc";
char   c0 = s[0];   // c0 = 'a'
char   c1 = s[1];   // c1 = 'b'
char   c2 = s[2];   // c2 = 'c'

s[0] = 'z';         // s = "zbc"

P.S.: We will use cin/cout to read/write a string.

Input Format

You are given two strings, a and b, separated by a new line. Each string will consist of lower case Latin characters (‘a’-‘z’).

Output Format

In the first line print two space-separated integers, representing the length of a and b respectively.
In the second line print the string produced by concatenating a and b (a+b).
In the third line print two space-separated strings, a′ and b′. a′ and b′ are the same as a and b, respectively, except that their first characters are swapped.

Sample Input

abcd
ef

Sample Output

4 2
abcdef
ebcd af

Explanation

a=‘‘abcd“
b=‘‘ef“
|a|=4
|b|=2
a+b=‘‘abcdef“
a′=‘‘ebcd“
b′=‘‘af“

Solution

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

int main() {
   // Complete the program
    string a,b;
    cin>>a>>b;
    cout<<a.size()<<" "<<b.size()<<endl;
    cout<<a+b<<endl;
    char t=a[0];
    a[0]=b[0];
    b[0]=t;
    cout<<a<<" "<<b;
    return 0;
}

For Loop

Problem Statement

A for loop is a programming language statement which allows code to be repeatedly executed.

The syntax for this is

for ( <expression_1> ; <expression_2> ; <expression_3> )
    <statement>

expression_1 is used for intializing variables which are generally used for controlling terminating flag for the loop.
expression_2 is used to check for the terminating condition. If this evaluates to false, then the loop is terminated.
expression_3 is generally used to update the flags/variables.

A sample loop will be

for(int i = 0; i < 10; i++) {
    ...
}

Input Format

You will be given two positive integers, a and b (a≤b), separated by a newline.

Output Format

For each integer n∈[a,b] (so all numbers in that range):

If 1≤n≤9, then print the English representation of it. That is “one” for 1, “two” for 2, and so on.
Else if n>9 and it is even, then print “even”.
Else if n>9 and it is odd, then print “odd”.

Note: [a,b] represents the interval, i.e., [a,b]={x∈Z| a≤x≤b}={a, a+1,…,b}

Sample Input

8
11

Sample Output

eight
nine
even
odd

Solution

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

int main() {
    // Complete the code.
    int a,b;
    cin>>a>>b;
    for(int n=a;n<=b;n++)
    {
     if(n>9)
       {
          if(n%2==0)
              cout<<"even"<<endl;
           else cout<<"odd"<<endl;
       }
    else if(n==9)
        cout<<"nine"<<endl;
    else if(n==1)
        cout<<"one"<<endl;
    else if(n==2)
        cout<<"two"<<endl;  
    else if(n==3)
        cout<<"three"<<endl;        
    else if(n==4)
        cout<<"four"<<endl; 
    else if(n==5)
        cout<<"five"<<endl;
    else if(n==6)
        cout<<"six"<<endl;
    else if(n==7)
        cout<<"seven"<<endl;      
    else
        cout<<"eight"<<endl; 
     
    }
    return 0;
}

S	M	T	W	T	F	S
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31