In this HackerEarth Benny and Gifts problem solution Little pig Benny has just taken a shower. Now she is going to buy some gifts for her relatives. But the problem is that Benny doesn’t know how to reach to the gift shop. Her friend Mike has created a special set of instructions for her. A set of instructions is a string which consists of letters {‘L’, ‘R’, ‘U’, ‘D’}.
For simplicity, let’s assume that Benny is staying at point (0, 0) on the infinite plane. She consistently fulfills all the instructions written by Mike. Let’s assume that now she is staying at point (X, Y). Then depending on what is the current instruction she moves in some 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)
The weather is cold because it’s winter now. Initially, all points are snowy. But if Benny have already visited some point at any time this point becomes icy (because Benny has just taken a shower). Every time, when Benny makes a step into icy points she slips and falls down.
You are given a string S which denotes a set of instructions for Benny. Your task is to calculate how may times she will fall down.
HackerEarth Benny and Gifts problem solution.
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
#include <utility>
#include <memory.h>
#include <set>
#include <map>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
const int N = 100500;
int n;
int x, y;
char s[N];
set< pair<int, int> > was;
int main() {
gets(s + 1);
n = (int)strlen(s + 1) + 1;
x = y = 0;
int result = 0;
for (int i = 1; i <= n; i++) {
cout << x << " " << y << " --> ";
if (was.find(mp(x, y)) != was.end()) {
++result;
}
was.insert(mp(x, y));
if (s[i] == 'L') {
--y;
} else if (s[i] == 'R') {
++y;
} else if (s[i] == 'U') {
--x;
} else if (s[i] == 'D') {
++x;
}
}
printf("%dn", result);
return 0;
}
Second solution
#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <time.h>
#include <cassert>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
#define FILL(A,value) memset(A,value,sizeof(A))
#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979
typedef long long Int;
typedef unsigned long long UInt;
typedef vector<int> VI;
typedef pair<int, int> PII;
const int INF = 1000000007;
const int MAX = 40007;
const int MAX2 = 1000000;
const int MAXD = 20;
const int BASE = 1000000007;
const int MOD = 1000000007;
int main()
{
//ifstream inUser("users.csv");
//ifstream inProblem("problems.csv");
//freopen("in.txt" , "r" , stdin);
//freopen("out.csv" , "w" , stdout);
string s;
cin >> s;
assert(s.size() >= 1 && s.size() <= 100000);
int x = 0;
int y = 0;
set<PII> S;
S.insert(MP(0,0));
int res = 0;
FOR(i,0,s.size())
{
assert(s[i] == 'L' || s[i] == 'R' || s[i] == 'U' || s[i] == 'D');
if (s[i] == 'L') --y;
if (s[i] == 'R') ++y;
if (s[i] == 'U') --x;
if (s[i] == 'D') ++x;
if (S.count(MP(x , y))) ++res;
S.insert(MP(x , y));
}
cout << res << endl;
return 0;
}