Dadas dos arrays de H[] y B[] que consisten en N y M enteros respectivamente, que denotan el diámetro de los agujeros y las bolas respectivamente. Se hace rodar un número M de bolas de A a B sobre una superficie inclinada con N agujeros, cada uno con diferente profundidad, como se muestra en la siguiente figura:
La tarea es encontrar la posición final de cada bola en el orden de la bola lanzada considerando lo siguiente:
- Una bola caerá en un hoyo si su diámetro es menor o igual al diámetro del hoyo.
- Un hoyo H i se llenará si en él caen i números de bolas.
- Si un hoyo está lleno, no caen más bolas en él.
- Una bola llegará a B desde A , si y solo si no cae en ninguno de los agujeros.
- Si una bola está en el hoyo Pi , entonces su posición es i . Si una pelota llegó al punto inferior B, entonces tome su posición como 0 .
Ejemplos:
Entrada: H[] = {21, 3, 6}, B[] = {20, 15, 5, 7, 10, 4, 2, 1, 3, 6, 8}
Salida: 1 0 3 0 0 3 3 2 2 0 0
Explicación:
La bola de diámetro 20 caerá en el agujero H 1 y el agujero H 1 se llenará.
Las bolas con diámetro 15, 7 y 10 llegarán al fondo, ya que el agujero H 1 está lleno y los diámetros de los agujeros H 2 y H 3 son menores que los diámetros de las bolas.
Bolas con diámetros 5, 4 y 2 caerán en el agujero H 3 .
La bola de diámetro 1 caerá en el agujero H 2 porque el agujero H 3 ya está lleno.
Bola con diámetro 3 caerá en el agujero H 2 .
Bolas con diámetros 6 y 8 llegarán al punto inferior B.
La posición de la bola 20 es 1 porque está en el agujero H 1 .
Las posiciones de la bola 15, 7, 10, 3, 6 y 8 son 0 porque llegaron al punto inferior B.
Por lo tanto, las bolas con diámetro 5, 4 y 2 están en el 3er orificio H 3 , la bola con diámetro 1 y 3 están en el segundo agujero H 2 .Entrada: H[] = {20, 15, 10, 5, 25}, B[] = {5, 10, 15, 20, 25, 30, 4, 9, 14, 19}
Salida: 5 5 5 5 5 0 4 3 2 1
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una posición de array [] de tamaño N para almacenar la posición final de cada bola y una profundidad de array [] de tamaño N para almacenar la capacidad de cada hoyo.
- Itere sobre el rango [1, N] usando la variable i y establezca la profundidad inicial [i] del agujero [i] en i+1 .
- Recorra el arreglo ball[] usando la variable i y haga lo siguiente:
- Inicialice el indicador en Falso.
- Iterar sobre la array hole[] usando la variable j en orden inverso.
- Compruebe si el diámetro del agujero es mayor o igual que el de la bola, es decir, agujero[j] ≥ bola[i] , y si ese agujero no está lleno, es decir, profundidad [j] ≤ j entonces, coloque el bola en ese hoyo agregando j + 1 en la array position[] e incrementando la profundidad del hoyo en 1 y marcando igual a True
- salir del bucle .
- Si la bola no cabe en ningún hoyo (ha llegado al final de la pendiente), la bandera será Falso, luego agregue 0 en la array position[] .
- Después de los pasos anteriores, imprima el valor almacenado en la posición de la array [] como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to find and print the final
// position of balls
vector<int> ballPositionFinder(vector<int>holes,vector<int>balls){
// Array of zero equal to length of holes array
// to store the no. of balls in the hole
vector<int>depth(holes.size(),0);
// Stores the positions of balls
vector<int>positions;
// Iterate through balls array
// and holes array in reverse order.
for(int i : balls){
// Initialize flag equal to false
bool flag = false;
vector<int>array;
for(int i=0;i<holes.size();i++){
array.push_back(i);
}
reverse(array.begin(),array.end());
for(auto j : array)
{
// Check if the diameter of ball is less than the
// diameter of hole and depth is less than the index.
if(i <= holes[j] && depth[j] <= j)
{
// If the condition is true push the position
// for ball in position array and increment depth of hole by 1.
positions.push_back(j + 1);
depth[j] += 1;
// Here the ball will fall into the hole
// so make the flag True and break the loop.
flag = true;
break;
}
}
// Check if the ball has reached the bottom
// if the ball reaches bottom flag will remain false
// so then push 0 to the position array.
if(flag == false)
positions.push_back(0);
}
return positions;
}
// Driver Code
int main()
{
vector<int>holes = {21, 3, 6};
vector<int>balls = {20, 15, 5, 7, 10, 4, 2, 1, 3, 6, 8};
// Function Call
vector<int> output = ballPositionFinder(holes, balls);
for(auto i : output)
cout<<i<<" ";
}
// This code is contributed by shinjanpatra
Python3
# Python program for the above approach # Function to find and print the final # position of balls def ballPositionFinder(holes, balls): # Array of zero equal to length of holes array # to store the no. of balls in the hole depth = [0 for i in range(len(holes))] # Stores the positions of balls positions = [] # Iterate through balls array # and holes array in reverse order. for i in balls: # Initialize flag equal to false flag = False for j in reversed(range(len(holes))): # Check if the diameter of ball is less than the # diameter of hole and depth is less than the index. if i <= holes[j] and depth[j] <= j: # If the condition is true append the position # for ball in position array and increment depth of hole by 1. positions.append(j+1) depth[j] += 1 # Here the ball will fall into the hole # so make the flag True and break the loop. flag = True break # Check if the ball has reached the bottom # if the ball reaches bottom flag will remain false # so then append 0 to the position array. if flag == False: positions.append(0) return positions # Driver Code if __name__ == "__main__": holes = [21, 3, 6] balls = [20, 15, 5, 7, 10, 4, 2, 1, 3, 6, 8] # Function Call output = ballPositionFinder(holes, balls) for i in output: print(i, end=" ")
Javascript
<script>
// JavaScript program for the above approach
// Function to find and print the final
// position of balls
function ballPositionFinder(holes, balls){
// Array of zero equal to length of holes array
// to store the no. of balls in the hole
let depth = new Array(holes.length).fill(0)
// Stores the positions of balls
let positions = []
// Iterate through balls array
// and holes array in reverse order.
for(let i of balls){
// Initialize flag equal to false
let flag = false
let array = []
for(let i=0;i<holes.length;i++){
array.push(i)
}
array.reverse()
for(let j of array)
{
// Check if the diameter of ball is less than the
// diameter of hole and depth is less than the index.
if(i <= holes[j] && depth[j] <= j)
{
// If the condition is true push the position
// for ball in position array and increment depth of hole by 1.
positions.push(j + 1)
depth[j] += 1
// Here the ball will fall into the hole
// so make the flag True and break the loop.
flag = true
break
}
}
// Check if the ball has reached the bottom
// if the ball reaches bottom flag will remain false
// so then push 0 to the position array.
if(flag == false)
positions.push(0)
}
return positions
}
// Driver Code
let holes = [21, 3, 6]
let balls = [20, 15, 5, 7, 10, 4,
2, 1, 3, 6, 8]
// Function Call
let output = ballPositionFinder(holes, balls)
for(let i of output)
document.write(i," ")
// This code is contributed by shinjanpatra
</script>
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
// Java program for the above approach
// Function to find and print the final
// position of balls
static ArrayList<Integer> ballPositionFinder(int[] holes,int[] balls){
// Array of zero equal to length of holes array
// to store the no. of balls in the hole
int[] depth = new int[holes.length];
Arrays.fill(depth, 0);
// Stores the positions of balls
ArrayList<Integer> positions = new ArrayList<>();
// Iterate through balls array
// and holes array in reverse order.
for(int i : balls){
// Initialize flag equal to false
boolean flag = false;
ArrayList<Integer> array = new ArrayList<>();
for(int j=0;j<holes.length;j++){
array.add(j);
}
Collections.reverse(array);
for(int j : array)
{
// Check if the diameter of ball is less than the
// diameter of hole and depth is less than the index.
if(i <= holes[j] && depth[j] <= j)
{
// If the condition is true push the position
// for ball in position array and increment depth of hole by 1.
positions.add(j + 1);
depth[j] += 1;
// Here the ball will fall into the hole
// so make the flag True and break the loop.
flag = true;
break;
}
}
// Check if the ball has reached the bottom
// if the ball reaches bottom flag will remain false
// so then push 0 to the position array.
if(flag == false)
positions.add(0);
}
return positions;
}
// Driver Code
public static void main(String args[])
{
int[] holes = {21, 3, 6};
int[] balls = {20, 15, 5, 7, 10, 4, 2, 1, 3, 6, 8};
// Function Call
ArrayList<Integer> output = ballPositionFinder(holes, balls);
for(int i : output)
System.out.print(i + " ");
}
}
// code is contributed by shinjanpatra
Producción
1 0 3 0 0 3 3 2 2 0 0
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sherwinfernandes y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA