Colonia de Bacterias

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 128M

Authors:

leocar, leo, FrankHG

Problem type

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

El biólogo Mr. Relue está investigando en su laboratorio cierta bacteria con un modo muy peculiar de reproducción. Inicialmente hay solo dos de ellas alineadas y durante todo el ciclo de vida de la colonia todas las bacterias permanecen alineadas. Las bacterias se reproducen a cada segundo.

Cada bacteria tiene un índice de reproducción que le permitirá replicarse con las dos bacterias adyacentes produciendo una nueva bacteria con índice de repreducción igual a la suma de las dos que la formaron, y para mantenerse alineadas la nueva bacteria se ubica entre las dos anteriores. Mr. Relue nota que este modo de reproducción produce un crecimiento exponencial no deseado. Vea el modelo de crecimiento con los respectivos índices de reproducción de la colonia durante 6 segundos cuando las dos primeras bacterias tienen índices de reproducción 1:

1.  { 1 1 }
2.  { 1 2 1 }
3.  { 1 3 2 3 1 }
4.  { 1 4 3 5 2 5 3 4 1 }
5.  { 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 }
6.  { 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9 7 12 5 13 8 11 3 10 7 11 4 9 5 6 1 }

Así que él le hace una modificación al ADN de las bacterias de manera tal que en el segundo N solo aparezcan bacterias con índice de reproducción igual a N, de modo que ahora la colonia crecería así:

1.  { 1 1 } 
2.  { 1 2 1 }
3.  { 1 3 2 3 1 }
4.  { 1 4 3 2 3 4 1 }
5.  { 1 5 4 3 5 2 5 3 4 5 1 }
6.  { 1 6 5 4 3 5 2 5 3 4 5 6 1 }

O sea, que el segundo N solo aparecen bacterias entre dos con índices cuya suma sea $N$ ~N~. Después de $N$ ~N~ segundos Mr. Relue quiere saber cuántas bacterias hay con índice de reproducción menor o igual a un $K$ ~K~ dado, haga un programa que compute esta información y así prodrá trabajar junto al prestigioso biólogo.

Entrada

En la primera línea aparecerán los enteros $N (1 \leq N \leq 10^7)$ ~N (1 \leq N \leq 10^7)~ y $K (1 \leq K \leq N)$ ~K (1 \leq K \leq N)~.

Salida

Imprima un único entero que es la cantidad de bacterias con índice de reproducción menor o igual a $K$ ~K~ después de $N$ ~N~ segundos de vida de la colonia. Se asegura que la respuesta cabe en un entero de 64 bits.

Ejemplos #1 de Entrada

5 4

Ejemplos #1 de Salida

Ejemplos #2 de Entrada

10 10

Ejemplos #2 de Salida

Ejemplos #3 de Entrada

100 70

Ejemplos #3 de Salida

Comments

0

dmesadiaz commented on Feb. 29, 2020, 5:15 a.m.

Aguien podria decirme como resolver este problema

0

FrankHG commented on Feb. 10, 2020, 2:50 p.m.

Para todos los que preguntaron, ya colocado el rango de N