Retos C/C++

[[L]ord [R]NA]

no tan simple pero que no rompa craneos.

[ghastlyX]

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 <= 10⁹.

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

Ejemplo:

Entrada:

Código [Seleccionar] Expandir

5
1 3
2 4
3 5
1 2
5 6

Salida:

Código [Seleccionar] Expandir

3

Nota: Por las restricciones que he puesto, se acepta una solución O(N²), 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).

[Dznp]

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

[[L]ord [R]NA]

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.

[ghastlyX]

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.

[ghastlyX]

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 (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

typedef pair<int, int> PII;

bool comp(PII a, PII b) {
    return (a.second < b.second) or (a.second == b.second and a.first < b.first);
}

int main() {
    int n;
    cin >> n;
    vector<PII> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end(), comp);
    int cnt = 0, ant = -1;
    for (int i = 0; i < n ; ++i) {
        if (v[i].first >= ant) {
            ++cnt;
            ant = v[i].second;
        }
    }
    cout << cnt << endl;
}


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(N²).

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

typedef pair<int, int> PII;

int main() {
    int n;
    cin >> n;
    vector<PII> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end());
    vector<int> M(n);
    int res = 0;
    for (int i = 0; i < n ; ++i) {
        M[i] = 1;
        for (int j = 0; j < i; ++j)
            if (v[j].second <= v[i].first) M[i] = max(M[i], M[j] + 1);
        res = max(res, M[i]);
    }
    cout << res << endl;
}


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.

[[L]ord [R]NA]

bueno GhastlyX coloca otro reto, pero que no sea tan fuerte...

[ghastlyX]

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

[[L]ord [R]NA]

Reto#13 Considerese el siguiente algoritmo:

Código [Seleccionar] Expandir


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 [Seleccionar] Expandir

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 [Seleccionar] Expandir

1 10
Salida:

Código [Seleccionar] Expandir

1 10 20

[[D4N93R]]

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 (ocaml) [Seleccionar] Expandir


open System

//forma 1 dos ciclos no usa funcion externa
let r i j=
   let mutable t = 0
   for i in i .. j do
       let mutable n = i
       let mutable x = 2
       while n <> 1 do
           if n % 2 = 1 then n <- 3*n+1 else n <-n/2
           if x > t then t <- x
           x <- x + 1
   t

//funcion para la forma 2 y 3        
let rec gcd n y =
   if n = 1 then y
   else match n % 2 with
       | 1 -> gcd (3*n+1) y + 1
       | _ -> gcd ( n/2) y + 1


//forma 2
let r2 i j =
   let mutable m = 0
   let mutable o = 0
   for i in i .. j do
       o <- gcd i 1
       if o > m then m <- o
   m

//forma 3
let rec r3 i j n=
   if i = j then n
   else let e = gcd i 1
       r3 (i+1) j (match e > n with |true -> e |_ -> n)

let a  = Console.ReadLine() |> int
let b  = Console.ReadLine() |> int

printfn "r  %A" (r a b)
printfn "r2 %A" (r2 a b)
printfn "r3 %A" (r3 a b 1)

Console.ReadKey(true);



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!