El origen del ajedrez P65001


Statement
 

pdf   zip

thehtml

Según la leyenda que le contó Beremiz al califa de Bagdad, el ajedrez se debe a un joven brahmán, el cual lo inventó para distraer y alegrar a un rey. Como premio, el rey concedió un deseo al brahmán, el cual “solamente” pidió un grano de trigo por la primera casilla del tablero, dos granos por la segunda casilla, cuatro por la tercera, ocho por la cuarta, …, y así sucesivamente hasta la casilla número 64. El rey se rió al oir el deseo, y lo concedió inmediatamente. Después consultó cuánto trigo era con sus sabios matemáticos, los cuales llegaron a la conclusión de que era más del que podría producir la India entera en más de un siglo. El final de la leyenda cuenta que el brahmán liberó al rey de su promesa imposible de cumplir, y éste a cambio le nombró su primer ministro.

Entrada

La entrada consiste en diversos casos, cada uno con el número de casillas c de un juego, y un número deseado de granos de trigo g. Se cumple 2 ≤ c ≤ 109 y 1 ≤ g ≤ 264 − 1.

Salida

Para cada caso, escribid una línea con la mínima x entera estrictamente positiva tal que si el brahmán pide 1 grano por la primera casilla, x granos por la segunda, x2 granos por la tercera, x3 granos por la cuarta, etcétera, la suma total será por lo menos de g granos.

Observación

Se puede resolver este problema usando el tipo unsigned long long, si se vigilan los posibles desbordamientos antes de que se produzcan.

Public test cases
  • Input

    4 15
    4 16
    1000 1
    2 1000
    64 18446744073709551615
    42 18446744073709551615
    41 18446744073709551615
    2 18446744073709551615
    1000000000 18446744073709551615
    

    Output

    2
    3
    1
    999
    2
    3
    4
    18446744073709551614
    2
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++