1259 - Div 4 Base 3

[dovier]

http://coj.uci.cu/24h/problem.xhtml?abb=1259

[Avid]

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

[Dariel]

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]

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).

[ymondelo20]

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.