0votos

La habitación del pánico en C#

por josejuan hace 6 años

Lo dicho en la solución de JavaScript, aquí posteo únicamente para dar la solución sin desbordamiento.

Una serie de habitaciones están conectadas unas con las otras por puertas automáticas que se abren usando tarjetas de seguridad. Unas reglas estipuladas te impiden pasar directamente del principio a fin de forma similar a las Torres de Hanoi.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static ulong Reduce( ulong Q, ulong T ) { 
    if( Q < T ) 
        return Q + 1; 
    var k = Q / ( T - 2 ); 
    if( Q % ( T - 2 ) > 0 ) 
        k++; 
    var q = ( k - 1 ) * ( T - 2 ) + T - 1; 
    if( q - Q >= T - 2 ) 
        k -= 1; 
    return Q + ( k - 1 ) * 2 + 1; 
static ulong Panico( ulong T, ulong H ) { 
    var N = 1UL; 
    while( H-- > 0 ) 
        N = Reduce(N, T); 
    return N; 
static ulong Suma( ulong Tmax, ulong H ) { 
    var S = 0UL; 
    for( var T = 3UL; T <= Tmax; T++ ) 
        S += Panico(T, H); 
    return S; 
 
// Suma(40, 30) ~~~~~> 34315549139516 
3 comentarios
0votos

Escrito por xurxof hace 6 años

¿Alguien podía comentar que hace Reduce()? Gracias!
0votos

Escrito por josejuan hace 6 años

El número de tarjetas que necesitas para N+1 puertas, es el número de tarjetas que necesitas para N puertas más lo que te cuesta pasar esas tarjetas por la última puerta.

Así, si llamamos Q al nº de tarjetas que queremos tener "al otro lado" de la puerta, T al nº de tarjetas simultáneamente que podemos llevar y N el nº de tarjetas que debemos tener previamente, tenemos que

N [T]> Q

si Q = 1, claramente N = 2 (pasamos por la puerta una vez)
si Q = 2, claramente N = 3 (pasamos por la puerta dos veces)

notar que T >= 3, sino, para más de una puerta no hay solución

en general, cada vez que llevamos un paquete de tarjetas de N a Q y volvemos a N, lo que hacemos es

1. tenemos en N un máximo de T tarjetas en la mano.
2. al pasar por la puerta usamos una
3. estamos en Q con T - 1 tarjetas
4. dejamos en Q T - 2 tarjetas porque tenemos que volver a N por más
5. estamos en N

así, el número de tarjetas que necesitamos en N para dejar Q al otro lado es la suma de

T - 2
T - 2
T - 2
...
T - 2

teniendo en cuenta que en el último "trasvase" el resto de dividir Q / (T - 2) puede no alcanzar (T - 1), pues en el último trasvase acarreamos una tarjeta más, hace falta controlar el resto de la operación para saber el valor real de N.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.