# Capgemini Tech Challenge 2019 | Round2 & Round 3 Question

**Round 2:**

**MISSION WITH MI6: **Last year a hacking took place in the safest and crucial defense network of the US. Hackers downloaded crucial defense-related confidential files and documents from their network and after that, they flew to Dubai for delivery of the documents to some terror-related outfits. Investigation Agent MI6 found that there is a meeting scheduled between parties in the hotel room of Burj Khalifa. MI6 agency formed a team and send their best agents for recovering documents and catching hackers.

Hey geek! It's time to become a success story instead of reading them. Check out our most renowned **DSA Self Paced Course**, now at a student-friendly price and become industry ready. And if you are looking for a more complete interview preparation resource, check out **Complete Interview Preparation Course**** **that will prepare you for the SDE role of your dreams!

Feeling prepared enough for your interview? Test your skills with our **Test Series** that will help you prepare for top companies like **Amazon, Microsoft, TCS, Wipro, Google** and many more!

After reaching Dubai, agents check-in to a hotel and found a way to go to the room by hacking surveillance cameras but there is very high security on the floor where the meeting is supposed to be held. So they decided to take another route by walking on the wall of the hotel building with the help of electromagnetic repulsive force. They have a gadget having this type of technology that helps them in walking on the wall of the hotel.

There are various metal square-shaped sheets attached to the outside wall of the hotel. A specialist agent Bob decided to walk on the wall and his colleague guide him and instruct him that on which square sheet he had to walk. Bob’s colleague sends him a set of instructions which helps in determining which particular sheet he has to stand. A set of instructions is a string that consists of letters ‘L’, ‘R’, ‘U’, ‘D’ .

For simplicity let’s assume that Bob is staying at point (0, 0) on a big wall. He consistently fulfills all the instructions sent by his colleague. Let’s assume that now he is staying at point (X, Y), then depending on what is the current instruction he moves in one direction:

‘L’: from (X,Y) moves to point (X,Y-1) ‘R’: from (X,Y) moves to point (X,Y+1) ‘U’: from (X,Y) moves to point (X-1,Y) 'D' : from (X,Y) moves to point (X+1,Y)

Initially, all the points are good ones and there is no crack on any point or sheet. But if Bob already visited some point at any time then next time this point cracked. Every time Bob makes a step on the cracked points he slips on the wall.

You are given a string S which tells the set of instructions for Bob. Your work is to calculate how many times Bob slips from his position.

**Input Format:**

**Input 1:** It will be a string that tells the string S which denotes the set of instructions for Bob.

Constraints 1 ≤ S ≤ 105

**Output Format: **It will be an integer which tells that how many times Bob slips from his position

Sample TestCase 1

InputRRULDLOutput2 Here is my solution:

## C++

`#include<bits/stdc++.h>` `using` `namespace` `std;` `int` `main()` `{` ` ` `/*input the string*/` ` ` `string str;` ` ` `cin>>str;` ` ` `/* best data structure for this problem is ` ` ` `unordered map , by using this data structure` ` ` `we can detect every repeating steps*/` ` ` `unordered_map<string,` `int` `> mp;` ` ` `int` `res=0;` ` ` `int` `x=0,y=0;` ` ` `string ss;` ` ` `mp[` `"0,0"` `]=1;` ` ` `/*traverse the whole string */` ` ` `for` `(` `int` `i=0;i<str.size();i++)` ` ` `{` ` ` `if` `(str[i]==` `'L'` `)` ` ` `{` ` ` `y--;` ` ` `ss=to_string(x)+` `","` `+to_string(y);` ` ` `if` `(mp[ss]) res++;` ` ` `else` ` ` `mp[ss]=1;` ` ` `}` ` ` `else` `if` `(str[i]==` `'R'` `)` ` ` `{` ` ` `y++;` ` ` `ss=to_string(x)+` `","` `+to_string(y);` ` ` `if` `(mp[ss]) res++;` ` ` `else` ` ` `mp[ss]=1;` ` ` `}` ` ` `else` `if` `(str[i]==` `'D'` `)` ` ` `{` ` ` `x++;` ` ` `ss=to_string(x)+` `","` `+to_string(y);` ` ` `if` `(mp[ss]) res++;` ` ` `else` ` ` `mp[ss]=1;` ` ` `}` ` ` `else` `if` `(str[i]==` `'U'` `) {` ` ` `x--;` ` ` `ss = to_string(x) + ` `","` `+ to_string(y);` ` ` `if` `(mp[ss]) res++;` ` ` `else` ` ` `mp[ss] = 1;` ` ` `}` ` ` `}` ` ` `cout<<res;` ` ` `return` `0;` ` ` `}` |

