• Lunes 23 de Diciembre de 2024, 07:18

Autor Tema:  La Carrera  (Leído 9633 veces)

Binary

  • Miembro activo
  • **
  • Mensajes: 66
    • Ver Perfil
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 !!!

Enko

  • Miembro de PLATA
  • *****
  • Mensajes: 1562
  • Nacionalidad: 00
    • Ver Perfil
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 :angry: ) y eso hace que no todo el mundo tenga tiempo libre para disfrutarlo programando. :hola:

Binary

  • Miembro activo
  • **
  • Mensajes: 66
    • Ver Perfil
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: 00
    • Ver Perfil
Re: La Carrera
« Respuesta #3 en: Viernes 13 de Agosto de 2004, 00:19 »
0
¿Pero no estabas de vacaciones? ¿Como puede ser ? &lt;_&lt;

Binary

  • Miembro activo
  • **
  • Mensajes: 66
    • Ver Perfil
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: 00
    • Ver Perfil
Re: La Carrera
« Respuesta #5 en: Viernes 13 de Agosto de 2004, 02:54 »
0
Ya entendí. :P
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 :fire: )

Binary

  • Miembro activo
  • **
  • Mensajes: 66
    • Ver Perfil
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
    • Ver Perfil
    • http://atejada.blogspot.com
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  :lol: ) y de 6:15 p.m a 10:45 p.m tengo clases en la Universidad......(Gracias a dios....Termino en Marzo  B) ).....

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  :scream:

Saludos,

Blag  :devil:

Binary

  • Miembro activo
  • **
  • Mensajes: 66
    • Ver Perfil
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... :D

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: 00
    • Ver Perfil
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 :devil: ,  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 :blink:  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. :angel:
No de verdad. :devil:

Enko

  • Miembro de PLATA
  • *****
  • Mensajes: 1562
  • Nacionalidad: 00
    • Ver Perfil
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
    • Ver Perfil
Re: La Carrera
« Respuesta #11 en: Sábado 14 de Agosto de 2004, 02:14 »
0
Código: Text
  1.  
  2.  
  3.    for I := 1 to CantAut do
  4.       begin
  5.        for J := I+1 to CantAut do
  6.  
  7.  
  8.  

con esto ya me queda claro que no esta resuelto :D
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? :D

......
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: es
    • Ver Perfil
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...  :lightsabre:

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...  :whistling:

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
    • Ver Perfil
Re: La Carrera
« Respuesta #13 en: Sábado 14 de Agosto de 2004, 15:02 »
0
TIenes razon, por alli va el reto :D
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: 00
    • Ver Perfil
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
    • Ver Perfil
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: 00
    • Ver Perfil
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  :unsure:  (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. :adios:

Binary

  • Miembro activo
  • **
  • Mensajes: 66
    • Ver Perfil
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
    • Ver Perfil
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
    • Ver Perfil
Re: La Carrera
« Respuesta #19 en: Martes 24 de Agosto de 2004, 00:47 »
0
Código: Text
  1.  
  2. // Race
  3. #include &#60;stdio.h&#62;
  4. #define MAXV 1000001
  5. #define LOW_BIT(x) ((((x) - 1) ^ (x)) & (x))
  6.  
  7. int v[MAXV];
  8.  
  9. int query(int pos)
  10. {
  11.   int i, r = 0;
  12.   for(i = pos; i &#62; 0; i -= LOW_BIT(i))
  13.     r += v[i];
  14.   return r;
  15. }
  16.  
  17. void update(int pos, int val)
  18. {
  19.   int i;
  20.   for(i = pos; i &#60; MAXV; i += LOW_BIT(i))
  21.     v[i] += val;
  22. }
  23.  
  24. int main()
  25. {
  26.   int n, i, ans, pos, speed;
  27.   FILE *fin, *fout;
  28.  
  29.   fin = fopen(&#34;race.in&#34;, &#34;r&#34;);
  30.   fout = fopen(&#34;race.out&#34;, &#34;w&#34;);
  31.  
  32.   ans = 0;
  33.   fscanf(fin, &#34;%d&#34;, &n);
  34.   for(i = 0; i &#60; n; i++) {
  35.     fscanf(fin, &#34;%d %d&#34;, &pos, &speed);
  36.     ans += query(MAXV-1) - query(speed);
  37.     update(speed, 1);
  38.   }
  39.  
  40.   fprintf(fout, &#34;%d&#092;n&#34;, ans);
  41.  
  42.   fclose(fin);
  43.   fclose(fout);
  44.   return 0;
  45. }
  46.  
  47.