from collections import defaultdict graph=defaultdict(list) v,e=map(int,input().split()) for i in range(e): u,v=map(str,input().split()) graph[u].append(v) graph[v].append(u) for i in graph: print(i,"->",graph[i]) Input: 7 9 A B A C A F C E C F C D D E D G G F Output: F -> ['A', 'C', 'G'] C -> ['A', 'E', 'F', 'D'] G -> ['D', 'F'] D -> ['C', 'E', 'G'] A -> ['B', 'C', 'F'] E -> ['C', 'D'] B -> ['A']
Problem Description
There is a corridor in a Jail which is N units long. Given an array A of size N. The ith index of this array is 0 if the light at ith position is faulty otherwise it is 1.
All the lights are of specific power B which if is placed at position X, it can light the corridor from [ X-B+1, X+B-1].
Initially all lights are off.
Return the minimum number of lights to be turned ON to light the whole corridor or -1 if the whole corridor cannot be lighted.
Problem Constraints1 <= N <= 1000
1 <= B <= 1000
Input Format
First argument is an integer array A where A[i] is either 0 or 1.
Second argument is an integer B.
Output Format
Return the minimum number of lights to be turned ON to light the whole corridor or -1 if the whole corridor cannot be lighted.
Example Input
Input 1:
A = [ 0, 0, 1, 1, 1, 0, 0, 1].
B = 3
Input 2:
A = [ 0, 0, 0, 1, 0].
B = 3
Example Output
Output 1:
2
Output 2:
-1
Example Explanation
Explanation 1:
In the first configuration, Turn on the lights at 3rd and 8th index.
Light at 3rd index covers from [ 1, 5] and light at 8th index covers [ 6, 8].
Explanation 2:
In the second configuration, there is no light which can light the first corridor.
Solution: class Solution:
# @param A : list of integers
# @param B : integer
# @return an integer
def solve(self, A, B):
foundAt=0
i=0
count=0
len_a=len(A)
while(i<len_a):
j=min(i+B-1,len_a-1)
found=False
while(j>=(i-B+1) and j>0 and j<len_a):
if(A[j]==1):
found=True
foundAt=j
count+=1
i=foundAt+B
break;
j-=1
if not found:
return -1
return count
Solution Credits:
Comments
Post a Comment