Monk and Philosopher's Stone - HackerEarth Solution

Monk and Philosopher's Stone - Hacker Earth Solution

Harry Potter wants to get the Philosopher's stone to protect it from Snape. Monk being the guard of Philosopher's Stone is very greedy and has a special bag, into which he can add one gold coin at a time or can remove the last gold coin he added. Monk will sleep, once he will have the enough number of gold coins worth amount X. To help Harry, Dumbledore has given a same kind of bag to Harry (as of Monk) with N gold coins each having worth  $A[i]$ where i range from $1\le i\le N$.

Dumbledore also gave him a set of instructions which contains two types of strings:
1) "Harry" (without quotes): It means Harry will remove $i^{th}$ coin from his bag and throw it towards Monk and Monk will add it in his bag, where i will start from 1 and go up to N.
2) "Remove" (without quotes): it means Monk will remove the last coin he added in his bag.
Once the worth of the coins in Monk's bag becomes equal to X, Monk will go to sleep. In order to report Dumbledore, Harry wants to know the number of coins in Monk's bag, the first time their worth becomes equal to X.

Help Harry for the same and print the required number of coins. If the required condition doesn't occur print "-1" (without quotes).

Input:
The first line will consists of one integer N denoting the number of gold coins in Harry's Bag.
Second line contains N space separated integers, denoting the worth of gold coins.
Third line contains 2 space separated integers Q and X, denoting the number of instructions and the value of X respectively.
In next Q lines, each line contains one string either "Harry" (without quotes) or "Remove" (without quotes).

Output:
In one line, print the the number of coins in the Monk's bag, the first time their worth becomes equal to X.

Constraints:
$1\le N\le {10}^4$
$1\le A[i]\le {10}^4$
$1\le Q\le {10}^5$
$1\le X\le {10}^7$

SAMPLE INPUT

 

4
3 1 1 4
6 7
Harry
Harry
Harry
Remove
Remove
Harry

SAMPLE OUTPUT

 

2

Explanation

Initailly, set of instructions contains "Harry", then Harry will throw $1^{st}$ coin to Monk which is of worth 3 . Similarly Monk will have  $2^{nd}$ and $3^{rd}$ gold coin in its bag, both having worth 1.

Now set contains "Remove" 2 times, which means Monk will remove $3^{rd}$ and $2^{nd}$ coin, both having worth 1.

Now Harry will throw $4^{th}$ coin towards Monk having worth 4. Now the Monk's bag contains 2 coins with worth 3 and 4, which is equal to worth 7.

So the answer is 2.

Monk and Philosopher's Stone - Hacker Earth Solution

Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
 stack<int> s;
 int n;
 cin>>n;
 int a[n];
 for(int i=0;i<n;i++)
 {
 cin>>a[i];
 }
 int t;
 int x,top1;
 int sum=0;
 int k =0;
 cin>>t>>x;
 int count =0;
 while(t--)
 {
 
 string s1;
 cin>>s1;
 if(s1 == "Harry")
 {
 s.push(a[k]);
 sum+= a[k];
 k++;
 
 }
 if(sum == x)
 {
 cout<<s.size()<<endl;
 break;
 }
 else if(s1 == "Remove")
 {
 top1 = s.top();
 sum-= top1;
 s.pop();
 }
 
 }
 if(sum!= x)
 {
 cout<<"-1"<<endl;
 }
 return 0;
}

Monk and Philosopher's Stone - Hacker Earth Solution

All rights reserved. No part of this Post may be copied, distributed, or transmitted in any form or by any means, without the prior written permission of the website admin, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law. For permission requests, write to the owner, addressed “Attention: Permissions Coordinator,” to the coderinme.net@gmail.com.

Disclaimer: The above Problem is generated by HackerEarth but the Solution is Provided by Us. This tutorial is only for Educational and Learning purposes. Authority if any of the queries regarding this post or website contact us on coderinme.net@gmail.com .

For DMCA: https://allhackerranksolutionsbykaira.blogspot.com/p/dmca.html