Hay N estaciones en línea recta, cada una de ellas tiene una potencia de radiación no negativa. Cada estación puede aumentar la potencia de radiación de sus estaciones vecinas de la siguiente manera, la
estación i con potencia de radiación R aumentará (i – 1) la radiación de la estación en R – 1 , (i – 2) la radiación de la estación en R – 2 , así sucesivamente… y (i + 1) la radiación de la estación por R – 1 , (i + 2) la radiación de la estación por R – 2 , así sucesivamente… hasta que la potencia de radiación efectiva sea positiva.
La tarea es encontrar las radiaciones finales para cada una de las estaciones.
Ejemplos:
Entrada: arr[] = {1, 2, 3}
Salida: 3 4 4
La nueva radiación será {1 + (2 – 1) + (3 – 2), 2 + (1 – 1) + (3 – 1 ), 3 + (2 – 1)}
es decir, {3, 4, 4}
Entrada: arr[] = {9, 87, 55, 2, 1}
Salida: 148 149 149 147 144
Entrada: arr[] = {7 , 9, 12, 2, 5}
Salida: 26 28 29 28 25
Enfoque ingenuo: para cada estación, aumento la radiación de las estaciones vecinas como se mencionó anteriormente hasta que la radiación efectiva se vuelve negativa.
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 final radiations
void print(int rStation[], int n)
{
for (int i = 1; i <= n; i++)
cout << rStation[i] << " ";
cout << endl;
}
// Function to create the array of the
// resultant radiations
void radiated_Station(int station[], int n)
{
// Resultant radiations
int rStation[n + 1];
// Initialize resultant array with 0
memset(rStation, 0, sizeof(rStation));
for (int i = 1; i <= n; i++) {
// Declaring index counter for left
// and right radiation
int li = i - 1, ri = i + 1;
// Effective radiation for left
// and right case
int lRad = station[i] - 1, rRad = station[i] - 1;
// Radiation for i-th station
rStation[i] += station[i];
// Radiation increment for left stations
while (li >= 1 && lRad >= 1) {
rStation[li--] += lRad--;
}
// Radiation increment for right stations
while (ri <= n && rRad >= 1) {
rStation[ri++] += rRad--;
}
}
// Print the resultant radiation
// for each of the stations
print(rStation, n);
}
// Driver code
int main()
{
// 1-based indexing
int station[] = { 0, 7, 9, 12, 2, 5 };
int n = (sizeof(station) / sizeof(station[0])) - 1;
radiated_Station(station, n);
return 0;
}
Java
// Java implementation of the approach
class GFG {
// Function to print the final radiations
static void print(int rStation[], int n)
{
for (int i = 1; i <= n; i++)
System.out.print(rStation[i] + " ");
System.out.println("");
}
// Function to create the array of the
// resultant radiations
static void radiated_Station(int station[], int n)
{
// Resultant radiations
int rStation[] = new int[n + 1];
for (int i = 1; i <= n; i++) {
// Declaring index counter for left
// and right radiation
int li = i - 1, ri = i + 1;
// Effective radiation for left
// and right case
int lRad = station[i] - 1, rRad = station[i] - 1;
// Radiation for i-th station
rStation[i] += station[i];
// Radiation increment for left stations
while (li >= 1 && lRad >= 1) {
rStation[li--] += lRad--;
}
// Radiation increment for right stations
while (ri <= n && rRad >= 1) {
rStation[ri++] += rRad--;
}
}
// Print the resultant radiation
// for each of the stations
print(rStation, n);
}
// Driver code
public static void main(String[] args)
{
// 1-based indexing
int station[] = { 0, 7, 9, 12, 2, 5 };
int n = station.length - 1;
radiated_Station(station, n);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python 3 implementation of the approach
# Function to print the final radiations
def printf(rStation, n):
for i in range(1, n + 1, 1):
print(rStation[i], end = " ")
print("\n", end = " ")
# Function to create the array of the
# resultant radiations
def radiated_Station(station, n):
# Resultant radiations
rStation = [0 for i in range(n + 1)]
for i in range(1, n + 1):
# Declaring index counter for left
# and right radiation
li = i - 1
ri = i + 1
# Effective radiation for left
# and right case
lRad = station[i] - 1
rRad = station[i] - 1
# Radiation for i-th station
rStation[i] += station[i]
# Radiation increment for left stations
while (li >= 1 and lRad >= 1):
rStation[li] += lRad
lRad -= 1
li -= 1
# Radiation increment for right stations
while (ri <= n and rRad >= 1):
rStation[ri] += rRad
rRad -= 1
ri += 1
# Print the resultant radiation
# for each of the stations
printf(rStation, n)
# Driver code
if __name__ == '__main__':
# 1-based indexing
station = [0, 7, 9, 12, 2, 5]
n = len(station) - 1
radiated_Station(station, n)
# This code is contributed by
# Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG {
// Function to print the final radiations
static void print(int[] rStation, int n)
{
for (int i = 1; i <= n; i++)
Console.Write(rStation[i] + " ");
Console.WriteLine("");
}
// Function to create the array of the
// resultant radiations
static void radiated_Station(int[] station, int n)
{
// Resultant radiations
int[] rStation = new int[n + 1];
for (int i = 1; i <= n; i++) {
// Declaring index counter for left
// and right radiation
int li = i - 1, ri = i + 1;
// Effective radiation for left
// and right case
int lRad = station[i] - 1, rRad = station[i] - 1;
// Radiation for i-th station
rStation[i] += station[i];
// Radiation increment for left stations
while (li >= 1 && lRad >= 1) {
rStation[li--] += lRad--;
}
// Radiation increment for right stations
while (ri <= n && rRad >= 1) {
rStation[ri++] += rRad--;
}
}
// Print the resultant radiation
// for each of the stations
print(rStation, n);
}
// Driver code
public static void Main(String[] args)
{
// 1-based indexing
int[] station = { 0, 7, 9, 12, 2, 5 };
int n = station.Length - 1;
radiated_Station(station, n);
}
}
/* This code contributed by PrinciRaj1992 */
PHP
<?php
// PHP implementation of the approach
// Function to print the final radiations
function print_radiation($rStation, $n)
{
for ($i = 1; $i <= $n; $i++)
{
echo $rStation[$i]." ";
}
echo "\n";
}
// Function to create the array of the
// resultant radiations
function radiated_Station($station, $n)
{
// Resultant radiations
$rStation = array();
// Initialize resultant array with 0
$rStation = array_fill(0, $n+1, 0);
for ($i = 1; $i <= $n; $i++) {
// Declaring index counter for left
// and right radiation
$li = $i - 1;
$ri = $i + 1;
// Effective radiation for left
// and right case
$lRad = $station[$i] - 1;
$rRad = $station[$i] - 1;
// Radiation for i-th station
$rStation[$i] += $station[$i];
// Radiation increment for left stations
while ($li >= 1 && $lRad >= 1) {
$rStation[$li--] += $lRad--;
}
// Radiation increment for right stations
while ($ri <= $n && $rRad >= 1) {
$rStation[$ri++] += $rRad--;
}
}
// Print the resultant radiation
// for each of the stations
print_radiation($rStation, $n);
}
// Driver code
// 1-based indexing
$station = array( 0, 7, 9, 12, 2, 5 );
$n = (sizeof($station) / sizeof($station[0])) - 1;
radiated_Station($station, $n);
//code contributed by Shashank_Sharma
?>
Javascript
<script>
// javascript implementation of the approach
// Function to print the final radiations
function print( rStation, n)
{
for (var i = 1; i <= n; i++)
document.write(rStation[i] + " ");
document.write("<br>");
}
// Function to create the array of the
// resultant radiations
function radiated_Station(station, n)
{
// Resultant radiations
var rStation = [] ;
rStation.length = 6 ;
rStation.fill(0)
for (var i = 1; i <= n; i++) {
// Declaring index counter for left
// and right radiation
var li = i - 1, ri = i + 1;
// Effective radiation for left
// and right case
var lRad = station[i] - 1, rRad = station[i] - 1;
// Radiation for i-th station
rStation[i] += station[i];
// Radiation increment for left stations
while (li >= 1 && lRad >= 1) {
rStation[li--] += lRad--;
}
// Radiation increment for right stations
while (ri <= n && rRad >= 1) {
rStation[ri++] += rRad--;
}
}
// Print the resultant radiation
// for each of the stations
print(rStation, n);
}
// Driver code
// 1-based indexing
var station = [ 0, 7, 9, 12, 2, 5 ]
var n = station.length - 1;
radiated_Station(station, n);
// This code is contributed by bunnyram19.
</script>
Producción:
26 28 29 28 25
Complejidad temporal: O(n*n)
Espacio Auxiliar: O(n)
Enfoque eficiente:
- Para cada estación, calcularemos los efectos de radiación de los extremos izquierdo y derecho por separado.
- Luego, dos iteraciones, una desde la izquierda y otra desde la derecha, construirán dos arrays.
- La iteración de la izquierda construirá el array left_Rad[] que está formado por la radiación efectiva izquierda de cada estación y right_Rad[] se construirá mediante la iteración de la derecha.
- Para la estación i , supongamos que se efectuará por m número de radiación izquierda de estaciones y n número de radiación derecha de estaciones. necesitamos otras arrays lCount[] para los valores m y rcount[] para los valores n .
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 final radiations
void print(int rStation[], int n)
{
for (int i = 1; i <= n; i++)
cout << rStation[i] << " ";
cout << endl;
}
// Function to create the array of the
// resultant radiations
void radiated_Station(int station[], int n)
{
// Resultant radiations
int rStation[n + 1];
int left_Rad[n + 2], right_Rad[n + 2];
// Frequency of stations that affect each station
int lCount[n + 2], rCount[n + 2];
// Initialization of the arrays with 0
memset(left_Rad, 0, sizeof(left_Rad));
memset(right_Rad, 0, sizeof(right_Rad));
memset(lCount, 0, sizeof(lCount));
memset(rCount, 0, sizeof(rCount));
for (int i = 1; i < n + 1; i++) {
// Radiation of station i
int Rad = station[i];
// Left and right most position of radiation
// for station i, index should be
// in between the station range
int li = max(1, i - Rad + 1), ri = min(n, Rad - 1 + i);
// At station 1 radiation effect
// for station i
int at1 = max(0, Rad - i + 1);
left_Rad[1] += at1;
// While iterating from left avoid
// effective radiation at right
left_Rad[i + 1] -= Rad;
// At station n radiation effect
// for station i
int atn = max(0, Rad - n + i);
right_Rad[n] += atn;
// While iterating from right avoid
// effective radiation at left
right_Rad[i - 1] -= Rad;
// Left and right most position
// where station i effects
lCount[li]++;
rCount[ri]++;
// Avoiding right radiation for
// left iteration and vice-versa
lCount[i + 1]--;
rCount[i - 1]--;
}
// Left iteration
for (int i = 1; i <= n; i++) {
lCount[i] += lCount[i - 1];
// Total radiations at index 1 already counted
if (i > 1)
left_Rad[i] += left_Rad[i - 1] + lCount[i];
}
// Right iteration
for (int i = n; i >= 1; i--) {
rCount[i] += rCount[i + 1];
// Total radiations at index n already counted
if (i < n)
right_Rad[i] += right_Rad[i + 1] + rCount[i];
}
// Final iteration that creates
// the resultant radiation
for (int i = 1; i <= n; i++) {
// Added extra value in each index
rStation[i] = left_Rad[i] + right_Rad[i] - station[i];
}
// Print the resultant radiation
// for each of the stations
print(rStation, n);
}
// Driver code
int main()
{
// 1-based indexing
int station[] = { 0, 7, 9, 12, 2, 5 };
int n = (sizeof(station) / sizeof(station[0])) - 1;
radiated_Station(station, n);
return 0;
}
Java
// Java implementation of the approach
class GFG {
// Function to print the final radiations
static void print(int rStation[], int n)
{
for (int i = 1; i <= n; i++)
System.out.print(rStation[i] + " ");
System.out.println("");
}
// Function to create the array of the
// resultant radiations
static void radiated_Station(int station[], int n)
{
// Resultant radiations
int[] rStation = new int[n + 1];
int[] left_Rad = new int[n + 2];
int[] right_Rad = new int[n + 2];
// Frequency of stations that affect each station
int[] lCount = new int[n + 2];
int[] rCount = new int[n + 2];
for (int i = 1; i < n + 1; i++) {
// Radiation of station i
int Rad = station[i];
// Left and right most position of radiation
// for station i, index should be
// in between the station range
int li = Math.max(1, i - Rad + 1), ri = Math.min(n, Rad - 1 + i);
// At station 1 radiation effect
// for station i
int at1 = Math.max(0, Rad - i + 1);
left_Rad[1] += at1;
// While iterating from left avoid
// effective radiation at right
left_Rad[i + 1] -= Rad;
// At station n radiation effect
// for station i
int atn = Math.max(0, Rad - n + i);
right_Rad[n] += atn;
// While iterating from right avoid
// effective radiation at left
right_Rad[i - 1] -= Rad;
// Left and right most position
// where station i effects
lCount[li]++;
rCount[ri]++;
// Avoiding right radiation for
// left iteration and vice-versa
lCount[i + 1]--;
rCount[i - 1]--;
}
// Left iteration
for (int i = 1; i <= n; i++) {
lCount[i] += lCount[i - 1];
// Total radiations at index 1 already counted
if (i > 1)
left_Rad[i] += left_Rad[i - 1] + lCount[i];
}
// Right iteration
for (int i = n; i >= 1; i--) {
rCount[i] += rCount[i + 1];
// Total radiations at index n already counted
if (i < n)
right_Rad[i] += right_Rad[i + 1] + rCount[i];
}
// Final iteration that creates
// the resultant radiation
for (int i = 1; i <= n; i++) {
// Added extra value in each index
rStation[i] = left_Rad[i] + right_Rad[i] - station[i];
}
// Print the resultant radiation
// for each of the stations
print(rStation, n);
}
// Driver code
public static void main(String[] args)
{
// 1-based indexing
int station[] = { 0, 7, 9, 12, 2, 5 };
int n = station.length - 1;
radiated_Station(station, n);
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Function to print the final radiations def print_array(rStation, n): for i in range(1, n + 1): print(rStation[i], end = " ") # Function to create the array of the # resultant radiations def radiated_Station(station, n): # Resultant radiations rStation = [0] * (n + 1) left_Rad = [0] * (n + 2) right_Rad = [0] * (n + 2) # Frequency of stations that # affect each station lCount = [0] * (n + 2) rCount = [0] * (n + 2) for i in range(1, n + 1): # Radiation of station i Rad = station[i] # Left and right most position of # radiation for station i, index # should be in between the station range li = max(1, i - Rad + 1) ri = min(n, Rad - 1 + i); # At station 1 radiation effect # for station i at1 = max(0, Rad - i + 1) left_Rad[1] += at1; # While iterating from left avoid # effective radiation at right left_Rad[i + 1] -= Rad; # At station n radiation effect # for station i atn = max(0, Rad - n + i); right_Rad[n] += atn # While iterating from right avoid # effective radiation at left right_Rad[i - 1] -= Rad # Left and right most position # where station i effects lCount[li] += 1 rCount[ri] += 1 # Avoiding right radiation for # left iteration and vice-versa lCount[i + 1] -= 1 rCount[i - 1] -= 1 # Left iteration for i in range(1, n + 1): lCount[i] += lCount[i - 1] # Total radiations at index 1 # already counted if (i > 1): left_Rad[i] += (left_Rad[i - 1] + lCount[i]) # Right iteration for i in range(n, 0, -1): rCount[i] += rCount[i + 1] # Total radiations at index n already counted if (i < n): right_Rad[i] += (right_Rad[i + 1] + rCount[i]) # Final iteration that creates # the resultant radiation for i in range(1, n + 1): # Added extra value in each index rStation[i] = (left_Rad[i] + right_Rad[i] - station[i]) # Print the resultant radiation # for each of the stations print_array(rStation, n) # Driver code if __name__ == "__main__": # 1-based indexing station = [ 0, 7, 9, 12, 2, 5 ] n = len(station) - 1 radiated_Station(station, n) # This code is contributed by chitranayal
C#
// C# implementation of the approach
using System;
class GFG {
// Function to print the final radiations
static void print(int[] rStation, int n)
{
for (int i = 1; i <= n; i++)
Console.Write(rStation[i] + " ");
Console.WriteLine("");
}
// Function to create the array of the
// resultant radiations
static void radiated_Station(int[] station, int n)
{
// Resultant radiations
int[] rStation = new int[n + 1];
int[] left_Rad = new int[n + 2];
int[] right_Rad = new int[n + 2];
// Frequency of stations that affect each station
int[] lCount = new int[n + 2];
int[] rCount = new int[n + 2];
for (int i = 1; i < n + 1; i++) {
// Radiation of station i
int Rad = station[i];
// Left and right most position of radiation
// for station i, index should be
// in between the station range
int li = Math.Max(1, i - Rad + 1),
ri = Math.Min(n, Rad - 1 + i);
// At station 1 radiation effect
// for station i
int at1 = Math.Max(0, Rad - i + 1);
left_Rad[1] += at1;
// While iterating from left avoid
// effective radiation at right
left_Rad[i + 1] -= Rad;
// At station n radiation effect
// for station i
int atn = Math.Max(0, Rad - n + i);
right_Rad[n] += atn;
// While iterating from right avoid
// effective radiation at left
right_Rad[i - 1] -= Rad;
// Left and right most position
// where station i effects
lCount[li]++;
rCount[ri]++;
// Avoiding right radiation for
// left iteration and vice-versa
lCount[i + 1]--;
rCount[i - 1]--;
}
// Left iteration
for (int i = 1; i <= n; i++) {
lCount[i] += lCount[i - 1];
// Total radiations at index 1 already counted
if (i > 1)
left_Rad[i] += left_Rad[i - 1] + lCount[i];
}
// Right iteration
for (int i = n; i >= 1; i--) {
rCount[i] += rCount[i + 1];
// Total radiations at index n already counted
if (i < n)
right_Rad[i] += right_Rad[i + 1] + rCount[i];
}
// Final iteration that creates
// the resultant radiation
for (int i = 1; i <= n; i++) {
// Added extra value in each index
rStation[i] = left_Rad[i] + right_Rad[i] - station[i];
}
// Print the resultant radiation
// for each of the stations
print(rStation, n);
}
// Driver code
public static void Main(String[] args)
{
// 1-based indexing
int[] station = { 0, 7, 9, 12, 2, 5 };
int n = station.Length - 1;
radiated_Station(station, n);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript implementation of the approach
// Function to print the final radiations
function print(rStation, n)
{
for (let i = 1; i <= n; i++)
document.write(rStation[i] + " ");
document.write("<br>");
}
// Function to create the array of the
// resultant radiations
function radiated_Station(station, n)
{
// Resultant radiations
let rStation = new Array(n + 1);
let left_Rad = new Array(n + 2).fill(0);
let right_Rad = new Array(n + 2).fill(0);
// Frequency of stations that affect each station
let lCount = new Array(n + 2).fill(0);
let rCount = new Array(n + 2).fill(0);
for (let i = 1; i < n + 1; i++) {
// Radiation of station i
let Rad = station[i];
// Left and right most position of radiation
// for station i, index should be
// in between the station range
let li = Math.max(1, i - Rad + 1);
let ri = Math.min(n, Rad - 1 + i);
// At station 1 radiation effect
// for station i
let at1 = Math.max(0, Rad - i + 1);
left_Rad[1] += at1;
// While iterating from left avoid
// effective radiation at right
left_Rad[i + 1] -= Rad;
// At station n radiation effect
// for station i
let atn = Math.max(0, Rad - n + i);
right_Rad[n] += atn;
// While iterating from right avoid
// effective radiation at left
right_Rad[i - 1] -= Rad;
// Left and right most position
// where station i effects
lCount[li]++;
rCount[ri]++;
// Avoiding right radiation for
// left iteration and vice-versa
lCount[i + 1]--;
rCount[i - 1]--;
}
// Left iteration
for (let i = 1; i <= n; i++) {
lCount[i] += lCount[i - 1];
// Total radiations at index 1 already counted
if (i > 1)
left_Rad[i] += left_Rad[i - 1] + lCount[i];
}
// Right iteration
for (let i = n; i >= 1; i--) {
rCount[i] += rCount[i + 1];
// Total radiations at index n already counted
if (i < n)
right_Rad[i] += right_Rad[i + 1] + rCount[i];
}
// Final iteration that creates
// the resultant radiation
for (let i = 1; i <= n; i++) {
// Added extra value in each index
rStation[i] = left_Rad[i] +
right_Rad[i] - station[i];
}
// Print the resultant radiation
// for each of the stations
print(rStation, n);
}
// Driver code
// 1-based indexing
let station = [ 0, 7, 9, 12, 2, 5 ];
let n = station.length - 1;
radiated_Station(station, n);
</script>
Producción:
26 28 29 28 25
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por sayantan_das24 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA