RIB - Editorial


Run It Back

Author: Shreyas Barve
Tester: Rishabh Rathi




Number Theory


The place where Senku wants to go is full of sulfuric acid deposits (which emits deadly gas that will kill him on the spot). Senku, being a genius has made a gas mask.

The gas mask functions in the following way:
Among the K deposits closest to him, if there are strictly more sulfuric acid deposits than other gases then Senku has to run away and he will not be able to get the sulfuric acid. Otherwise, he can get the acid.

You have to develop a solution to this problem. Help him out!


The problem is similar to KNN problem to some extent. You have co-ordinates of Senku.
You find the distances of other co-ordinates with respect to Senku using Euclidean distance.

Add the values to a list and sort the list according to the distance in ascending order.
You have to then take first K points and count the number of gases, compare them and output accordingly.


Tester's Solution - Python
import math

# co-ordinates of the site
x, y = map(int, input().split())

# n = total number of sites
# k = sites which gas mask can handle
n, k = map(int, input().split())

# list to store all the sites data
sites = []

# including all the data of the sites
for i in range(n):
	x1, y1, g = input().split()
	x1, y1 = int(x1), int(y1)
	dist = math.sqrt((x-x1)**2 + (y-y1)**2)
	sites.append([dist, g])

# sort all the sites accoding to their distances

# get the data of only needed sites
cnt_sulphur = cnt_other = 0

for i in range(k):
	if sites[i][1] == "S":
		cnt_sulphur += 1
		cnt_other += 1	

if cnt_sulphur > cnt_other:
	print("EASY AS CAKE")

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. :smile: