HackerEarth Gudi trapped in the Room problem solution

In this HackerEarth Gudi trapped in the Room problem solution Gudi enters the castle, and moves along the main path. Suddenly, a block in the ground opens and she falls into it! Gudi slides down and lands in a dark room. A mysterious voice announces:

Intruders are not allowed inside the castle. To proceed, you must solve my puzzle. Here is a string S indexed from 1 to N, consisting of digits from 0-9. If you summon the spell "Sera", the string will be rotated clockwise by H positions. If you summon the spell "Xhaka", the number A will be added to all the even-indexed digits of the string. For example, if H = 1 A = 3 "Sera" and "Xhaka" on the string "781" will result in strings ""178" and "711" respectively i.e. digits post 9 are cycled back to 0. The objective is to obtain the lexicographically smallest string possible as a result of applying any of the two spells any number of times in any order. Find the string and I shall set you free


HackerEarth Gudi trapped in the Room problem solution


HackerEarth Gudi trapped in the Room problem solution.

#include<bits/stdc++.h>


using namespace std;

#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define elif else if
#define pii pair<int,int>
#define pb push_back

set<string>mp;
int add,shift;
void dfs( string tmp)
{
//cout<<tmp<<endl;
mp.insert(tmp);
string next=tmp;
int i,n=tmp.size();
for(i=0;i<n;i++)
{
next[(i+shift)%n]=tmp[i];
}
if(mp.find(next)==mp.end())
dfs(next);
next=tmp;
for(i=0;i<n;i++)
{
if(i%2)
next[i]= '0'+ (next[i]-'0'+add)%10;
}
if(mp.find(next)==mp.end())
dfs(next);
return;
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out","w",stdout);
ios_base::sync_with_stdio(0);
int t;
cin>>t;
assert(1<=t && t<=10);
while(t--)
{
string inp;
cin>>inp>>add>>shift;
mp.clear();
dfs(inp);
cout<<*(mp.begin());
if(t>0)
cout<<endl;
}
return 0;
}

Second solution

import sys
t = int(sys.stdin.readline())
stack = [[] for i in range(1000010)]
for __ in range(t):
s = map(lambda x: ord(x)-ord('0'), sys.stdin.readline().rstrip())
a,h = map(int, sys.stdin.readline().split())
h %= len(s)
ans = "".join(map(str,s))
vis = set()
sidx = 0

def push(val):
global ans,sidx
hs = "".join(map(str,val))
if hs in vis: return
ans = min(ans, hs)
vis.add(hs)
stack[sidx] = val
sidx += 1

push(s)
while sidx > 0:
cur = stack[sidx-1]
sidx -= 1
push(cur[h:]+cur[:h])
for i in range(1,len(cur),2):
cur[i] = (cur[i]+a)%10
push(cur)

print ans

Post a Comment

0 Comments