Número mínimo de bombas

Hay extraterrestres en n edificios (mínimo de 1 en cada uno) y tienes que matarlos a todos un número mínimo de bombardeos. Los edificios están numerados como 1 – n. Los extraterrestres en un edificio bombardeado resultan heridos en el primer bombardeo y mueren en el segundo. Cuando un edificio es bombardeado por primera vez, los alienígenas en ese edificio intentan escapar al edificio más cercano (para el primer edificio, el más cercano es el segundo y para el enésimo edificio es el n-1). Calcula el número mínimo de bombas necesarias para matar a todos los alienígenas y el orden de los bombardeos. 
Ejemplo: 
 

Input: 3
Output: 4 
        2 1 3 2 
Explanation: Minimum number of bombs required are 4.
             First bomb the 2nd building, aliens 
             will  move to 1st or 3rd to save
             themselves. Then bomb at 1st building, 
             if some aliens have moved from 2nd 
             building to 1st they will be killed and
             the 1st building aliens will be injured,
             and they will move to the 2nd building
             as it is nearest to them. Now, bomb at
             the 3rd building to kill aliens who 
             moved from the 2nd building to 3rd and
             injure 3rd building aliens so they move 
             to 2nd building as it is nearest to them.
             Now, bomb at the 2nd building again and
             all aliens who moved from 1st or 3rd
             building will be killed.

Input: 2
Output: 3
        2 1 2  

Podemos hacer una forma constructiva de matar a todos los alienígenas. Dado que todos se mueven hacia la izquierda o hacia la derecha, debemos asegurarnos de que todas las posiciones pares sean atacadas, una al principio para herir a los alienígenas y la otra vez al final. Cuando atacamos a los extraterrestres en las posiciones pares la primera vez que se mueven a los edificios de posiciones impares, entonces atáquelos en las posiciones impares para matar todas las posiciones pares anteriores y herir a los alienígenas en posiciones impares. Los extraterrestres de la posición impar se lesionan y se moverán a la posición par, así que atácalos al final para matarlos. 
El número de formas será n/2 + n/2 + n/2 que es n + n/2. 
A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to find number of bombings required
// to kill all aliens.
#include <bits/stdc++.h>
using namespace std;
 
// function to print where to shoot
void print(int n)
{
    // no. of bombs required
    cout << n + n / 2 << endl;
 
    // bomb all the even positions
    for (int i = 2; i <= n; i += 2)
        cout << i << " ";
 
    // bomb all the odd positions
    for (int i = 1; i <= n; i += 2)
        cout << i << " ";
 
    // bomb all the even positions again
    for (int i = 2; i <= n; i += 2)
        cout << i << " ";
}
 
// driver program
int main()
{
    int n = 3;
    print(n);
    return 0;
}

// Java program to find number of bombings
// required to kill all aliens.
class GFG {
     
    // function to print where to shoot
    static void print(int n)
    {
 
        // no. of bombs required
        System.out.println(n + n / 2);
     
        // bomb all the even positions
        for (int i = 2; i <= n; i += 2)
            System.out.print( i + " ");
     
        // bomb all the odd positions
        for (int i = 1; i <= n; i += 2)
            System.out.print(i + " ");
     
        // bomb all the even positions again
        for (int i = 2; i <= n; i += 2)
            System.out.print( i + " ");
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int n = 3;
         
        print(n);
    }
}
 
// This code is contributed by Anant Agarwal.

"""Python program to find number of
bombings required to kill all aliens"""
 
# function to print where to shoot
def bomb_required(n):
     
    # no. of bombs required
    print(n+n // 2)
     
    # bomb all the even positions
    for i in range(2, n + 1, 2):
        print(i, end = " ")
     
    # bomb all the odd positions
    for i in range(1, n + 1, 2):
        print(i, end = " ")
     
    # bomb all the even positions again
    for i in range(2, n, 2):
        print(i, end = " ")
 
# Driver Code        
bomb_required(3)
 
# This code is contributed by Abhishek Agrawal.

// C# program to find number of bombings
// required to kill all aliens.
using System;
 
class GFG {
     
    // function to print where to shoot
    static void print(int n)
    {
 
        // no. of bombs required
        Console.WriteLine(n + n / 2);
     
        // bomb all the even positions
        for (int i = 2; i <= n; i += 2)
            Console.Write( i + " ");
     
        // bomb all the odd positions
        for (int i = 1; i <= n; i += 2)
            Console.Write(i + " ");
     
        // bomb all the even positions
        // again
        for (int i = 2; i <= n; i += 2)
            Console.Write( i + " ");
    }
     
    // Driver code
    public static void Main ()
    {
        int n = 3;
        print(n);
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to find number
// of bombings required to
// kill all aliens.
 
 
// function to print
// where to shoot
function p_rint($n)
{
     
    // no. of bombs required
    echo floor($n + $n / 2),"\n" ;
 
    // bomb all the even positions
    for ($i = 2; $i <= $n; $i += 2)
        echo $i ," ";
 
    // bomb all the odd positions
    for ( $i = 1; $i <= $n; $i += 2)
        echo $i , " ";
 
    // bomb all the even positions again
    for ( $i = 2; $i <= $n; $i += 2)
        echo $i , " ";
}
 
    // Driver Code
    $n = 3;
    p_rint($n);
 
// This code is contributed by anuj_67.
?>

<script>
// javascript program to find number of bombings
// required to kill all aliens.   
// function to print where to shoot
    function print(n) {
 
        // no. of bombs required
        document.write(n + parseInt(n / 2) + "<br/>");
 
        // bomb all the even positions
        for (i = 2; i <= n; i += 2)
            document.write(i + " ");
 
        // bomb all the odd positions
        for (i = 1; i <= n; i += 2)
            document.write(i + " ");
 
        // bomb all the even positions again
        for (i = 2; i <= n; i += 2)
            document.write(i + " ");
    }
 
    // Driver code   
        var n = 3;
        print(n);
 
// This code is contributed by Rajput-Ji
</script>

Producción: 
 

4
2 1 3 2

Complejidad temporal: O(n)

Espacio Auxiliar : O(1)

Este artículo es una contribución de Raj . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.