Practice
Contest: Division 1
Contest: Division 2
Author: Sachin Yadav
Tester: Vraj Patel
Editorialist: Nishikant Parmar
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Simple conditional operators
PROBLEM:
There is a man of height H. He can duck by Y_{1} and jump by Y_{2}. There are barriers of two types namely t= 1 and t = 2. The barriers of type 1 start from a height X above the ground while the barriers of type 2 start from the ground and extend up to the height X above the ground. (Refer to the figure given in problem for better understanding )
He has life L and every time he can’t pass a barrier by bending or jumping he smashes into the barrier, breaking it, which costs him a single life and the barrier is considered passed. He can pass the barrier even if the barrier merely touches him on bending or jumping.
If after breaking a barrier no life is left, the man dies immediately, unable to pass that barrier.
How many barriers can he cross before dying finally?
QUICK EXPLANATION:
For each barrier, we look for condition in which man can pass it and decrease the life count if he can not pass. As soon as life becomes zero we stop traversing.
EXPLANATION:
This problem can be solved by traversing through the barriers one-by-one and checking the given conditions.
Case 1 : When t = 1
Since the barrier starts from a height X above the ground, the man can cross the barrier only if his height is less than or equal to X, the minimum height the man can achieve is H-Y_{1}, so if his minimum height is more than X then decrease the life by 1.
Case 2: When t = 2
Since the barrier extends up to a height X from the ground; the man can cross the barrier only if he jumps a height more than or equal to X. Thus, if Y_{2} is less than X, then decrease the life by 1.
While traversing the array if life becomes zero, then you should stop traversing. In the end, the answer is the number of barriers traversed.
Note: Do not count the barrier at which life becomes zero.
TIME COMPLEXITY
O(N)
SOLUTIONS:
Setter's Solution
#include<iostream>
using namespace std;
int arr[1001], types[1001];
int main()
{
int T; cin>>T;
while(T--)
{
int N,H, Y1, Y2, L; cin>>N>>H>>Y1>>Y2>>L;
int count=0;
for(int i=0; i<N; i++) cin>>types[i]>>arr[i];
for(int i=0; i<N; i++)
{
if(types[i]==1 && arr[i]<H-Y1)
--L;
else if(types[i]==2 && arr[i]>Y2)
--L;
if(L==0) break;
++count;
}
cout<<count<<"\n";
}
return 0;
}
Tester's Solution
for _ in range(int(input())):
N,H,y1,y2,L = [int(i) for i in input().split()]
barr_l = [[int(i) for i in input().split()] for j in range(N)]
bc = 0
for bt,x in barr_l:
if(bt==1):
if(x<H-y1):
L-=1
else:
if(y2<x):
L-=1
if L>0:
bc+=1
if L<=0:
break
print(bc)
Editorialist's Solution
T=int(input())
for k in range(T):
N, H, Y1, Y2, L = map(int,input().split())
barriers = [(0,0)]*N
for i in range(N):
t,X = map(int,input().split())
barriers[i]=(t,X)
ans = 0
for j in range(N):
t = barriers[j][0]
X = barriers[j][1]
if t==1:
if H-Y1 > X:
L = L - 1
else:
if Y2 < X:
L = L - 1
if L==0:
break
ans = ans + 1
print(ans)
