Dadas dos arrays A[] y B[] . Donde el tamaño de A[] representa el número de filas y A[i] representa el número de casillas en la i -ésima fila. La array B[] representa una array de bolas donde B[i] representa un número en la bola. Dado que la bola i (que tiene el valor B[i]) se colocará en una caja cuya posición desde el principio es B[i] (fila mayor). La tarea es encontrar la fila y la columna de las casillas correspondientes a cada B[i] .
Ejemplos:
Entrada: A[] = {2, 3, 4, 5}, B[] = {1, 4, 6, 3}
Salida:
1, 1
2, 2
3, 1
2, 1
B[0] = 1, por lo tanto, la posición del cuadro será la primera fila, la primera columna
B[1] = 4, por lo tanto, la posición del cuadro será la segunda fila, la segunda columna
B[2] = 6, por lo tanto, la posición del cuadro será la tercera fila, la primera columna
B[3] = 3 , por lo tanto, la posición del cuadro será la segunda fila, la primera columna
Entrada: A[] = {2, 2, 2, 2}, B[] = {1, 2, 3, 4}
Salida:
1, 1
1, 2
2, 1
2, 2
Enfoque: Según el enunciado del problema, en la 1.ª fila A[0] hay una cantidad de cajas colocadas de manera similar en la 2.ª fila A[1] hay una cantidad de cajas. Entonces, en caso de que se vaya a colocar una bola en cualquier casilla de la segunda fila, su valor debe ser mayor que A[0] . Por lo tanto, para encontrar la posición real del cuadro donde se colocará una bola B[i] , primero encuentre la suma acumulativa de la array A[] y luego encuentre la posición del elemento en la array de suma acumulativa que es solo mayor que B [i] , ese será el número de fila y para encontrar el número de cuadro en esa fila en particular, busque el valor de B[i]: valor en la array acumulativa que es más pequeño que B[i].
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the position of each boxes
// where a ball has to be placed
void printPosition(int A[], int B[], int sizeOfA, int sizeOfB)
{
// Find the cumulative sum of array A[]
for (int i = 1; i < sizeOfA; i++)
A[i] += A[i - 1];
// Find the position of box for each ball
for (int i = 0; i < sizeOfB; i++) {
// Row number
int row = lower_bound(A, A + sizeOfA, B[i]) - A;
// Column (position of box in particular row)
int boxNumber = (row >= 1) ? B[i] - A[row - 1] : B[i];
// Row + 1 denotes row if indexing of array start from 1
cout << row + 1 << ", " << boxNumber << "\n";
}
}
// Driver code
int main()
{
int A[] = { 2, 2, 2, 2 };
int B[] = { 1, 2, 3, 4 };
int sizeOfA = sizeof(A) / sizeof(A[0]);
int sizeOfB = sizeof(B) / sizeof(B[0]);
printPosition(A, B, sizeOfA, sizeOfB);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to print the position of each boxes
// where a ball has to be placed
static void printPosition(int A[], int B[],
int sizeOfA, int sizeOfB)
{
// Find the cumulative sum of array A[]
for (int i = 1; i < sizeOfA; i++)
{
A[i] += A[i - 1];
}
// Find the position of box for each ball
for (int i = 0; i < sizeOfB; i++)
{
// Row number
int row = lower_bound(A, 0, A.length, B[i]);
// Column (position of box in particular row)
int boxNumber = (row >= 1) ? B[i] - A[row - 1] : B[i];
// Row + 1 denotes row if indexing of array start from 1
System.out.print(row + 1 + ", " + boxNumber + "\n");
}
}
private static int lower_bound(int[] a, int low, int high, int element)
{
while (low < high)
{
int middle = low + (high - low) / 2;
if (element > a[middle])
{
low = middle + 1;
}
else
{
high = middle;
}
}
return low;
}
// Driver code
public static void main(String[] args)
{
int A[] = {2, 2, 2, 2};
int B[] = {1, 2, 3, 4};
int sizeOfA = A.length;
int sizeOfB = B.length;
printPosition(A, B, sizeOfA, sizeOfB);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 implementation of the approach import bisect # Function to print the position of each boxes # where a ball has to be placed def printPosition(A, B, sizeOfA, sizeOfB): # Find the cumulative sum of array A[] for i in range(1, sizeOfA): A[i] += A[i - 1] # Find the position of box for each ball for i in range(sizeOfB): # Row number row = bisect.bisect_left(A, B[i]) # Column (position of box in particular row) if row >= 1: boxNumber = B[i] - A[row - 1] else: boxNumber = B[i] # Row + 1 denotes row # if indexing of array start from 1 print(row + 1, ",", boxNumber) # Driver code A = [2, 2, 2, 2] B = [1, 2, 3, 4] sizeOfA = len(A) sizeOfB = len(B) printPosition(A, B, sizeOfA, sizeOfB) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to print the position of each boxes
// where a ball has to be placed
static void printPosition(int []A, int []B,
int sizeOfA, int sizeOfB)
{
// Find the cumulative sum of array A[]
for (int i = 1; i < sizeOfA; i++)
{
A[i] += A[i - 1];
}
// Find the position of box for each ball
for (int i = 0; i < sizeOfB; i++)
{
// Row number
int row = lower_bound(A, 0, A.Length, B[i]);
// Column (position of box in particular row)
int boxNumber = (row >= 1) ? B[i] - A[row - 1] : B[i];
// Row + 1 denotes row if indexing of array start from 1
Console.WriteLine(row + 1 + ", " + boxNumber + "\n");
}
}
private static int lower_bound(int[] a, int low,
int high, int element)
{
while (low < high)
{
int middle = low + (high - low) / 2;
if (element > a[middle])
{
low = middle + 1;
}
else
{
high = middle;
}
}
return low;
}
// Driver code
static public void Main ()
{
int []A = {2, 2, 2, 2};
int []B = {1, 2, 3, 4};
int sizeOfA = A.Length;
int sizeOfB = B.Length;
printPosition(A, B, sizeOfA, sizeOfB);
}
}
// This code has been contributed by Tushil.
PHP
<?php
// function to find the lower bound
function lower_bound($A, $valueTosearch)
{
$row = 0;
foreach ($A as $key=>$value)
{
if($valueTosearch <= $value)
return $row;
$row++;
}
return $row+1;
}
// Function to print the position of each boxes
// where a ball has to be placed
function printPosition($A, $B, $sizeOfA, $sizeOfB)
{
// Find the cumulative sum of array A[]
for ($i = 1; $i <$sizeOfA; $i++)
$A[$i] += $A[$i - 1];
// Find the position of box for each ball
for ($i = 0; $i < $sizeOfB; $i++)
{
// Row number
$row = lower_bound($A, $B[$i]) ;
// Column (position of box in particular row)
$boxNumber = ($row >= 1) ? $B[$i] - $A[$row - 1] : $B[$i];
// Row + 1 denotes row if indexing of array start from 1
print_r($row+1 .", ".$boxNumber);
echo "\n";
}
}
// Driver code
$A = array(2, 2, 2, 2 );
$B = array( 1, 2, 3, 4 );
$sizeOfA =count($A);
$sizeOfB = count($B);
printPosition($A, $B, $sizeOfA, $sizeOfB);
// This code is contributed by Shivam.Pradhan
?>
Javascript
<script>
// javascript implementation of the approach
// Function to print the position of each boxes
// where a ball has to be placed
function printPosition(A , B , sizeOfA , sizeOfB) {
// Find the cumulative sum of array A
for (i = 1; i < sizeOfA; i++) {
A[i] += A[i - 1];
}
// Find the position of box for each ball
for (i = 0; i < sizeOfB; i++) {
// Row number
var row = lower_bound(A, 0, A.length, B[i]);
// Column (position of box in particular row)
var boxNumber = (row >= 1) ? B[i] - A[row - 1] : B[i];
// Row + 1 denotes row if indexing of array start from 1
document.write(row + 1 + ", " + boxNumber + "<br/>");
}
}
function lower_bound(a , low , high , element) {
while (low < high) {
var middle = low + (high - low) / 2;
if (element > a[middle]) {
low = middle + 1;
} else {
high = middle;
}
}
return low;
}
// Driver code
var A = [ 2, 2, 2, 2 ];
var B = [ 1, 2, 3, 4 ];
var sizeOfA = A.length;
var sizeOfB = B.length;
printPosition(A, B, sizeOfA, sizeOfB);
// This code contributed by gauravrajput1
</script>
1, 1 1, 2 2, 1 2, 2
Complejidad de tiempo: O (tamaño de A + tamaño de B)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA