Hola,
les paso mi solucion del problema. Chequen por favor la forma en que defino las T'[ ]s, si se les ocurre una forma de escribir eso, sin tener que decirlo una por una, me dicen porfa.
Espero puedan subir sus soluciones para revisarlas, la idea del blog es que nos hagamos comentarios sobre lo que hacemos, tratemos de mejorar y aprendamos de los demas.
#include<stdio.h>
long long k, s[17], m, i,j,l,n, p[17],t[17],r;
int main(){
s[0]=1;
for(i=1;i<17;i++)
s[i]=5*s[i-1]+1;
p[0]=5;
for(j=1;j<17;j++)
p[j]=5*p[j-1];
scanf("%lld",&m);
t[16]=m/s[16];
t[15]=(m-t[16]*s[16])/s[15];
t[14]=(m-t[16]*s[16]-s[15]*t[15])/s[14];
t[13]=(m-t[16]*s[16]-s[15]*t[15]-t[14]*s[14])/s[13];
t[12]=(m-t[16]*s[16]-s[15]*t[15]-t[14]*s[14]-t[13]*s[13])/s[12];
t[11]=(m-t[16]*s[16]-s[15]*t[15]-t[14]*s[14]-t[13]*s[13]-t[12]*s[12])/s[11];
t[10]=(m-t[16]*s[16]-s[15]*t[15]-t[14]*s[14]-t[13]*s[13]-t[12]*s[12]-t[11]*s[11])/s[10];
t[9]=(m-t[16]*s[16]-s[15]*t[15]-t[14]*s[14]-t[13]*s[13]-t[12]*s[12]-t[11]*s[11]-t[10]*s[10])/s[9];
t[8]=(m-t[16]*s[16]-s[15]*t[15]-t[14]*s[14]-t[13]*s[13]-t[12]*s[12]-t[11]*s[11]-t[10]*s[10]-t[9]*s[9])/s[8];
t[7]=(m-t[16]*s[16]-s[15]*t[15]-t[14]*s[14]-t[13]*s[13]-t[12]*s[12]-t[11]*s[11]-t[10]*s[10]-t[9]*s[9]-t[8]*s[8])/s[7];
t[6]=(m-t[16]*s[16]-s[15]*t[15]-t[14]*s[14]-t[13]*s[13]-t[12]*s[12]-t[11]*s[11]-t[10]*s[10]-t[9]*s[9]-t[8]*s[8]-t[7]*s[7])/s[6];
t[5]=(m-t[16]*s[16]-s[15]*t[15]-t[14]*s[14]-t[13]*s[13]-t[12]*s[12]-t[11]*s[11]-t[10]*s[10]-t[9]*s[9]-t[8]*s[8]-t[7]*s[7]-t[6]*s[6])/s[5];
t[4]=(m-t[16]*s[16]-s[15]*t[15]-t[14]*s[14]-t[13]*s[13]-t[12]*s[12]-t[11]*s[11]-t[10]*s[10]-t[9]*s[9]-t[8]*s[8]-t[7]*s[7]-t[6]*s[6]-t[5]*s[5])/s[4];
t[3]=(m-t[16]*s[16]-s[15]*t[15]-t[14]*s[14]-t[13]*s[13]-t[12]*s[12]-t[11]*s[11]-t[10]*s[10]-t[9]*s[9]-t[8]*s[8]-t[7]*s[7]-t[6]*s[6]-t[5]*s[5]-t[4]*s[4])/s[3];
t[2]=(m-t[16]*s[16]-s[15]*t[15]-t[14]*s[14]-t[13]*s[13]-t[12]*s[12]-t[11]*s[11]-t[10]*s[10]-t[9]*s[9]-t[8]*s[8]-t[7]*s[7]-t[6]*s[6]-t[5]*s[5]-t[4]*s[4]-t[3]*s[3])/s[2];
t[1]=(m-t[16]*s[16]-s[15]*t[15]-t[14]*s[14]-t[13]*s[13]-t[12]*s[12]-t[11]*s[11]-t[10]*s[10]-t[9]*s[9]-t[8]*s[8]-t[7]*s[7]-t[6]*s[6]-t[5]*s[5]-t[4]*s[4]-t[3]*s[3]-t[2]*s[2])/s[1];
t[0]=(m-t[16]*s[16]-s[15]*t[15]-t[14]*s[14]-t[13]*s[13]-t[12]*s[12]-t[11]*s[11]-t[10]*s[10]-t[9]*s[9]-t[8]*s[8]-t[7]*s[7]-t[6]*s[6]-t[5]*s[5]-t[4]*s[4]-t[3]*s[3]-t[2]*s[2]-t[1]*s[1])/s[0];
r=0;
for(n=0;n<17;n++)
r=r+p[n]*t[n];
k=r;
printf("%lld",k);
}
yo no le etiendo a tu codigo, bueno cual es la idea que seguiste para la solucion?? es qe no me qeda clara solo con el codigo =)
ResponderEliminarPuedes revisar un poco lo que explican en la redaccion del problema en la pagina de la OMI. La idea es que dado un numero n, podemos encontrar la cantidad de 0's de n! calculando la cantidad de potencias de 5, ya que hay muchas mas potencias de 2, que de 5: cada 2*5 agrega un 0.
ResponderEliminarLa cantidad de factores 5 es igual al numero divido entre 5 (solo considerando enteros), esto nos da la cantidad de multiplos de 5. luego volvemos a dividir entre 5, encontramos la cantidad de multiplos de 25, los cuales tienen por lo menos 2 factores 5, pero ya habiamos contado uno, por lo que solo agregan otro, y asi seguimos con todas las potencias de 5(en algun momento da 0 la division).
k la cantidad de 0's es k/5+k/25+...
lo que hago en mi codigo es lo contrario, veo como calcular un numero k como suma de potencias de 5.
Alain sugirio poner ese codigo enorme de la siguiente manera:
ResponderEliminar#include
long long k, s[17], m, i,j,l,n, p[17],t[17],r;
int main(){
s[0]=1;
for(i=1;i<17;i++)
s[i]=5*s[i-1]+1;
p[0]=5;
for(j=1;j<17;j++)
p[j]=5*p[j-1];
scanf("%lld",&m);
t[16]=m/s[16];
for(i=15;i>=0;i--){
t[i]=m;
for(j=16;j>i;j--)
t[i]=t[i]-t[j]*s[j];
t[i]=t[i]/s[i];
}
r=0;
for(n=0;n<17;n++)
r=r+p[n]*t[n];
k=r;
printf("%lld",k);
}