A man is doing an experiment with the device that he built newly. The structure of the device is as below diagram.
B to E is a sloping surface with n holes, labelled H1, H2, … Hn, on it. Holes are of different diameters and depths. The man is releasing m number of balls of different diameters from the point B one after the other. He needs to find the positions of each ball after the experiment. The specialities of the device are : A ball will fall into the hole, if its diameter is less than or equal to the diameter of the hole. A hole Hi will become full, if i numbers of balls fall into it. For example hole labelled H3 will become full if 3 balls fall into it. If a hole is full, then no more balls fall into it. A ball will reach the bottom point E from B, if and only if it is not falling into any of the holes. Please help him in finding the eventual position of the balls. If a ball is in hole Pi, then take its position as i. If a ball reached the bottom point E, then take its position as 0.
Constraints:
0 <= N <= 50
0 < Diameter of holes <= 10^9
0 < m <= 1000
0 < Diameter of balls <= 10^9
Input:
Line 1 : total number of holes, N
Line 2 : N space seperated integers denoting the diameters of N holes, from bottom to top.
Line 3 : total number of balls, M.
Line 4 : M space seperated integers denoting diameters of balls in the order of release.
Output:
Line 1 : Positions of each ball in the order of ball release seperated by space.
Example
Input:
3
21 3 6
11
20 15 5 7 10 4 2 1 3 6 8
Output:
1 0 3 0 0 3 3 2 2 0 0
Solution: In C
#include<stdio.h>
// #define int long long
int main(){
int n;
scanf("%d",&n);
int cap[n+1];
int arr[n+1];
arr[0]=1000000007;
cap[0]=100;
for(int i=0;i<n;i++) {
scanf("%d",&arr[i]);
cap[i]=i+1;
}
int q;
scanf("%d",&q);
while(q--){
int k;
scanf("%d",&k);
int flag=0;
for(int j=n-1;j>=0;j--){
if(arr[j]>=k && cap[j]>0){
cap[j]--;
printf("%d ",j+1);
flag=1;
break;
}
}
if(flag == 0)
printf("%d ", flag);
}
}Solution: In Java
import java.util.*;
class Main{
public static void main(String[] args){
Scanner ip=new Scanner(System.in);
int n,i,q;
n=ip.nextInt();
int[] cap=new int[n+1];
int[] a=new int[n+1];
a[0]=1000000007;
cap[0]=100;
for(i=0;i<n;i++) {
a[i]=ip.nextInt();
cap[i]=i+1;
}
q=ip.nextInt();
while(q!=0){
int k;
k=ip.nextInt();
int flag=0;
for(int j=n-1;j>=0;j--){
if(a[j]>=k && cap[j]>0){
cap[j]--;
System.out.print(j+1 + " ");
flag=1;
break;
}
}
if(flag == 0)
System.out.print(flag + " ");
q--;
}
}
}Solution: In Python 3
N=int(input())
if(0<N<=50):
holes=[]*N
holes=list(map(int,input().split()))
H=[]
l1=[]
l2=[]
final_list=[]
for i in range(N):
H.append(i+1)
M=int(input())
set_flag=0
l1=list(range(0,N))
l2=l1[::-1]
if(0<M<=1000):
balls=[]*M
balls=list(map(int,input().split()))
flag=1
for each_ball in balls:
if(flag==0):
for i in l2:
if(each_ball<=holes[i] and H[i]>0):
final_list.append(i+1)
H[i]=H[i]-1
set_flag=1
flag=0
break
else:
set_flag=0
if(set_flag==0):
final_list.append(0)
flag=0
if(flag==1):
for j in l1:
if(each_ball<=holes[j] and H[j]>0):
final_list.append(j+1)
H[j]=H[j]-1
set_flag=1
flag=1
break
else:
set_flag=0
if(set_flag==0):
final_list.append(0)
flag=0
for ii in range(M-1):
print(final_list[ii],end=" ")
print(final_list[M-1])Also Checkout