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

Binary · « **en:** Miércoles 11 de Agosto de 2004, 18:35 »

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

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

Yo soy del hemisferio sur.

Enko

¿Pero no estabas de vacaciones? ¿Como puede ser ?

Binary

2 semanas... vacaciones de invierno

(Yo voy al colegio, soy estudiante de secundaria)

Enko

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

Vas 2 veces a la escuela al dia?!?
WOW, has de saber demasiado ya!!!

Blag

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

Binary

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

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

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
</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>XCODE </td></tr><tr><td id='XCODE'>
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.

</td></tr></table><div class='postcolor'>

Igualmente está en el archivo adjunto con la ejecutable. Probala y me contas.

Binary

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

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

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

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

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

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

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

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

Código: Text

 
// Race
#include &#60;stdio.h&#62;
#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 &#62; 0; i -= LOW_BIT(i))
    r += v[i];
  return r;
}
 
void update(int pos, int val)
{
  int i;
  for(i = pos; i &#60; MAXV; i += LOW_BIT(i))
    v[i] += val;
}
 
int main()
{
  int n, i, ans, pos, speed;
  FILE *fin, *fout;
 
  fin = fopen(&#34;race.in&#34;, &#34;r&#34;);
  fout = fopen(&#34;race.out&#34;, &#34;w&#34;);
 
  ans = 0;
  fscanf(fin, &#34;%d&#34;, &n);
  for(i = 0; i &#60; n; i++) {
    fscanf(fin, &#34;%d %d&#34;, &pos, &speed);
    ans += query(MAXV-1) - query(speed);
    update(speed, 1);
  }
 
  fprintf(fout, &#34;%d&#092;n&#34;, ans);
 
  fclose(fin);
  fclose(fout);
  return 0;
}
 
 