2649 - Square Factory

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
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

2649 - Square Factory

Post by ymondelo20 » 5 years ago



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

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

Re: 2649 - Square Factory

Post by facug91 » 5 years ago

Hola, para resolver este problema un amigo encontró la fórmula Image donde el a1 sería 1 (el primer elemento) y r sería 4.
Cuando lo escribimos con exponenciación rápida modular, en los casos ejemplos endaba, entonces lo subimos y nos dio wrong answer. Entramos en el datagen y nos dimos cuenta que para algunos casos funciona y para otros no. No entendíamos por qué, y al final nos dimos cuenta que aveces hace el módulo de 1000003, y después divide por 3 (r - 1 = 4 - 1 = 3), y ahí da mal el resultado. No sé si se pueden postear códigos acá por eso no lo hago (es mi primer mensaje en el foro).
Nuestro problema es que no sabemos cómo resolver esto, porque no se puede poner la división por 3 adentro de la función de exponencición, pero afuera da mal el resultado... cómo podemos hacer para solucionar eso? O es por otro lado la solución?

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

Re: 2649 - Square Factory

Post by ymondelo20 » 5 years ago

Puedes postear la sección del código que te interesa...
Además, no es una solución aceptada.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

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

Re: 2649 - Square Factory

Post by facug91 » 5 years ago

Este es mi código (sin contar los includes):

Code: Select all

#define square(x) ((x) * (x))
#define tint long long int
#define mod 1000003

using namespace std;

int c;
tint n;

int bigmod (tint p) {
	if (p == 0) {
		return 1;
	} else if (p % 2 == 0) {
		return square(bigmod(p/2)) % mod;
	} else {
		return (4 * bigmod(p-1) % mod);
	}
}

int main() {
	cin>>c;
	
	for (;c--;) {
		cin>>n;
		printf("%d\n",(bigmod(n+1)-1)/3);
	}
	
    return 0;
}
El tema es que como el número es muy grande, en la exponenciación (osea, la función bigmod), además de elevar el 4 a la potencia 'n+1', va haciendo el mod 1000003, y cuando vuelve y divide por 3, muchas veces da mal el resultado. Pero no sé cómo arreglar eso, o si en realidad estoy encarando mal el problema.

rvargas
Posts: 37
Joined: 5 years ago
Gender: None specified

Re: 2649 - Square Factory

Post by rvargas » 5 years ago

¿No sera un problema que solo le estás aplicando modulo solo a la potencia?

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

Re: 2649 - Square Factory

Post by facug91 » 5 years ago

No, por ejemplo, si calculo 4^9 debería darme 1048576, lo que dividido 3 me da 349525 (redondeado), resultado que es correcto. Pero en mi resolución, como en la exponenciación hago el módulo de todos los resultado, me devuelve 48573, que dividido 3 me da 16191. El problema está en que tengo que dividir el resultado por 3, y no sé cómo hacer eso usando módulo antes...

Aclaración: hacer el módulo del resultado dividido 3 no tendría sentido, porque el número va a ser sí o sí menor que el resultado de la función bigmod, que es donde aplico el módulo.

HaZard
Posts: 114
Joined: 5 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 2649 - Square Factory

Post by HaZard » 4 years ago

¿el tamaño del código no puede exceder los 128 bytes? por favor arreglen esto...
teruel

HaZard
Posts: 114
Joined: 5 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 2649 - Square Factory

Post by HaZard » 4 years ago

ahora me aparece que el tamaño del codigo puede llegar hasta 16 Kb, pero al enviar mi solucion me dice "The source code is too long", que puede estar pasando?
teruel

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

Re: 2649 - Square Factory

Post by ymondelo20 » 4 years ago

HaZard wrote:ahora me aparece que el tamaño del codigo puede llegar hasta 16 Kb, pero al enviar mi solucion me dice "The source code is too long", que puede estar pasando?
Ya lo he corregido.
Saludos.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

Post Reply

Return to “Problem set”