elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Security Series.XSS. [Cross Site Scripting]


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Ejercicios
| | | |-+  Retos C/C++
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: 1 2 3 4 [5] 6 7 8 9 Ir Abajo Respuesta Imprimir
Autor Tema: Retos C/C++  (Leído 40,322 veces)
[L]ord [R]NA


Desconectado Desconectado

Mensajes: 1.513

El Dictador y Verdugo de H-Sec


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #40 en: 22 Agosto 2010, 16:02 pm »

:xD no tan simple pero que no rompa craneos.


En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #41 en: 22 Agosto 2010, 16:35 pm »

Pues pongo uno que es bastante conocido pero que es interesante si no se conoce.

Reto #12
Año 2546, un ladrón quiere cometer una serie de robos en tiendas. Concretamente, hay N tiendas y para cada una, tras una exitosa tarea de investigación, sabe en qué intervalo de tiempo no hay vigilancia (y podrá cometer el robo).

Nuestro ladrón puede teletransportarse de un sitio a otro de forma instantánea (los coches son cosa del pasado), pero sólo robará una tienda si puede dedicar el intervalo completo sin vigilancia a robarla. Por ejemplo, si tenemos dos tiendas con intervalos [100, 200] y [200, 300], podrá robar las dos (recordemos que se puede teletransportar), pero si fueran [100, 200] y [199, 300] sólo podría robar una de las dos.

Entrada:
Un número N <= 1000, seguido de N líneas. En cada una de estas líneas habrá dos números X Y, indicando que la tienda i-ésima no tiene vigilancia en ese intervalo de tiempo. Se cumplirá que 0 <= X,Y <= 109.

Salida:
El máximo número de tiendas que podrá robar.

Ejemplo:

Entrada:
Código:
5
1 3
2 4
3 5
1 2
5 6

Salida:
Código:
3

Nota: Por las restricciones que he puesto, se acepta una solución O(N2), que se puede lograr haciendo una dinámica muy sencilla. Este problema de los intervalos es conocido como típico problema greedy, pues existe una solución greedy O(NlogN).


En línea

Dznp

Desconectado Desconectado

Mensajes: 119


Ver Perfil
Re: Retos C/C++
« Respuesta #42 en: 22 Agosto 2010, 16:56 pm »

:xD no tan simple pero que no rompa craneos.

3) No publicar para decir cosas que no tengan que ver con la solucion al reto o para postear un nuevo reto.


Es gracioso... Porque hace 3 dias me dijiste exactamente lo mismo por poner una respuesta que no tenga que ver con un reto.
Me parece que te crees capas de hacer lo que quieras por ser el creador, pero si pones reglas cumplilas vos también ;)
En línea

[L]ord [R]NA


Desconectado Desconectado

Mensajes: 1.513

El Dictador y Verdugo de H-Sec


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #43 en: 22 Agosto 2010, 17:16 pm »

:xD no tan simple pero que no rompa craneos.

3) No publicar para decir cosas que no tengan que ver con la solucion al reto o para postear un nuevo reto.


Es gracioso... Porque hace 3 dias me dijiste exactamente lo mismo por poner una respuesta que no tenga que ver con un reto.
Me parece que te crees capas de hacer lo que quieras por ser el creador, pero si pones reglas cumplilas vos también ;)

Si te fijas el hizo una pregunta... es de mala educacion no contestarla.
En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #44 en: 23 Agosto 2010, 22:46 pm »

Como veo que no hay soluciones, os digo el nombre del problema que os he puesto, que como ya dije es bastante conocido como típico problema greedy, a ver si así aparece alguna solución. El problema se conoce como Activity selection problem.
En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #45 en: 25 Agosto 2010, 16:35 pm »

Han pasado tres días y no hay soluciones, así que explico como se resuelve (aunque si se buscaba en Google el nombre del problema tal y como dije, explica en muchos sitios diferentes la solución).

La solución más eficiente es un algoritmo greedy que consiste en ordenar los intervalos por hora de final. Una vez hecho esto, se coge el primero y se va cogiendo el siguiente que no solape con el último cogido.
Código
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <map>
  5. using namespace std;
  6.  
  7. typedef pair<int, int> PII;
  8.  
  9. bool comp(PII a, PII b) {
  10.    return (a.second < b.second) or (a.second == b.second and a.first < b.first);
  11. }
  12.  
  13. int main() {
  14.    int n;
  15.    cin >> n;
  16.    vector<PII> v(n);
  17.    for (int i = 0; i < n; ++i) cin >> v[i].first >> v[i].second;
  18.    sort(v.begin(), v.end(), comp);
  19.    int cnt = 0, ant = -1;
  20.    for (int i = 0; i < n ; ++i) {
  21.        if (v[i].first >= ant) {
  22.            ++cnt;
  23.            ant = v[i].second;
  24.        }
  25.    }
  26.    cout << cnt << endl;
  27. }
  28.  

El último for de este algoritmo es lineal, por lo que la complejidad se ve dominada por el coste de ordenar, que usando un algoritmo eficiente como por ejemplo Merge Sort deja una complejidad de O(NlogN).

