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.
Contraints
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.
Testcase
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
CODE (SOLUTION)
#include<iostream>
using namespace std;
int main()
{
int n,m;
cin>>n;
int h[n+1];
int capa[n+1];
for(int i=0;i<n;i++)
{
cin>>h[i];
capa[i]=i+1;
}
cin>>m;
int b[m+1];
int res=0;
int ctr=0;
for(int i=0;i<m;i++)
{
ctr=0;
cin>>b[i];
for(int j=n-1;j>=0;j--)
{
if(b[i]<=h[j] && capa[j]!=0)
{
cout<<(j+1)<<" ";
capa[j]--;
ctr=1;
break;
}
}
if(ctr==0)
{
cout<<"0"<<" ";
}
}
}
If we go through sequence order the output will be below, sequence.
3
21 3 6
11
20 15 5 7 10 4 2 1 3 6 8
1 0 3 0 0 3 2 2 3 0 0
Bro you have to check first for 6 then for 3 then for 21 as above statement I was also doing the same mistake I take me a while to fix that
import java.io.*;
import java.util.Arrays;
public class Main
{
public static void main (String[]args) throws IOException
{
BufferedReader br =new BufferedReader (new InputStreamReader (System.in));
//—————————holes————————————–
int N = Integer.parseInt (br.readLine ());
String diameter = br.readLine ();
diameter.trim ();
String N_diameter[] = diameter.split (” “, -1);
diameter = null;
//———————————————————————–
//+++++++++++++++constraints checking++++++++++++++++++++++++++++++++++
{
if (N > 50 || N < 0 || N_diameter.length != N)
{
System.exit (0);
}
for (int i = 0; i 1000000000)
{
System.exit (0);
}
}
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//————————-balls—————————————-
int balls = Integer.parseInt (br.readLine ());
diameter = br.readLine ();
String ball_diameter[] = diameter.split (” “, -1);
//———————————————————————-
//+++++++++++++++constraints checking+++++++++++++++++++++++++++++++++++
{
if (balls > 1000 || balls < 0 || ball_diameter.length != balls)
{
System.exit (0);
}
for (int i = 0; i 1000000000)
{
System.exit (0);
}
}
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//————————-final pos————————————
int final_pos[] = new int[balls];
int count[] = new int[N_diameter.length];
Arrays.fill (count, 1);
//———————————————————————-
//FINAL LOGIC
for (int i = 0; i = 0; j–)
{
if (Integer.parseInt (ball_diameter[i]) <=
Integer.parseInt (N_diameter[j]) && count[j] <= j + 1)
{
count[j] = count[j] + 1;
final_pos[i] = j + 1;
break;
}
else
{
final_pos[i] = 0;
}
}
}
for (int i = 0; i < balls; i++)
{
System.out.print (final_pos[i] + " ");
}
}
}
n=int(input(“Enter no. of balls:”))
d1,d2,d3=[int(input(“Enter diameter of holes:”)) for i in range(3)]
m=int(input(“Enter no. of balls:”))
l=[20,15,5,7,10,4,2,1,3,6,8]
a,b,c=0,0,0
for i in l:
if a==1:
if b<=2:
if i<=d2 and b<2:
print("2",end="")
b+=1
elif i<=d3 and c<3:
print("3",end="")
c+=1
else:
print("0",end="")
elif i<=d1:
print("1",end="")
a+=1
hn=int(input())
hdl=list(map(int,input().split()))
bn=int(input())
bdl=list(map(int,input().split()))
h={}
sol={}
for i in range(hn):
h[i]=[]
for i in range(bn):
flag=False
for j in range(hn-1,-1,-1):
if bdl[i]<=hdl[j] and len(h[j])<j+1:
h[j].append(bdl[i])
sol[bdl[i]]=j+1
flag=True
break
else:
if not flag:
sol[bdl[i]]=0
for i in sol.values():
print(i,end=' ')
#include
int main()
{
int n,m;
scanf(“%d”,&n);
int h[n+1];
int capa[n+1];
for(int i=0;i<n;i++)
{
scanf("%d",&h[i]);
capa[i]=i+1;
}
scanf("%d",&m);
int b[m+1];
int res=0;
int ctr=0;
for(int i=0;i=0;j–)
{
if(b[i]<=h[j] && capa[j]!=0)
{
printf("%d ",j+1);
capa[j]–;
ctr=1;
break;
}
}
if(ctr==0)
{
printf("0 ");
}
}
}
n=int(input())
l1=list(map(int,input().split()))
holes=[]
for i in range(n):
holes.append([l1[i] , i+1])
m=int(input())
balls=list(map(int,input().split()))
res=[“0”]*m
c=1
for i in range(2,n+1):
c *= i
for i in range(m):
if c==0:
break
for j in range(n):
if holes[j][1] > 0:
if balls[i] <= holes[j][0]:
holes[j][1] -= 1
c -= 1
res[i] = str(j+1)
break
print(" ".join(res))
package project;
import java.util.*;
public class hallball {
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int H[]=new int[N];
int cap[]=new int[N];
for(int i=0;i<N;i++)
{
H[i]=sc.nextInt();
cap[i]=i+1;
}
int M=sc.nextInt();
int P[]=new int[M];
int pos[]=new int[M];
for(int i=0;i<M;i++)
{
P[i]=sc.nextInt();
pos[i]=0;
}
for(int i=0;i=0;j–)
{
if(cap[j]>0)
{
if(P[i]<=H[j])
{
pos[i]=j+1;
cap[j]–;
break;
}
}
}
}
for(int i=0;i<M;i++)
{
System.out.print(pos[i]);
}
}
}
//Simple solution by Nikhil Prakash
import java.io.*;
import java.util.Scanner;
import java.util.Arrays;
class Balls
{
public static void main(String args[])throws IOException
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();//holes
int holes[]=new int[n];
int cap[]=new int[n];
for(int i=0;i<n;i++)
{
holes[i]=sc.nextInt();
cap[i]=i+1;
}
int m=sc.nextInt();//balls
int balls[]=new int[m];
int pos[]=new int[m];
for(int i=0;i=0;j–)
{
if(balls[i]<=holes[j])
{
if(cap[j]!=0)
{
cap[j]–;
pos[i]=j+1;
break;
}
}
}
}
System.out.println(Arrays.toString(pos));
}
}
//simple solution by Nikhil Prakash using Java
import java.io.*;
import java.util.Scanner;
import java.util.Arrays;
class Balls
{
public static void main(String args[])throws IOException
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();//holes
int holes[]=new int[n];
int cap[]=new int[n];
for(int i=0;i<n;i++)
{
holes[i]=sc.nextInt();
cap[i]=i+1;
}
int m=sc.nextInt();//balls
int balls[]=new int[m];
int pos[]=new int[m];
for(int i=0;i=0;j–)
{
if(balls[i]<=holes[j])
{
if(cap[j]!=0)
{
cap[j]–;
pos[i]=j+1;
break;
}
}
}
}
System.out.println(Arrays.toString(pos));
}
}
is there a way to optimize this? what if number of balls is 10^9 and number of holes is 10^9?
nh=int(input())
h=list(map(int,input().split()))
nb=int(input())
b=list(map(int,input().split()))
d={}
for i in range(len(h)-1,-1,-1):
d[h[i]]=i+1
k=list(d)
for i in b:
for j in k:
if i0:
print(len(k)-k.index(j))
d[j]-=1
break
else:
print(0)
** if i0: **
if i0:
N = int(input())
holes = list(map(int, input().split()))
M = int(input())
balls = list(map(int, input().split()))
dict = {}
for i in range(len(holes)):
dict[i] = [0, i + 1]
for i in range(len(balls)):
j = -1
checker = 0
while j >= – len(holes):
if balls[i] <= holes[j] and dict[len(holes) + j][0] < dict[len(holes) + j][1]:
print(len(holes) + j + 1, end=" ")
dict[len(holes) + j][0] += 1
checker = 1
break
j -= 1
if checker == 0:
print(0, end=" ")
N = int(input())
holes = list(map(int, input().split()))
M = int(input())
balls = list(map(int, input().split()))
dict = {}
for i in range(len(holes)):
dict[i] = [0, i + 1]
for i in range(len(balls)):
j = -1
checker = 0
while j >= – len(holes):
if balls[i] <= holes[j] and dict[len(holes) + j][0] < dict[len(holes) + j][1]:
print(len(holes) + j + 1, end=" ")
dict[len(holes) + j][0] += 1
checker = 1
break
j -= 1
if checker == 0:
print(0, end=" ")