Viernes 15 de Noviembre de 2024, 02:00
SoloCodigo
Bienvenido(a),
Visitante
. Por favor,
ingresa
o
regístrate
.
¿Perdiste tu
email de activación?
Inicio
Foros
Chat
Ayuda
Buscar
Ingresar
Registrarse
SoloCodigo
»
Foros
»
Asuntos Oficiales
»
Retos
»
La Carrera
« anterior
próximo »
Imprimir
Páginas: [
1
]
Autor
Tema: La Carrera (Leído 9577 veces)
Binary
Miembro activo
Mensajes: 66
La Carrera
«
en:
Miércoles 11 de Agosto de 2004, 18:35 »
0
NIVEL: FACIL
Intro: no tengo
Descripcion:
Se tiene una pista de carreras recta e infinita.
En ella, hay un punto de partida.
Hay N autitos (2 <= N <= 1 000 000) que empiezan estacionados a Xi km del punto de partida. Asi... el auto 'i' esta a Xi kms.
Al empezar la carrera, todos los autos empezaran a moverse hacia la misma direccion, alejandose del punto de partida.
Cada auto tendra una velocidad determinada Vi (para el auto 'i') (1 <= vi <= 1 000 000).
Por facilidad, el largo de cada auto es 0, al igual que el ancho, y el tiempo de aceleracion desde la partida hasta alcanzar la velocidad maxima es 0.
Tarea:
Determinar las veces que ocurrira un adelantamiento, es decir, un auto adelantara a otro, si y solo si, el primero estuvo mas cerca del punto de partida que el segundo, y tiene una velocidad mayor.
Entrada (race.in):
En la primera linea: un entero N.
En lineas 2..N+1: 2 enteros: la distancia del auto 'i' del punto de partida y la velocidad del auto 'i'.
Salida (race.out):
Un solo entero: la cantidad de veces que ocurrira un adelantamiento modulo 1 000 000.
Ejemplo:
4
0 2
2 1
3 8
6 3
El primer auto (que empieza en 0 y tiene una velocidad de 2) adelantara al segunto (que empieza en 2 pero se mueve mas lento).
El tercero, adelantara al 4to porque empieza alntes que el y tiene una velocidad mayor.
Por lo tanto, la salida sera:
2
-----------------
Espero que alguien de una solucion por alli. Y no me vengan con que es muy complicado!!! Ya que ese si que es facil !!!
Tweet
Enko
Miembro de PLATA
Mensajes: 1562
Nacionalidad:
Re: La Carrera
«
Respuesta #1 en:
Jueves 12 de Agosto de 2004, 19:50 »
0
No te enojes de eso que nadie resuelve tus retos, simplemento da la desgracia que el mundo esta dividido en dos hemisferios, cuendo en uno es verano(vacaciones) en otro es invierno(escuela que roba tiempo mas que el gobierno dinero
) y eso hace que no todo el mundo tenga tiempo libre para disfrutarlo programando.
Binary
Miembro activo
Mensajes: 66
Re: La Carrera
«
Respuesta #2 en:
Viernes 13 de Agosto de 2004, 00:08 »
0
Yo soy del hemisferio sur.
Enko
Miembro de PLATA
Mensajes: 1562
Nacionalidad:
Re: La Carrera
«
Respuesta #3 en:
Viernes 13 de Agosto de 2004, 00:19 »
0
¿Pero no estabas de vacaciones? ¿Como puede ser ?
Binary
Miembro activo
Mensajes: 66
Re: La Carrera
«
Respuesta #4 en:
Viernes 13 de Agosto de 2004, 02:44 »
0
2 semanas... vacaciones de invierno
(Yo voy al colegio, soy estudiante de secundaria)
Enko
Miembro de PLATA
Mensajes: 1562
Nacionalidad:
Re: La Carrera
«
Respuesta #5 en:
Viernes 13 de Agosto de 2004, 02:54 »
0
Ya entendí.
Yo igual solo que tengo la mala suerte de ir a una secundaria tecnica con doble turno (a la mañana y a la tarde
)
Binary
Miembro activo
Mensajes: 66
Re: La Carrera
«
Respuesta #6 en:
Viernes 13 de Agosto de 2004, 04:57 »
0
Vas 2 veces a la escuela al dia?!?
WOW, has de saber demasiado ya!!!
Blag
Moderador
Mensajes: 697
Re: La Carrera
«
Respuesta #7 en:
Viernes 13 de Agosto de 2004, 07:15 »
0
Yo trabajo de 8:30 a.m a 5:30 p.m (Gracias a dios....Programando
) y de 6:15 p.m a 10:45 p.m tengo clases en la Universidad......(Gracias a dios....Termino en Marzo
).....
Así que mi único tiempo para programar en otra cosa que no sea ABAP.....Es de 12:00 a.m a 1:00 a.m......Porque después de eso, estoy durmiendo
Saludos,
Blag
Alvaro Tejada Galindo
Consultor ABAP Senior - Freelancer
SinglePath's Experimental HomePage
Revista "Código Latino"
Blag's Blogs en SDN
Lenguajes Script y SAP
Mi Blog Personal
Binary
Miembro activo
Mensajes: 66
Re: La Carrera
«
Respuesta #8 en:
Viernes 13 de Agosto de 2004, 14:56 »
0
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.
Enko
Miembro de PLATA
Mensajes: 1562
Nacionalidad:
Re: La Carrera
«
Respuesta #9 en:
Viernes 13 de Agosto de 2004, 23:12 »
0
Es más facil escribir un post. Soy un BAGO
, tal vez sean 15-20 min estando fresquito pero el cansamcio no lo puede todo. Despues de la escuela
(7:20 a 12:50 y de 14:10 hasta 18:10) quedo con la cabeza VACIA
de manera que no puedo pensar Y SI, SOY MUY BAGO.
Llendo las veces que voy, tengo muchos trabajos prácticos que llevan tiempo y son monotonos, asi que no aprendo tanto como parece.
Te prometo que este sábado intento hacer algo a ver que sale y esta vez va en serio.
No de verdad.
Enko
Miembro de PLATA
Mensajes: 1562
Nacionalidad:
Re: La Carrera
«
Respuesta #10 en:
Sábado 14 de Agosto de 2004, 00:38 »
0
Bueno es cierto es facil. No tenia ganas de hacerlo soy BAGO.
Tu entrada es
Citar
4
0 2
2 1
3 8
6 3
El Cuatro al principio lo borre ( seria el numero de coches), no me hizo falta.
Las velocidades de los autos tienen que ser escritas ordebnadas en orden ascendiente por su posición de salida como la has escrito en tu ejemplo.
El codigo fuente esta en Pascal ya que no era mi momento para C, Ultimamente no ando bien con el pero igual lo quiero mucho.
aqui esta el codigo fuente
<!--xc1--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>
XCODE
</td></tr><tr><td id='XCODE'><!--exc1-->
program
AdelantamientosDeCoches;
uses
CRT;
const
MaxVel =
100
;
MinVel =
1
;
MaxAut =
100
;
MinAut =
1
;
var
Entrada : TEXT;
I : Integer;
J : Integer;
Auto :
array
[MinAut..MaxAut]
of
WORD;
Vel :
array
[MinVel..MaxVel]
of
WORD;
CantAut : Integer;
Adelantos : Integer;
S :
string
;
Begin
TextMode(
3
);
TextColor(White);
WriteLn(
'Reto propuesto por Binary'
);
WriteLn(
''
);
TextColor(Blue);
WriteLn(
'Ingrese el nombre de la entrada NADA para entrada.txt'
);
Write(
'Nombre: '
);
ReadLn(S);
if
length(S)=
0
then
S :=
'Entrada.txt'
;
TextColor(
4
);
ClrScr;
WriteLn(
'Usando Entrada.txt'
);
WriteLn(
''
);
TextColor(
15
);
J :=
1
;
I :=
0
;
Adelantos :=
0
;
Assign(Entrada,S);
Reset(Entrada);
while
not
EOF(Entrada)
do
begin
I := I +
1
;
ReadLn(Entrada, Auto[I], Vel[I]);
WriteLn(Auto[I] ,
' '
, Vel[I]);
CantAut := I;
end
;
WriteLn(
''
);
TextColor(Yellow);
for
I :=
1
to
CantAut
do
begin
for
J := I+
1
to
CantAut
do
begin
TextColor(Blue);
Write(J,
': '
);
TextColor(Green);
Write(Auto[J] ,
' '
, Vel[J]);
TextColor(White);
Write(
' vs '
);
TextColor(Red);
Writeln(Auto[I] ,
' '
, Vel[I]);
if
(Auto[I] < Auto[J])
and
(Vel[I] > Vel[J])
then
Adelantos := Adelantos +
1
;
end
;
end
;
TextColor(
15
);
WriteLn(
''
);
WriteLn(
''
);
WriteLn(
'Adelantos: '
, Adelantos);
WriteLn(
'CantAutos: '
, CantAut);
WriteLn(
''
);
TextColor(
4
);
WriteLn(
'EugenioEnko 2004'
);
ReadKey;
Close(Entrada);
End
.
<!--xc2--></td></tr></table><div class='postcolor'><!--exc2-->
Igualmente está en el archivo adjunto con la ejecutable. Probala y me contas.
El mensaje contiene
1 archivo adjunto
. Debes
ingresar
o
registrarte
para poder verlo y descargarlo.
Binary
Miembro activo
Mensajes: 66
Re: La Carrera
«
Respuesta #11 en:
Sábado 14 de Agosto de 2004, 02:14 »
0
Código: Text
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
Nagisa
Miembro MUY activo
Mensajes: 119
Nacionalidad:
Re: La Carrera
«
Respuesta #12 en:
Sábado 14 de Agosto de 2004, 11:50 »
0
hola!! Para ser de secundaria estas metiendo demasiada caña...
Yo no voy a ponerme en ello por que como dije tengo las mañanas para estudiar, las tardes para trabajar y las noches para estudiar tb (dormir es un lujo que no puedo permitirme
).
De todos modos este parece sencillo. Es contar los coches que empiezan detras de cada uno y con mayor velocidad. Para solucionar el problema de la complejidad cuadratica me imagino que habria que usar un coso tipo arbol o heap o algo asi. No obstante aun no lo he pensado...
Es que has escogido una mala epoca para poner retos... Yo estoy preparandome uno de numeros primos. Cuando lo saque yo os lo posteare, pero ya digo que sera por Octubre...
Binary
Miembro activo
Mensajes: 66
Re: La Carrera
«
Respuesta #13 en:
Sábado 14 de Agosto de 2004, 15:02 »
0
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!
Enko
Miembro de PLATA
Mensajes: 1562
Nacionalidad:
Re: La Carrera
«
Respuesta #14 en:
Sábado 14 de Agosto de 2004, 15:42 »
0
Me base en la Ordenacion de Burbuja ya que no tenia ganas de complicarme en velocidad (no decia un límite) pero veo que tendré que cambiarlo por otro, Ordenacion por fusion. ¿No?
Binary
Miembro activo
Mensajes: 66
Re: La Carrera
«
Respuesta #15 en:
Sábado 14 de Agosto de 2004, 16:22 »
0
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...
Enko
Miembro de PLATA
Mensajes: 1562
Nacionalidad:
Re: La Carrera
«
Respuesta #16 en:
Miércoles 18 de Agosto de 2004, 00:05 »
0
La escuela me ha lavado el cerebro. Trate de solucionar el reto jugando el V Rally
(se nota que ya no se que hacer).
Traté hacer algo el sabado pero no me salió. Se me vienen como 5 examenes en la semana que viene así que no tendré tiempo para programar(la solucioón debe ser corta, pero no tengo práctica en algoritmos maniosos y se me complica). Además estaba aprendiendo algo de programación gráfica mientras desarollaba una pobre librería de este tipo y todo tendrá que ser suspendido por los examenes.
Resumiendo: ME RINDO.
Binary
Miembro activo
Mensajes: 66
Re: La Carrera
«
Respuesta #17 en:
Martes 24 de Agosto de 2004, 00:08 »
0
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....
Binary
Miembro activo
Mensajes: 66
Re: La Carrera
«
Respuesta #18 en:
Martes 24 de Agosto de 2004, 00:12 »
0
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...
Binary
Miembro activo
Mensajes: 66
Re: La Carrera
«
Respuesta #19 en:
Martes 24 de Agosto de 2004, 00:47 »
0
Código: Text
// 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;
}
Imprimir
Páginas: [
1
]
« anterior
próximo »
SoloCodigo
»
Foros
»
Asuntos Oficiales
»
Retos
»
La Carrera