|
|
Esta sección te permite ver todos los posts escritos por este usuario. Ten en cuenta que sólo puedes ver los posts escritos en zonas a las que tienes acceso en este momento.
Mensajes - Binary
1
« en: Jueves 18 de Noviembre de 2004, 19:22 »
Hola a todos... Les quiero hacer saber que existen los Online Judges que son un sistema para ir solucionando problemas de la ACM. Estos son lugares donde hay muchisimos problemas en "problemset" y uno puede resolver uno y meterlo al sistema para graduacion. Hay 2 posibilidades: que este bueno o malo el programa entregado  Por eso es dificil resolver los retos porque el mas minimo detalle vuelve tu programa inutil a resolver el problema. Ahora... La mayoria de los problemas son de algoritmos pero hay una parte matematicos. Es entretenido resolver problemas cuando se sabe que despues verificaras si podiste resolverlo o no. Estos son algunos Online Judges con problemas por resolver: acm.zju.edu.cn acm.sgu.ru acm.uva.es spoj.sphere.pl Vayan y retense Uds mismos... Yo personalmente resuelvo de todos excepto el uva.es. Lo que si es que son bien dificiles y una gran parte de los problemas son imposibles para mi. Sin embargo, algunos problemas los podemos comentar, de modo que los podamos resolver juntos. Creo que es una buena idea, porque asi podremos ir aprendiendo todos. Saludos a todos y buena suerte!
2
« en: Miércoles 10 de Noviembre de 2004, 21:53 »
Hi everyone... im back...
Luego de mi presentacion en Athenas el 11-18 de septiembre, me fui a Bulgaria, mi pais natal, donde estuve por 1 mes, asi que ahora estoy de vuelta...
Sin medalla de las internacionales, pero igual, feliz de haber ido...
grrrr... 255/600 ptos finales... 265 era bronce, no importa... es mas impiortante participar que ganar (el logo de los perdedores), pero ahora le encuentro el sentido...
Bueno... no tengo mucho tiempo, encontre mi PC con un monton de viruses, asiq ue voy a reinstalarlo, luego vere que mas hago...
Adios...
3
« en: Lunes 6 de Septiembre de 2004, 22:12 »
Pues, no creo que se trate de saber o no, sino que esas competencias requieren tener una practica bastante activa los ultimos 5-6 meses antes de la competencia de modo que se te vengan ideas a la cabeza de inmediato... En los ultimos 8 meses yo resolvi 500-600 problemas por el estilo, con eso, al ver un problema se me ocurren muchas formas de trabajarlo y asi puedo tener algoritmos entre los cuales elegir el mas apropiado... El otro dia hice copy *.cpp y me sorprendi al ver 500 archivos copiados, que son todo mi empenio de los ultimos meses. Aun asi... creo que uno nunca esta lo suficientemente preparado para lo que viene, porque en las internacionales no dan problemas que ya se hayan visto o publicado, sino que los inventan y los dejan de modo tal que el algoritmo que hay que usar sean irreconosible... o hay que modificarlo demasiado para que se ajuste al problema. Como sea... deseanme suerte para el 10 de sept que tengo la olimpiada y esoty nervioso  Adios a todos!! Estare un buen tiempo sin posts por aqui... Saludos desde Chile...
4
« en: Sábado 4 de Septiembre de 2004, 16:26 »
Este problema es sacado de IOI 1998 (International Olympiad in Informatics) que es para jovenes de secundaria. Las reglas de la IOI son 5 horas para 3 problemas, lo que impondria un limite de menos de 2 horas para cada problema.
Los problemas nunca se repiten y nunca seran de aplicar un algoritmo conocido y ya, porque eso no es la idea, sino, combinaciones y modificaciones de algoritmos, que lo harian mas dificil...
Hay personas que resuelven los 3 problemas en ese tiempo, pero la mayoria estan capaces de hacer 2 de 3, que tampoco es malo...
Yo participo en esta competencia, y en una semana estare participando en la IOI 2004 en Grecia, asi que por favor no me digan que no se pueden resolver, porque hay muchas personas que lo hacen.
10 mins para leer y entender el problema
20 mins para inventar algoritmo
30 mins para codificarlo
10 mins para depurarlo
Eso seria un tiempo normal para cualquier problema...
Saludos!
5
« en: Jueves 26 de Agosto de 2004, 14:42 »
int max(int a, int b) { return ( a > b ? a : b ); } int max(int a, int b, int c) { return max(a, max(b, c)); } int main() { int a, b, c; cin>>a>>b>>c; cout<<max(a, b, c)<<endl; return 0; }
6
« en: Miércoles 25 de Agosto de 2004, 04:28 »
De poder, se puede, pero no le encuentro mucho sentido...
Lo que estariamos haciendo es un tipo de lenguaje simplificado, pero su base es un lenguaje tan complejo como el C++...
Es interesante crear un lenguaje, pero no pasando por otro, sino, por lenguaje de maquina.... Sino estaria ocurriendo que nosotros procesamos cosas simples con una base muy compleja y avanzada, distrayendo todas las facultades de rapidez, que es algo absurdo....
Lo que si es que es una interesante idea, aunque poco practica... seria entretenido por lo menos hablar de eso, aunque no le saquemos el provecho, pero nada mas para detallar un poco en la logica de la programacion.
Saludos.
7
« en: Miércoles 25 de Agosto de 2004, 03:22 »
Yo no se nada de eso...!!!
Ni idea, pero si puedo observar por arriba lo que pasa... lo que si es que soy 100% usuario a nivel de sistema operativo.
Saludos.
8
« en: Martes 24 de Agosto de 2004, 00:59 »
// Divisibility #include <stdio.h> #define MAXR 10000001 int r[MAXR]; int main() { int n, k, i, num, mod, found; __int64 sum = 0; FILE *fin, *fout; fin = fopen("div.in", "r"); fout = fopen("div.out", "w"); found = 0; fscanf(fin, "%d %d", &n, &k); for(i = 0; i < n; i++) { fscanf(fin, "%d", &num); sum += num; mod = (int)(sum % k); if(r[mod] != 0) { fprintf(fout, "%d %d\n", r[mod]+2, i+1); found = 1; break; } r[mod] = i; } if(!found) fprintf(fout, "NO SOLUTION\n"); fclose(fin); fclose(fout); return 0; }
9
« en: Martes 24 de Agosto de 2004, 00:47 »
// Race #include <stdio.h> #define MAXV 1000001 #define LOW_BIT(x) ((((x) - 1) ^ (x)) & (x)) int v[MAXV]; int query(int pos) { int i, r = 0; for(i = pos; i > 0; i -= LOW_BIT(i)) r += v[i]; return r; } void update(int pos, int val) { int i; for(i = pos; i < MAXV; i += LOW_BIT(i)) v[i] += val; } int main() { int n, i, ans, pos, speed; FILE *fin, *fout; fin = fopen("race.in", "r"); fout = fopen("race.out", "w"); ans = 0; fscanf(fin, "%d", &n); for(i = 0; i < n; i++) { fscanf(fin, "%d %d", &pos, &speed); ans += query(MAXV-1) - query(speed); update(speed, 1); } fprintf(fout, "%d\n", ans); fclose(fin); fclose(fout); return 0; }
10
« en: Martes 24 de Agosto de 2004, 00:12 »
Ahora... lo que vamos a optimizar es la rapidez con la que guardaremos los autos en v[]....
Tanto la entrada, como al sacar, lo realizaremos en tiempo lg(N), gracias a la estructura de datos, conocida como index_tree...
(por favor, buscar en google para los que no la sepan)...
esta permite almacenar datos en array en tiempo lg(n) y preguntar en tiempo lg(n)... cuantos datos hay en v[1..n]... asi... al preguntar para v[1...MAXSPEED] - v[1..c.speed]... tenemos la cantidad buscada....
Ahora escribire el codigo...
11
« en: Martes 24 de Agosto de 2004, 00:08 »
Ya... posteo la solucion: Antes que nada... tenemos 1M diferentes velocidades. Asi tambien tenemos 1M autos, cada uno, caracterizado por su velocidad y su posicion inicial del pto de partida. Asi, para cada auto tenemos: struct Car { int pos, speed; }; Ademas, los autos vienen en orden de pos... mas precisamente... los autos mas cerca, primeros. Definiremos adelantamiento como la situacion en la que un auto "x" esta mas cerca de la partida que otro auto "y", y el auto x tiene mayor velocidad... Asi... if(c - .pos < c[y].pos && c
- .speed > c[y].speed) tenemos adelantamiento
Para facilitar las cosas, y hacerlas mas rapidas, haremos lo siguente... Tendremos un array de velocidades, en el que guardaremos la cantidad de autos que tienen dicha velocidad, asi: v - seria la cantidad de autos con velocidad x
Ahora: vamos recorriendo los autos uno por uno (del mas cercano al mas lejano). Para cada auto, haremos lo siguente.... veremos cuantos autos con velocidad mayor a la suya hay en v[]... (en v tenemos solo autos que ya han sido procesados, o sea, estan mas cerca de la partida que el dicho) luego, la suma de estos autos, la sumamos a "ans", representanto la cantidad de adelantamientos realizados pos los autos en v, al auto que estamos procesando. Asi... for(i = 0; i < N; i++) for(j = c .speed + 1; j < MAX_SPEED; j++)
ans += v[j];
hasta aqui seria la solucion de N^2, que tomaria horas al PC para resolver...
Altiro posteo la optimizada....
12
« en: Lunes 23 de Agosto de 2004, 14:51 »
while(a >  // para a > b codigo... ************** rec() { codigo; rec(); }
13
« en: Domingo 22 de Agosto de 2004, 21:24 »
Que le parece si lo replanteamos asi: De cuantas maneras se puede hacer un bucle infinito? nada mas para ver que tantas formas hay...
14
« en: Sábado 21 de Agosto de 2004, 14:59 »
una forma seria que escribieras una biblioteca de grandes numeros (almacenados en vectores)...
Eso es, suma, resta, multiplicacion y division para estos.
En ingles se llaman BIG NUMS, busca en google, de seguro podras encontrar las funciones.
Espero que te sirva.
15
« en: Viernes 20 de Agosto de 2004, 04:19 »
yo se como sacar rapidamente potencias con numeros binarios 
16
« en: Jueves 19 de Agosto de 2004, 15:30 »
no se si tiene algo que ver, pero tal vez tu DOS este en ingles y no tenga "enie"
estas seguro que 164 te da enie en DOS?
haz asi: printf("%c", 164);
17
« en: Jueves 19 de Agosto de 2004, 14:27 »
No te capto...
Si te refieres a los problemas, son de olimpiadas para alumnos de secundaria.
Son de olimpiadas como la IOI.
18
« en: Lunes 16 de Agosto de 2004, 18:20 »
se supone que hay una o mas personas tratando de solucionar los anteriores.... espero que lo hagan... en una semana posteo soluciones...
19
« en: Lunes 16 de Agosto de 2004, 14:38 »
Bueno, ya que ninguno de los anteriores fue resuelto... demosle la bienvenida al ultimo que posteo, por lo menos sera facil:
Descripcion:
Encontrar una subsequencia de numeros de largo N (2 <= N <= 100 000 000) de la sequencia dada, de modo que la suma de todos los numeros de la subsequencia sea divisible por K (2 <= K <= 10 000 000).
Entrada:
En la primera linea: dos enteros: N y K
En la segunda: N enteros
Salida:
En la primera linea, 2 enteros: i, j (denotando que la sequencia encerrada entre Si... Sj, es la secuencia deseada).... para un i <= j.
Ejemplo:
Entrada:
7 10
2 4 3 5 2 7 2
Salida:
3 5
Explicacion:
S(3) --> 3
S(4) --> 5
S(5) --> 2
3 + 5 + 2 = 10
10 % 10 = 0.
Saludos....
P.D. Por favor, nada de N^2 o N^3 porque N es bastante grande.
20
« en: Domingo 15 de Agosto de 2004, 16:20 »
Haz que cada hijo se comunique con el padre, y el les de las nuevas instrucciones.
Podria ser esto una solucion?
21
« en: Sábado 14 de Agosto de 2004, 16:22 »
Sinceramente, creo que las ordenaciones no son la respuesta. Ademas, siendo dos for anidados, la velocidad no podria mejorar drasticamente.
Si te fijas bien, hay un for que no varia... es el de por todos los autos, luego debemos responder de la forma mas rapida posible ( lg(n)) o similar, "cuantos autos hasta los analizados tienen una velocidad mayor que el que estamos calculando ahora".
Esto es porque recorremos los autos por posicion inicial, y el que estamos analizando esta mas adelante que todos los analizados hasta ahora, por eso, solo nos interesa: de los analizados hasta ahora, cuantos superan la velocidad de este.
Hay una estructura que permite responder a esta pregunta en lg(N) y modificar los datos para cada proximo auto en lg(n) tambien... asi que para cada auto tendriamos 2*lg(V), (v = posibles velocidades), lo que nos da una complijidad de N*2*lg(V) o O(N*lgN)
Saludos...
22
« en: Sábado 14 de Agosto de 2004, 15:02 »
TIenes razon, por alli va el reto Por algo le puse facil... es cosa de pensar lo que se busca... conociendo algunas estructuras basicas, no esta de mas... Suerte! Salu2!
23
« en: Sábado 14 de Agosto de 2004, 02:14 »
for I := 1 to CantAut do begin for J := I+1 to CantAut do
con esto ya me queda claro que no esta resuelto Tu metodo es O(N^2). Eso demoraria hasta la eternidad.... 1M ^2 = 1E12... hmmm como una hora. Busco una solucion N*lgN... si no... seria demasiado facil, no? ...... Por lo demas... tu solucion parece buena (aunque no la he probado) Eso si, trata de encontrar algo mas rapido... porque aunque fueran 100M autos, igual se podria, suerte! Saludos
24
« en: Viernes 13 de Agosto de 2004, 18:48 »
%lld
25
« en: Viernes 13 de Agosto de 2004, 14:56 »
y? Ya tienes la solucion? Es cosa de codificarla en 12-15 mins hombre... la idea es obvia... No, no, no, no entiendo, como alguien se sienta a escribir posts en vez de codificar un problemita... lol.
|
|
|
Mostrar Mensajes