Otra solución menos eficiente pero válida con las restricciones que puse es la dinámica cuadrática que se puede hacer en función de la N, que tiene complejidad O(N2).
Código
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <map>
  5. using namespace std;
  6.  
  7. typedef pair<int, int> PII;
  8.  
  9. int main() {
  10.    int n;
  11.    cin >> n;
  12.    vector<PII> v(n);
  13.    for (int i = 0; i < n; ++i) cin >> v[i].first >> v[i].second;
  14.    sort(v.begin(), v.end());
  15.    vector<int> M(n);
  16.    int res = 0;
  17.    for (int i = 0; i < n ; ++i) {
  18.        M[i] = 1;
  19.        for (int j = 0; j < i; ++j)
  20.            if (v[j].second <= v[i].first) M[i] = max(M[i], M[j] + 1);
  21.        res = max(res, M[i]);
  22.    }
  23.    cout << res << endl;
  24. }
  25.  

La idea de la dinámica es que M[ i] representa el máximo número de intervalos que puedo coger usando el i-ésimo en último lugar. Como están ordenados los intervalos por inicio (en el otro se ordenaba por final), el algoritmo planteado es correcto.
En línea

[L]ord [R]NA


Desconectado Desconectado

Mensajes: 1.513

El Dictador y Verdugo de H-Sec


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #46 en: 25 Agosto 2010, 18:15 pm »

:xD bueno GhastlyX coloca otro reto, :xD pero que no sea tan fuerte...
En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #47 en: 25 Agosto 2010, 18:21 pm »

Según las normas tras tres días cualquiera puede poner otro reto, mejor que lo ponga otro, que yo puse este último con intención de que fuera muy sencillo...
En línea

[L]ord [R]NA


Desconectado Desconectado

Mensajes: 1.513

El Dictador y Verdugo de H-Sec


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #48 en: 25 Agosto 2010, 18:32 pm »

Reto#13 Considerese el siguiente algoritmo:

Código:
1. input n
2. print n
3. if n = 1 then stop
4. if n is odd then n=3n+1
5. else n=n/2
6. goto 2

tomando la entrada 7 la siguiente secuencia es imprimida:

Código:
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

La entrada: Consiste en un par de enteros 'i' y 'j', los enteros deben estar comprendidos entre 0<=x<=1,000,000

El Problema: Determinar el ciclo mas largo entre 'i' y 'j'.

La salida: Se colocara en pantalla el valor de 'i', 'j' y el valor del mayor ciclo entre los valores de 'i' y 'j'

Ejemplo:

Entrada:
Código:
1 10
Salida:
Código:
1 10 20
« Última modificación: 25 Agosto 2010, 18:46 pm por Lord R.N.A. » En línea

[D4N93R]
Wiki

Desconectado Desconectado

Mensajes: 1.646


My software never has bugs. Its just features!


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #49 en: 27 Agosto 2010, 01:14 am »

Bueno, por ahora no toy seguro si es la mejor forma de hacerlo, sigo trbajando en ello, se que hay otras formas, pero no logro hacerlo aún ya que tengo unos pequeños problemas con sequences y mutable types.

F#
Código
  1. open System
  2.  
  3. //forma 1 dos ciclos no usa funcion externa
  4. let r i j=
  5.    let mutable t = 0
  6.    for i in i .. j do
  7.        let mutable n = i
  8.        let mutable x = 2
  9.        while n <> 1 do
  10.            if n % 2 = 1 then n <- 3*n+1 else n <-n/2
  11.            if x > t then t <- x
  12.            x <- x + 1
  13.    t
  14.  
  15. //funcion para la forma 2 y 3        
  16. let rec gcd n y =
  17.    if n = 1 then y
  18.    else match n % 2 with
  19.        | 1 -> gcd (3*n+1) y + 1
  20.        | _ -> gcd ( n/2) y + 1
  21.  
  22.  
  23. //forma 2
  24. let r2 i j =
  25.    let mutable m = 0
  26.    let mutable o = 0
  27.    for i in i .. j do
  28.        o <- gcd i 1
  29.        if o > m then m <- o
  30.    m
  31.  
  32. //forma 3
  33. let rec r3 i j n=
  34.    if i = j then n
  35.    else let e = gcd i 1
  36.        r3 (i+1) j (match e > n with |true -> e |_ -> n)
  37.  
  38. let a  = Console.ReadLine() |> int
  39. let b  = Console.ReadLine() |> int
  40.  
  41. printfn "r  %A" (r a b)
  42. printfn "r2 %A" (r2 a b)
  43. printfn "r3 %A" (r3 a b 1)
  44.  
  45. Console.ReadKey(true);
  46.  


EDIT:

PD: Se que la idea es hacerlo en C++, pero es que no tengo más nada que hacer :)

EDIT 2:
Coloco 2 formas más de hacerlo siguiendo el mismo algoritmo, solo lo hago para aprender F# más nada.
Nota: ghastlyX, estoy pensando en lo que me dijiste, un saludo!
« Última modificación: 27 Agosto 2010, 02:54 am por [D4N93R] » En línea

Páginas: 1 2 3 4 [5] 6 7 8 9 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Retos .Net « 1 2 3 »
Ejercicios
[D4N93R] 20 14,326 Último mensaje 6 Diciembre 2010, 03:26 am
por final_frontier
Concursos y retos
Programación General
lnvisible 0 1,386 Último mensaje 12 Diciembre 2010, 19:44 pm
por lnvisible
cuando consigo nuevos retos? « 1 2 »
WarZone
Tyrz 11 3,942 Último mensaje 15 Junio 2011, 23:11 pm
por [-Franko-]
Desarrollo de Retos Informaticos
Desarrollo Web
Sinedra 0 2,370 Último mensaje 23 Febrero 2011, 19:23 pm
por Sinedra
Retos C/C++
Programación C/C++
N0body 5 9,101 Último mensaje 9 Mayo 2011, 09:54 am
por ghastlyX
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines