Rompecabezas 81 | Rompecabezas de 100 personas en círculo con pistola

100 personas de pie en un círculo en un orden del 1 al 100. El número 1 tiene una espada. Mata a la siguiente persona (es decir, el número 2) y le da la espada al siguiente (es decir, el número 3). Todas las personas hacen lo mismo hasta que solo 1 sobrevive. ¿Qué número sobrevive al último? 
Hay 100 personas del 1 al 100. 
  
Solución: La 73ª persona sobrevivirá al fin 

Explicación 1 (intuitiva y lógica): Podemos observar que si el número de personas de pie en un círculo es una potencia de 2, entonces la persona que inicia el juego vivirá. Esto se debe a que después de cada ronda de asesinatos, el número de personas que quedan se reducirá en 2 y no quedará ningún resto, por lo que la siguiente ronda comenzará nuevamente con la misma persona que inició inicialmente el juego. Y esto seguirá.

En el caso de que el número de personas en el círculo no sea una potencia de dos, en la primera ronda, cuando el número de personas vivas se convierta en una potencia de 2, entonces la persona que sostiene el arma ganará porque, básicamente, está comenzando una juego con personas que quedan en la potencia de 2. Entonces, para 100, 36 personas deben morir cuando quedan 64 personas, es decir, un número menor que el número dado y una potencia de dos. La persona número 36 que morirá será la persona número 72, por lo que la persona número 73 tendrá el arma cuando el número de personas vivas sea 64.

Explicación 2 (código):  
Aquí, podemos definir una array con 100 elementos con valores de 1 a 100. 
 

• No.1 tiene una espada. Mata a la siguiente persona (es decir, el número 2) y le da la espada al siguiente (es decir, el número 3). 
  Hemos tomado el elemento de array como una persona. La primera persona mata a la siguiente. Entonces, comenzando desde 1, eliminaremos el siguiente elemento, es decir, 2.
• Luego, la primera persona le da la espada a la siguiente, es decir, 3. Esa persona también matará a la siguiente persona y esto continúa. Significa que, en la array, debemos comenzar con 1 y eliminar todos los demás elementos (alternativos) hasta el 100. (Se eliminarán todos los números pares y nos quedarán solo los números impares en la array).

Ronda 1: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47 , 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97 , 99 
Ronda 2: 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89 , 93, 97 
Ronda 3: 1, 9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89, 97 Ronda 4 
: 9, 25, 41, 57, 73, 89 
Ronda 5: 9 , 41, 73 
Vuelta 6: 9, 73 
Vuelta 7: 73 

Para evitar el cálculo manual hecho arriba, aquí el algoritmo general: 
Paso 1: Para un valor dado de N, encuentra la “Potencia de 2” inmediatamente mayor que N. Llamémoslo P 
Paso 2: Resta N de (P-1) . Llamémoslo M, es decir, M = (P-1)- N 
Paso 3: Multiplica M por 2, es decir, M*2 
Paso 4: Resta M*2 de P-1. Llamémoslo ans, es decir, ans = (P-1) – (M*2) 
Entonces, la persona con el número “ans” sobrevivirá hasta el final. 

Código:

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
 
    int person = 100;
 
    // Placeholder array for person
    vector<int> a(person);
 
    // Assign placeholders from 1 to N (total person)
    for (int i = 0; i < person; i++) {
        a[i] = i + 1;
    }
 
    // Will start the game from 1st person (Which is at
    // placeholder 0)
    int pos = 0;
 
    // Game will be continued till we end up with only one
    // person left
    while (a.size() > 1) {
        // Current person will shoot the person next to
        // him/her. So incrementing the position.
        pos++;
        // As person are standing in circular manner, for
        // person at last place has right neighbour at
        // placeholder 0. So we are taking modulo to make it
        // circular
        pos %= a.size();
        // Killing the person at placeholder 'pos'
        // To do that we simply remove that element
        a.erase(a.begin() + pos);
        // There is no need to increment the pos again to
        // pass the gun Because by erasing the element at
        // 'pos', now next person will be at 'pos'.
    }
 
    // Print Person that survive the game
    cout << a[0];
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.Arrays;
 
class GFG {
 
    // Driver code
    public static void main (String[] args) {
        int person = 100;
     
        // Placeholder array for person
        int[] a = new int[person];
     
        // Assign placeholders from 1 to N (total person)
        for (int i = 0; i < person; i++) {
            a[i] = i + 1;
        }
     
        // Will start the game from 1st person (Which is at
        // placeholder 0)
        int pos = 0;
     
        // Game will be continued till we end up with only one
        // person left
        while (a.length > 1)
        {
           
            // Current person will shoot the person next to
            // him/her. So incrementing the position.
            pos++;
           
            // As person are standing in circular manner, for
            // person at last place has right neighbour at
            // placeholder 0. So we are taking modulo to make it
            // circular
            pos %= a.length;
           
            // Killing the person at placeholder 'pos'
            // To do that we simply remove that element
            int[] anotherArray = new int[a.length - 1];
            System.arraycopy(a, 0, anotherArray, 0, pos);
            System.arraycopy(a, pos + 1, anotherArray, pos,a.length - pos - 1);
            a = anotherArray;
           
            // There is no need to increment the pos again to
            // pass the gun Because by erasing the element at
            // 'pos', now next person will be at 'pos'.
        }
     
        // Print Person that survive the game
        System.out.println(a[0]);
    }
}
 
// This Code is contributed by ShubhamSingh10

person = 100
 
# Placeholder array for person
a = [0] * person
 
# Assign placeholders from 1 to N (total person)
for i in range(person):
    a[i] = i + 1
     
# Will start the game from 1st person (Which
# is at placeholder 0)
pos = 0
 
# Game will be continued till we end up with
# only one person left
while (len(a) > 1):
     
    # Current person will shoot the person next
    # to him/her. So incrementing the position.
    pos += 1
     
    # As person are standing in circular manner,
    # for person at last place has right neighbour
    # at placeholder 0. So we are taking modulo
    # to make it circular
    pos %= len(a)
     
    # Killing the person at placeholder 'pos'
    # To do that we simply remove that element
    del a[pos]
     
    # There is no need to increment the pos again to
    # pass the gun Because by erasing the element at
    # 'pos', now next person will be at 'pos'.
 
# Driver code
 
# PrPerson that survive the game
print(a[0])
 
# This code is contributed by ShubhamSingh10

// C# program for the above approach
using System;
using System.Linq;
 
public static class GFG
{
   
    // Driver code
    static public void Main ()
    {
     
        int person = 100;
     
        // Placeholder array for person
        int[] a = new int[person];
     
        // Assign placeholders from 1 to N (total person)
        for (int i = 0; i < person; i++) {
            a[i] = i + 1;
        }
     
        // Will start the game from 1st person (Which is at
        // placeholder 0)
        int pos = 0;
     
        // Game will be continued till we end up with only one
        // person left
        while (a.Length > 1)
        {
           
            // Current person will shoot the person next to
            // him/her. So incrementing the position.
            pos++;
           
            // As person are standing in circular manner, for
            // person at last place has right neighbour at
            // placeholder 0. So we are taking modulo to make it
            // circular
            pos %= a.Length;
           
            // Killing the person at placeholder 'pos'
            // To do that we simply remove that element
            a = a.Where((source, index) =>index != pos).ToArray();
           
            // There is no need to increment the pos again to
            // pass the gun Because by erasing the element at
            // 'pos', now next person will be at 'pos'.
        }
     
        // Print Person that survive the game
        Console.Write(a[0]);
    }
}
 
// This Code is contributed by ShubhamSingh10

<script>
 
var person = 100;
 
// Placeholder array for person
var a = new Array(person);
 
// Assign placeholders from 1 to N (total person)
for (var i = 0; i < person; i++) {
    a[i] = i + 1;
}
 
// Will start the game from 1st person (Which is at
// placeholder 0)
var pos = 0;
 
// Game will be continued till we end up with only one
// person left
while (a.length > 1) {
    // Current person will shoot the person next to
    // him/her. So incrementing the position.
    pos++;
    // As person are standing in circular manner, for
    // person at last place has right neighbour at
    // placeholder 0. So we are taking modulo to make it
    // circular
    pos = pos% (a.length);
    // Killing the person at placeholder 'pos'
    // To do that we simply remove that element
    a.splice(pos,1)
     
    // There is no need to increment the pos again to
    // pass the gun Because by erasing the element at
    // 'pos', now next person will be at 'pos'.
}
 
// Print Person that survive the game
document.write(a[0]);
 
// This code is contributed by ShubhamSingh10
 
</script>

73

Este rompecabezas es aportado por Jyoti . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.