**Bob route consists of the following points:**

0,0 ---> 0,1 ---> 0,2 ----> -1,2 ---> -1,1 ----> 0,1(cracks) ----> 0,0 (cracks)

So, there will be 2 points where Bob visited again, and so he slips 2 steps.

**Round 3:**

**Craziest Prisons and Jails: **Some prisons are known for being violent and treating prisoners like animals, leading to inhumane and unethical tactics for keeping the peace. There is a prison located in Norway, Halden is often described as peaceful and relaxing. The prisoners are treated to good food, hot coffee, and cells that boast televisions, mini-fridges, private bathrooms, and scenic views of the surrounding forest.

Norway’s government build 3 new prisons each one is having its own unique design different from the other. Each prison consists of cells arranged into a one, two, or three-dimensional grid. Jailer can fill N prisoners into the cells.

The Distance between two cells is the smallest number of moves that a prisoner would need in order to reach one cell from the other. In one move, the prisoner may step into one of the adjacent cells.

Two prisoners can hear each other if the distance between their cells is at most D. Your task is to calculate how many pairs of prisoners there are such that one prisoner can hear the other prisoner.

**Example: **Suppose the prison will of 3-dimensional type then it will look like below

**Input Format:**

**Input 1:**It will be the integer which tells the type of prison P**Input 2:**It will be the integer which tells the number of prisoners N**Input 3:**It will be the integer which tells the largest distance D at which two prisoners can hear each other**Input 4:**It will be the integer which tells the size of the prison S; (the largest coordinate allowed to appear in the input):When P=1, S will be at most 75000000.

When P=2, S will be at most 75000.

When P=3, S will be at most 75.

**Input 5:**It will be a string array which tells the coordinates of each prisoner. Array format will be like:First-line will tell the total number of rows i.e. total number of prisoners N

Each of the following N lines contains P integers separated by single commas – the coordinates of one prisoner. Each coordinate will be between 1 and S (inclusive). More than one prisoner may occupy the same cell. If the P is one, then there will be no comma – only single value will be there in each line.

**Constraints**

1 ≤ P ≤ 3 1 ≤ N ≤ 100000 1 ≤ D ≤ 100000000

**Output Format: **It will be the single integer, the number of pairs of prisoners that can hear each other.

**Sample TestCase 1:**

Input3 8 10 20 8 10,10,10 10,10,20 10,20,10 10,20,20 20,10,10 20,10,20 20,20,10 20,20,20 Output 12

**Solution in C++:**

## C++

