1259 - Div 4 Base 3

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
dovier
Posts: 1143
Joined: 8 years ago
Location: Havana, Cuba
Gender: Male
Cuba

1259 - Div 4 Base 3

Post by dovier » 7 years ago




Avid
Posts: 4
Joined: 7 years ago
Gender: None specified

Re: 1259 - Div 4 Base 3

Post by Avid » 6 years ago

Hola, estoy atascado en este problema, me preguntaba si podrias darme alguna pista, pues me parece que converitr el numero a base decimal y comprobar su modulo con 4 se hace muy engorroso y me da WrongAnswer, si existe alguna forma de conocer si el numero en base 3 es divisible en entre 4 sin convertir el numero, por favor ayudame

User avatar
Dariel
Posts: 51
Joined: 8 years ago
Location: Santiago de Cuba
Gender: None specified
Contact:

Re: 1259 - Div 4 Base 3

Post by Dariel » 6 years ago

mas o menos lo que hice fue coger el numero e ir viendo cuanto aporta cada cifra modulo 4, por ejemplo si el numero es 1201, es 1*3^3 + 2*3^2+1*3^0, las potencias de 3 son congruentes con 1 y -1 alternadamente a partir de 3^0 asi que 1201 da 1*(-1) + 2*(1)+0*(-1)+1*(1) = -1+2+1 = 2 (1201(3) = 46(10) = 2 mod 4) no importa que los numeros sean de bastante digitos, no me dio problema con el tiempo

facug91
Posts: 12
Joined: 6 years ago
Gender: None specified

Re: 1259 - Div 4 Base 3

Post by facug91 » 6 years ago

Lo primero que se me ocurrió a mi fue eso, pasar el número a base 10 y ver si es múltiplo de 4, pero cuando hice el análisis de tiempo de eso me quedaba exageradamente lento (números de hasta 10^6 dígitos con un máximo de 10^4 casos de prueba, me daba un 10^10 bastante feo). Pero de todos modos lo escribí y pasó perfectamente bien, todavía no sé por qué jajaj.
El tema es que tenés que tener en cuenta algunos detalles importantes, como que el número en realidad es un string, y no podés pasarlo a base 10 de una por el tamaño del mismo, así que tenés que ir calculándolo dígito por dígito. Ese puede ser uno de los mótivos por los que te dé WA, que se desborde la variable que usas.
Podés hacer lo que hizo Dariel, o algo más general es ir haciéndole a cada cuenta que hagas mod 4, y si al final la variable que usaste para sumar da 0, quiere decir que es divisible por 4, sino no. Esto es por la propiedad de que (A + B) mod C = ((A mod C) + (B mod C)) mod C (Aritmética modular).

User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 1259 - Div 4 Base 3

Post by ymondelo20 » 6 years ago

Dato importante (lo he adicionado al problema):
You can safely assume that the amount of digits in the input will be at most 5 millions.
Entonces, 10^10 no es un problema: aunque un fichero con esa cantidad de caracteres tendría aproximadamante unos 9.3 GB (solo leerlo sería un problema).

Saludos.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

Post Reply

Return to “Problem set”