`#include<bits/stdc++.h>` `#define ll long int` `using` `namespace` `std;` ` ` `//calculate distance in 2D for two grid` `/* For 2D jail */` `int` `TwoD(ll x1,ll y1, ll x2, ll y2,ll distance ) ` `{` ` ` ` ` `ll d=0;` ` ` `if` `(x1==x2){` ` ` `d=` `abs` `(y1-y2);` ` ` `}` ` ` `else` `if` `(y1==y2){` ` ` `d=` `abs` `(x1-x2);` ` ` `}` ` ` `else` `{` ` ` `return` `0;` ` ` `}` ` ` ` ` `if` `(d<=distance){` ` ` `return` `1;` ` ` `}` ` ` `else` `{` ` ` `return` `0;` ` ` `}` ` ` ` ` `}` ` ` ` ` `//calculate distance in 3D for two grid` ` ` `/* For 3D jail*/` `int` `ThreeD(ll x1, ll y1,ll z1, ll x2,ll y2,ll z2,ll distance) ` `{` ` ` `ll d=0;` ` ` `if` `(x1==x2&&y1==y2){` ` ` `d=` `abs` `(z1-z2);` ` ` `}` ` ` `else` `if` `(y1==y2&&z1==z2){` ` ` `d=` `abs` `(x1-x2);` ` ` `}` ` ` `else` `if` `(z1==z2&&x1==x2){` ` ` `d=` `abs` `(y1-y2);` ` ` `}` ` ` `else` `{` ` ` `return` `0;` ` ` `}` ` ` ` ` `if` `(d<=distance){` ` ` `return` `1;` ` ` `}` ` ` `else` `{` ` ` `return` `0;` ` ` `}` ` ` `}` ` ` ` ` `//driver program` `int` `main()` `{` ` ` `ll p,n,d,s;` ` ` ` ` `ll res=0;` ` ` `cin>>p;` ` ` `cin>>n;` ` ` `cin>>d;` ` ` `cin>>s;` ` ` `cin>>n;` ` ` `ll distance=d ;` ` ` `int` `inp[n],inp1[n],inp2[n];` ` ` `ll x1,x2,y1,y2,z1,z2;` ` ` ` ` `if` `(p==1)` ` ` `{` ` ` `for` `(` `int` `i=0;i<n;i++)` ` ` `{` ` ` `cin>>inp[i];` ` ` ` ` ` ` `}` ` ` `}` ` ` `else` `if` `(p==2) {` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `scanf` `(` `"%d,%d"` `, &inp[i], &inp1[i]);` ` ` `}` ` ` `}` ` ` `else` `{` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `scanf` `(` `"%d,%d,%d"` `, &inp[i], &inp1[i], &inp2[i]);` ` ` ` ` `}` ` ` `}` ` ` ` ` ` ` ` ` `if` `(p==1)` ` ` `{` ` ` `sort(inp,inp+n);` ` ` `for` `(` `int` `i=0;i<n-1;i++)` ` ` `{` ` ` `for` `(` `int` `j = i+1; j <n ; j++) {` ` ` `if` `(inp[i] && inp[j] && inp[i]<=s && inp[j]<=s) {` ` ` `if` `(` `abs` `(inp[i] - inp[j]) <= distance) {` ` ` `res++;` ` ` `} ` `else` `{` ` ` `break` `;` ` ` `}` ` ` `}` ` ` ` ` `}` ` ` ` ` ` ` `}` ` ` `}` ` ` `else` `if` `(p==2) {` ` ` `for` `(` `int` `i = 0; i < n-1; i++) {` ` ` `for` `(` `int` `j=i+1;j<n;j++) {` ` ` `x1 = inp[i];` ` ` `y1 = inp1[i];` ` ` `x2 = inp[j];` ` ` `y2 = inp1[j];` ` ` `if` `(x1 && y1 && x2 && y2 && x1<=s && y1<=s && x2<=s && y2<=s )` ` ` `if` `(TwoD(x1,y1,x2,y2,distance)) {` ` ` `res++;` ` ` `}` ` ` `}` ` ` `}` ` ` `}` ` ` `else` `{` ` ` `res=0;` ` ` `for` `(` `int` `i = 0; i < n-1; i++) {` ` ` `for` `(` `int` `j=i+1;j<n;j++) {` ` ` `x1 = inp[i];` ` ` `y1 = inp1[i];` ` ` `z1 = inp2[i];` ` ` `x2 = inp[j];` ` ` `y2 = inp1[j];` ` ` `z2 = inp2[j];` ` ` `if` `(x1 && y1 && z1 && x2 && y2 && z2 && x1<=s && y1<=s && z1<=s && x2<=s && y2<=s && z2<=s )` ` ` `if` `(ThreeD(x1,y1,z1,x2,y2,z2,distance)){` ` ` `res++;` ` ` `}` ` ` ` ` `}` ` ` `}` ` ` `}` ` ` ` ` `cout<<res;` ` ` `return` `0;` `}` |