Foro de elhacker.net

Programación => Ejercicios => Mensaje iniciado por: [L]ord [R]NA en 19 Agosto 2010, 03:18 am



Título: Retos C/C++
Publicado por: [L]ord [R]NA en 19 Agosto 2010, 03:18 am
Bueno, esta zona esta un poco muerta por lo tanto no cuesta nada tratar de revivirla.

Tomando las mismas reglas que la del pasado post de retos de Python que se hizo en esta zona haremos uno en C/C++.

Reglas:

1) Se empezara con un ejercicio, quien lo resuelva propone otro ejercicio y asi seguimos.
2) Los ejercicios tendran un tiempo de vida de 3 dias, si en exactamente 3 dias alguien no publica una solucion alguien podra proponer otro ejercicio.
3) No publicar para decir cosas que no tengan que ver con la solucion al reto o para postear un nuevo reto.
4) Numerar los retos (Ej. Reto#1)


Bueno ya que yo postee, seria de mala educacion dejar que otro ponga el reto.



Reto#1: Realizar un programa que reciba un numero como argumento y diga si es primo o no.

PData: No estoy estudiando C/C++ actualmente en la universidad... (Para los que diran que es una tarea.)


Título: Re: Retos C/C++
Publicado por: Og. en 19 Agosto 2010, 03:28 am
Se me paso lo de la entrada por argumento XD
Editado...

Código
  1. #include <iostream>
  2.  
  3. using std::cout;
  4. using std::endl;
  5.  
  6. int getNum(char* text)
  7. {
  8.    int a=0, cont=0;
  9.    while(text[cont])
  10.    {
  11.        a *= 10;
  12.        a += text[cont++] - '0';
  13.    }
  14.    return a;
  15. }
  16.  
  17. int main(int argc, char** argv)
  18. {
  19.    int num;
  20.    num = getNum(argv[1]);
  21.    for(int i=2;i<=num/2;i++)
  22.        if(!(num%i))
  23.        {
  24.            cout << "No es primo" << endl;
  25.            return 0;
  26.        }
  27.    cout << "Es primo" << endl;
  28.    return 0;
  29. }
  30.  
Reto #2
Realiza un programa que dado un numero n te imprima todas las posibles permutaciones del conjunto 1 a n ordenadas de menor a mayor.

Ejemplo 1:

Entrada
Código:
3

Salida
Código:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Ejemplo 2:

Entrada
Código:
4

Salida
Código:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1


Título: Re: Retos C/C++
Publicado por: Leyer en 19 Agosto 2010, 05:31 am
Código
  1. #include <iostream>
  2. #include <string>
  3. #include <sstream>
  4. using namespace std;
  5. void String(string a,string b);
  6. int main(int argc, char *argv[]) {
  7.    string n="";
  8.    ostringstream stm;
  9.    int value=0;cin>>value;
  10.        for(int index=1;index<=value;index++){
  11.        stm<<index;
  12.            n=stm.str();
  13.        }String("",n);
  14.    return 0;
  15. }
  16. void String(string a, string b) {
  17.    if(b.length() <= 1)
  18.    cout<<a + b+"\n";
  19.    else
  20.    for (int i = 0; i < b.length(); i++) {
  21.        string n = b.substr(0, i) + b.substr(i + 1);
  22.        String(a + b.at(i), n);
  23.      }
  24.  }
  25.  

Reto #3

No me critiquen por lo fácil jaja XDDDD

Generar esta matriz para un entero N dado:

si se ingresa 4

1 0 0 0 0
1 2 0 0 0
1 2 3 0 0
1 2 3 4 0


Título: Re: Retos C/C++
Publicado por: Og. en 19 Agosto 2010, 06:09 am
Código
  1. #include <iostream>
  2.  
  3. using std::cin;
  4. using std::cout;
  5. using std::endl;
  6.  
  7. int main(void)
  8. {
  9.    int N;
  10.    cin >> N;
  11.    for(int i=0;i<N;i++)
  12.    {
  13.        for(int g=0; g<=i; g++)
  14.            cout << g+1 << " ";
  15.        for(int g=i; g<N; g++)
  16.            cout << 0 << " ";
  17.        cout << endl;
  18.    }
  19.    return 0;
  20. }
  21.  

Reto #4

Dadas las denominaciones de monedas que tienen disponibles y una cantidad de dinero que tienen que dar de cambio con esas denominaciones de monedas (supongan que tienen una infinidad de monedas de cada denominacion y que siempre tienen monedas de $1) escriban un programa que regrese la cantidad MINIMA de monedas necesarias para regresar ese cambio, por ejemplo:

{$1, $2, $5} y cambio de $9
la cantidad minima de monedas es 3 ($5 + $2 + $2 = $9)

{$1, $5, $7} y cambio de $10
la cantidad minima de monedas es 2 ($5 + $5 = $10)

por cierto, te puedo pedir el cambio de $3000 xD

una ves que hagan este problema, muchos se darán cuenta de lo hermosa que es la resolución que le da nuestro cerebro a las cosas.


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 19 Agosto 2010, 07:16 am
Código
  1. #include <iostream>
  2. #include <cstdlib>
  3.  
  4. using std::cout;
  5. using std::endl;
  6.  
  7. struct cambio
  8. {
  9. int uno;
  10. int cinco;
  11. int diez;
  12. int veinte;
  13. int cincuenta;
  14. int cien;
  15. int total;
  16. };
  17.  
  18.  
  19. int main(int argc,char *argv[])
  20. {
  21. int valor = atoi(argv[1]);
  22. if (valor!=0)
  23. {
  24. cambio *monedas = new cambio;
  25.  
  26. while(valor>=100)
  27. {
  28. monedas->cien++;
  29. monedas->total++;
  30. valor -=100;
  31. }
  32.  
  33. while(valor>=50)
  34. {
  35. monedas->cincuenta++;
  36. monedas->total++;
  37. valor -=50;
  38. }
  39.  
  40. while(valor>=20)
  41. {
  42. monedas->veinte++;
  43. monedas->total++;
  44. valor -=20;
  45. }
  46.  
  47. while(valor>=10)
  48. {
  49. monedas->diez++;
  50. monedas->total++;
  51. valor -=10;
  52. }
  53.  
  54. while(valor>=5)
  55. {
  56. monedas->cinco++;
  57. monedas->total++;
  58. valor -=5;
  59. }
  60.  
  61. while(valor>=1)
  62. {
  63. monedas->uno++;
  64. monedas->total++;
  65. valor -=1;
  66. }
  67.  
  68. cout<<"Total de Monedas: "<<monedas->total<<endl<<endl;
  69. cout<<"Valores: \n"<<"Cien: "<<monedas->cien<<endl;
  70. cout<<"Cincuenta: "<<monedas->cincuenta<<endl;
  71. cout<<"Veinte: "<<monedas->veinte<<endl;
  72. cout<<"Diez: "<<monedas->diez<<endl;
  73. cout<<"Cinco: "<<monedas->cinco<<endl;
  74. cout<<"Uno: "<<monedas->uno<<endl;
  75.  
  76. }
  77. else
  78. {
  79. cout<<"Valor no valido"<<endl;
  80.  
  81. }
  82. return 0;
  83. }
  84.  
  85.  

Reto#5 Dado un numero, encontrar todos los numeros perfectos inferiores a este.


Título: Re: Retos C/C++
Publicado por: leogtz en 19 Agosto 2010, 07:44 am
Código
  1. #include <iostream>
  2. #include <cstdlib>
  3. using std::cin;
  4. using std::cout;
  5. using std::endl;
  6. bool isperfect(const unsigned int& n)
  7. {
  8.    unsigned int suma = 0;
  9.    for(register unsigned int i = 1; i < n; i++)
  10.    if(!(n % i))
  11.    suma += i;
  12.    return(suma == n);
  13. }
  14. int main(int argc, char **argv)
  15. {
  16.    if(argc != 2)
  17.        exit(EXIT_FAILURE);
  18.    for(register unsigned int i = 1; i <= atoi(*(argv + 1)); i++)
  19.    if(isperfect(i) && (i < atoi(*(argv + 1))))
  20.    cout << i << endl;
  21.    return 0;
  22. }

Reto:

Recorrer una matriz bidimensional con un puntero, con recorrer me refiero a mostrar cada uno de sus valores, no me refiero a indexación, sino a mostrar los valores usando aritmética de punteros.


Título: Re: Retos C/C++
Publicado por: Og. en 19 Agosto 2010, 07:54 am
no han resuelto el reto #4 XD

por ejemplo yo te digo que las monedas que puedes dar son $1, $5 y $7, haora dime cual es la minima cantidad de monedas para completar la cantidad de 25$

Ejemplo1:

Entrada
Código:
3
1 5 7
25

Salida
Código:
5

Ejemplo2:

Entrada
Código:
1
1
25

Salida
Código:
25


el primer entero es el numero de denominaciones
seguidas de n enteros que son los valores de las denominaciones
y después el precio.

devuelves simplemente el mínimo de monedas para lograr el precio.

PD: es mas complejo de lo que parece, son esos problemas en los que te tienes que estar un par de horas pensando...


Título: Re: Retos C/C++
Publicado por: leogtz en 19 Agosto 2010, 08:11 am

PD: es mas complejo de lo que parece, son esos problemas en los que te tienes que estar un par de horas pensando...

Sí, jaja, es por eso que aún no respondemos :p


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 19 Agosto 2010, 08:16 am
@Og.:Ni idea de que quieres en realidad, querias ver la cantidad minima de monedas para dar cambio y eso es que realiza el programa... ahora creo que estas re-planteando el problema variandolo.


Título: Re: Retos C/C++
Publicado por: Og. en 19 Agosto 2010, 08:22 am
@Og.:Ni idea de que quieres en realidad, querias ver la cantidad minima de monedas para dar cambio y eso es que realiza el programa... ahora creo que estas re-planteando el problema variandolo.
Tal ves me di a malentender. En si no seria un reto si se usara el sistema de monedas que usamos cotidianamente, por que simplemente vas quitando la mayor denominación hasta que no puedas mas y empezar con la siguiente y asi sucesivamente, por eso lo del cambio de denominaciones.

limitare un poco el problema, supondríamos que solo existen tres tipos de moneda:
un peso, 5 pesos y 7 pesos nada mas.

ahora has el mismo problema y veras por que empieza a agarrar complejidad XD

el problema sera solo saber cual es el mínimo de monedas para llegar a un numero.



Bueno, con el de Leo:
Código
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int main(void)
  6. {
  7.    int mat[5][5];
  8.    for(int i=0; i<5; i++)
  9.        for(int g=0; g<5;g++)
  10.            mat[i][g] = i*g;
  11.    int* a = mat[0];
  12.    for(int i=0;i<25;i++)
  13.    {
  14.        if(!(i%5))
  15.            cout << endl;
  16.        cout << *a++ << " ";
  17.    }
  18. }

te refieres a algo asi?


Título: Re: Retos C/C++
Publicado por: leogtz en 19 Agosto 2010, 08:52 am
Sí, así es.

La idea es poner problemas sencillitos e ir aumentando la dificultad.

Saludos.


Título: Re: Retos C/C++
Publicado por: Oblivi0n en 19 Agosto 2010, 10:43 am
Buenas, yo me apunto a los retos, alguien puede decirme cuales estan resueltos y cuales no? (aunque los acabaré haciendo todos xD)


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 19 Agosto 2010, 14:38 pm
@guru6: las reglas...
@Og.: Te falto dejar el proximo reto.


Título: Re: Retos C/C++
Publicado por: ghastlyX en 19 Agosto 2010, 15:15 pm
Para el de las monedas, el problema surge en que el algoritmo greedy de ir cogiendo siempre las monedas más grandes no minimiza la cantidad de monedas, como se puede ver en el primer ejemplo que se ha puesto.

Una posible solución correcta pero muy ineficiente sería un backtracking probando todas las posibles maneras. Una forma mejor, que dejo a continuación, sería usando programación dinámica, quedando entonces una complejidad polinómica, en concreto O(np), donde n es el número de monedas y p la cantidad. Quizá me haya equivocado en algo, pero creo que es correcto.
Código
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. const int INF = 1000000000;
  6.  
  7. int dp(int p, vector<int>& M, vector<int>& v) {
  8.    if (p < 0) return INF;
  9.    if (p == 0) return 0; //Caso base
  10.    if (M[p] == -1) {
  11.        M[p] = INF;
  12.        for (int i = 0; i < v.size(); ++i)
  13.            M[p] = min(M[p], 1 + dp(p - v[i], M, v));
  14.    }
  15.    return M[p];
  16. }
  17.  
  18. int main() {
  19.    int n, p;
  20.    cin >> n;
  21.    vector<int> v(n);
  22.    for (int i = 0; i < n; ++i) cin >> v[i]; //Lectura de las monedas
  23.    cin >> p;
  24.    vector<int> M(p + 1, -1); //Tabla para la dinamica
  25.    cout << dp(p, M, v) << endl;
  26. }


Título: Re: Retos C/C++
Publicado por: Og. en 19 Agosto 2010, 15:18 pm
@ghastlyX Bien!!

Te toca dejarnos un reto.


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 19 Agosto 2010, 15:23 pm
Og. coloca el reto#6, al parecer esta de acuerdo con la respuesta... numeralo y plantealo debajo de tu respuesta al de LeoGutierrez.


Título: Re: Retos C/C++
Publicado por: Og. en 19 Agosto 2010, 15:36 pm
Mejor lo pongo como nuevo Post, después podrían haber confusiones.

Reto #7

Este estara simple.

Dado un numero N devuelve un numero K tal que K! tenga N 0's al final y K sea el menor posible.

Ejemplo1

Entrada
Código:
1

Salida
Código:
5
Por que 5! = 120 hay estan los N ceros

Ejemplo2

Entrada
Código:
2

Salida
Código:
10
Por que 10! = 3628800 hay estan los N ceros

PD: N puede ser de hasta 109


Título: Re: Retos C/C++
Publicado por: ghastlyX en 19 Agosto 2010, 16:24 pm
A ver, está claro que hay que contar el número de parejas de factores 5 y 2 y como hay más doses que cincos, basta con contar los cincos si no me equivoco. De esta forma, dado un cierto K, para saber cuántos ceros tendrá K!, habrá que contar cuántas veces aparece cada una de las potencias de 5 si no me equivoco. Así, haciendo binaria sobre el resultado, me queda esto, aunque puede que haya algún error en el razonamiento.
Código
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. long long ceros(long long x) {
  5.    long long res = 0, pot = 5;
  6.    while (x/pot > 0) {
  7.        res += x/pot;
  8.        pot *= 5;
  9.    }
  10.    return res;
  11. }
  12.  
  13. int main() {
  14.    long long n;
  15.    cin >> n;
  16.    long long ini = 1, fin = 5*n;
  17.    while (ini <= fin) {
  18.        long long m = (ini+fin)/2;
  19.        if (ceros(m) >= n) fin = m - 1;
  20.        else ini = m + 1;
  21.    }
  22.    cout << fin + 1 << endl;
  23. }
  24.  


Título: Re: Retos C/C++
Publicado por: [D4N93R] en 19 Agosto 2010, 16:52 pm
Código
  1. #include "stdafx.h"
  2. #include <iostream>
  3. using namespace std;
  4.  
  5.  
  6. int _tmain(int argc, _TCHAR* argv[])
  7. {
  8. int n, fac;
  9. cin >> n;
  10. cout << "HUHU: " << n *5 << endl;
  11. return 0;
  12. }
  13.  

Sin comprobar ni nada xD para qué? todo factorial de K va atener mínimo N ceros al final xD


Título: Re: Retos C/C++
Publicado por: ghastlyX en 19 Agosto 2010, 17:06 pm
Pero te pide el menor K que cumpla eso y tu programa no devuelve el menor. Si la entrada es N = 6, tu programa devuelve 30 cuando el menor es 25.


Título: Re: Retos C/C++
Publicado por: [D4N93R] en 19 Agosto 2010, 17:13 pm
Seee lo sé xD era joda, ghastlyX te toca poner reto, no te hagas el loco,  no leiste las reglas? xD


Título: Re: Retos C/C++
Publicado por: ghastlyX en 19 Agosto 2010, 17:15 pm
Si es correcta mi solución pongo el siguiente, pero la he pensado rápido y quizá haya algún error. A ver que dice Og.


Título: Re: Retos C/C++
Publicado por: Og. en 19 Agosto 2010, 17:18 pm
@ghastlyX Correcto!! XD

les dije que sera simple hehe

Te toca poner reto :D


Título: Re: Retos C/C++
Publicado por: ghastlyX en 19 Agosto 2010, 17:22 pm
Pues os dejo el que he preparado mientras por si estaba bien.

Reto 8: Se tiene un corral con gallos y gallinas, de tal forma que entre todos suman N animales (no necesariamente hay N/2 de cada, de hecho no tiene porque ser N par) y los animales están numerados de 0 a N - 1, pero no se sabe qué número pertenece a cada animal.

Buscando entre los papeles del anterior dueño, se encuentran unos registros de apareamiento entre los animales, en forma A B, donde A y B son números entre 0 y N - 1 que indican que los animales A y B se aparearon (no se especifica cuál es el macho y cuál la hembra). Ahora el problema es ver si los registros encontrados son consistentes o no, es decir, si existe alguna manera de numerar los animales para que se puedan cumplir. Nótese que los gallos no se aparean entre ellos y lo mismo se aplica a las gallinas.

Entrada: Dos números N y M, donde M será el número de registros existentes. A continuación, M líneas con dos números cada una indicando un registro de apareamiento.

Salida: Si los datos son consistentes, se deberá escribir "Si", en caso contrario, "No".

Restricciones (para que no se hagan backtrackings más que nada): 3 <= N <= 10000, 0 <= M <= 100000.

Ejemplos:

Entrada 1:
Citar
3 2
0 1
1 2

Salida 1:
Citar
Si

Entrada 2:
Citar
3 3
0 1
1 2
2 0

Salida 2:
Citar
No


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 19 Agosto 2010, 18:57 pm
No estoy muy seguro... espero confirmacion de GhastlyX.
Los resultados coinciden con sus ejemplos.

Código
  1. #include <iostream>
  2.  
  3. using std::cout;
  4. using std::cin;
  5. using std::endl;
  6.  
  7. int consistencia(int v1[],int v2[],int lenght)
  8. {
  9. int temp;
  10. for(int i=0;i<lenght;i++)
  11. { int k=0;
  12. do{
  13. if(v2[k]==v1[i])
  14. {
  15. temp=v1[k];
  16. v1[k]=v2[k];
  17. v2[k]=temp;
  18. }
  19. k++;
  20. }while(k<temp);
  21. }
  22.  
  23. for(int i=0;i<lenght;i++)
  24. { int k=0;
  25. do{
  26. if(v2[k]==v1[i])return 1;
  27. k++;
  28. }while(k<lenght);
  29. }
  30. return 0;
  31. }
  32.  
  33. int main()
  34. {
  35. int Regs, *gen1, *gen2, i;
  36.  
  37. cout<<"Cantidad de Registros: ";
  38. cin>>Regs;
  39. gen1 = new int[Regs];
  40. gen2 = new int[Regs];
  41.  
  42. for(i;i<Regs;i++)
  43. {
  44. gen1[i]=-1;
  45. gen2[i]=-1;
  46. }
  47.  
  48. for(i=0;i<Regs;i++)
  49. {
  50. cout<<"1er Valor del registro "<<i+1<<" :";
  51. cin>>gen1[i];
  52. cout<<"2do Valor del registro "<<i+1<<" :";
  53. cin>>gen2[i];
  54. }
  55.  
  56. if(consistencia(gen1,gen2,Regs))cout<<"No son consistentes"<<endl;
  57. else{cout<<"Son Consistentes"<<endl;}
  58.  
  59. }
  60.  


Título: Re: Retos C/C++
Publicado por: ghastlyX en 19 Agosto 2010, 19:41 pm
¿Dónde lees en tu código la cantidad de animales (N)? Por lo que veo estás suponiendo que N = 3 como en los dos ejemplos que he puesto, pero como dice el enunciado, 3 <= N <= 10000. Es decir, la cantidad de animales también es un parámetro de la entrada, no sólo los registros.

Edito: Veo que tal y como lo haces no depende de la N, voy a ver si es correcto y te digo algo.

Revisado, no es correcto, te dejo un contraejemplo:
Citar
4 4
0 1
2 3
0 2
1 3

Tu programa dice que no son consistentes pero sí lo son. Por ejemplo, si 0 y 3 son gallos y 1 y 2 gallinas, todo cuadra.


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 19 Agosto 2010, 20:12 pm
¿Dónde lees en tu código la cantidad de animales (N)? Por lo que veo estás suponiendo que N = 3 como en los dos ejemplos que he puesto, pero como dice el enunciado, 3 <= N <= 10000. Es decir, la cantidad de animales también es un parámetro de la entrada, no sólo los registros.

Edito: Veo que tal y como lo haces no depende de la N, voy a ver si es correcto y te digo algo.

Revisado, no es correcto, te dejo un contraejemplo:
Citar
4 4
0 1
2 3
0 2
1 3

Tu programa dice que no son consistentes pero sí lo son. Por ejemplo, si 0 y 3 son gallos y 1 y 2 gallinas, todo cuadra.



Dice que es inconsistente por el
Código:
4 4
, entiende que ambos son el mismo animal.

Edito: Estas en lo cierto... tiene un error incluso excluyendo el error aparente del [4 4].


Título: Re: Retos C/C++
Publicado por: ghastlyX en 19 Agosto 2010, 20:30 pm
He puesto el caso siguiendo el formato de entrada como había dicho antes, lo que tu programa no lo sigue y cuando lo he evaluado en él ya lo he cambiado consecuentemente. A tu programa se lo he pasado así:
Citar
4
0 1
2 3
0 2
1 3
Es decir, le he dicho que hay cuatro registros y se los he puesto y dice que no son consistentes mientras que sí lo son. El 4 4 que tú decías si te fijas en el formato de la entrada en el enunciado, quiere decir que hay 4 animales y 4 registros, que se dan a continuación.

Edito: No había visto tu modificación. Y como te decía, lo del 4 4 no es un error, es la primera línea de la entrada. Fíjate en el enunciado del problema en el apartado de entrada.


Título: Re: Retos C/C++
Publicado por: cgvwzq en 20 Agosto 2010, 00:14 am
Bueno, aunque no es eficiente creo que la idea no es mala del todo. Solo he hecho las dos pruebas del enunciado y funciona bien, pero ya me dirás si he hecho algún disparate.

El caso es que los valores de 'N' y 'M' se pasan por argumento, y se van pidiendo las 'M' 2-tuplas de parejas, en el momento en que una viole el "tratado de nogays" se muestra el 'No'. Si el final es consistente mostrará el 'Si'. De cualquier forma podría mostrar el 'No' al final, eso es facilmente modificable...

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int noFuck (int **corral, int g1, int g2, int n);
  5. int addChicken (int **corral, int g1, int g2);
  6.  
  7. int main(int argc, char **argv) {
  8.  
  9.   int **corral, n, m, i, gays = 0;
  10.   int g1,g2;
  11.  
  12.   if (argc != 3) return 1;
  13.  
  14.   n = atoi(argv[1]);
  15.   m = atoi(argv[2]);
  16.  
  17.   if (!(corral = (int**)calloc(n,sizeof(int)))) return 1;
  18.   for (i=0;i<n;i++) if (!(corral[i] = (int*)calloc(n/sizeof(int),sizeof(int)))) return 1;
  19.  
  20.   while (m-- > 0 & !gays) {
  21.  
  22.      scanf("%d %d",&g1,&g2);
  23.      if (!noFuck(corral,g1,g2,n)) addChicken(corral,g1,g2);// añadimos g1 a parejas de g2 y viceversa
  24.      else gays = 1;
  25.  
  26.   }
  27.  
  28.   if (!gays) printf("Si\n"); else printf("No\n");
  29.  
  30.   for (i=0;i<n;i++) free(corral[i]); free(corral);
  31.  
  32.   return 0;
  33.  
  34. }
  35.  
  36. int noFuck (int **corral, int g1, int g2, int n) {
  37.  
  38.   int i;
  39.  
  40.   if (g1 == g2) return 1;
  41.   for (i=0;i<=n/sizeof(int);i++) if (corral[g1][i] & corral[g2][i]) return 1;
  42.   return 0;
  43.  
  44. }
  45.  
  46. int addChicken (int **corral, int g1, int g2) {
  47.  
  48.   corral[g1][g2/sizeof(int)] |= (g2%sizeof(int));
  49.   corral[g2][g1/sizeof(int)] |= (g1%sizeof(int));
  50.   return 0;
  51.  
  52. }

^^


Título: Re: Retos C/C++
Publicado por: ghastlyX en 20 Agosto 2010, 01:51 am
He mirado tu código y si lo he entendido bien, creas una matriz de adyacencia con máscaras de bits y cada vez que se añade una arista miras si hay un nodo intermedio que forme un camino alternativo entre ambos nodos, lo que conforma un ciclo de longitud 3 y por lo tanto una situación inconsistente.

Suponiendo que sea eso lo que estás haciendo (en caso contrario dímelo), la solución no es correcta puesto que aunque ese es un caso no consistente claramente, hay más casos "malos" que no detectas, por ejemplo, si tenemos cinco animales que formen con las relaciones un pentágono (un ciclo de longitud cinco).

El problema como bien has enfocado, se reduce a transformar la información en un grafo y decidir si el grafo es de un cierto tipo o no (sabiendo cómo, claro). Si veo que sigue sin salir, daré más pistas.


Título: Re: Retos C/C++
Publicado por: Og. en 20 Agosto 2010, 02:00 am
Buen problema. Así si son divertidos.
Código
  1. #include <iostream>
  2.  
  3. using std::cin;
  4. using std::cout;
  5. using std::endl;
  6.  
  7. struct pareja
  8. {
  9.    int h;
  10.    int m;
  11. };
  12.  
  13. pareja *relaciones;
  14. int N, M;
  15. short *pollos, *relacionesChk;
  16. bool correcto;
  17.  
  18. bool Relaciona(int);
  19. void entid(int num, int tp);
  20.  
  21. int main(void)
  22. {
  23.    cin >> N >> M;
  24.    pollos = new short[N];
  25.    relacionesChk = new short[M];
  26.    relaciones = new pareja[M];
  27.    for(int i=0; i<M; i++)
  28.        relacionesChk[i] = 0;
  29.    for(int i=0; i<M; i++)
  30.    {
  31.        cin >> relaciones[i].h >> relaciones[i].m;
  32.    }
  33.    correcto = true;
  34.    Relaciona(0);
  35.    if(correcto)
  36.        cout << "SI";
  37.    else
  38.        cout << "NO";
  39.    delete pollos;
  40.    delete relacionesChk;
  41.    delete relaciones;
  42. }
  43.  
  44. bool Relaciona(int num)
  45. {
  46.    if(!correcto)
  47.        return 0;
  48.    if(num>=M)
  49.        return true;
  50.    for(int i=0; i<N; i++)
  51.        pollos[i] = -1;
  52.    relacionesChk[num] = 1;
  53.    pollos[relaciones[num].h] = 0;
  54.    pollos[relaciones[num].m] = 1;
  55.    entid(relaciones[num].h, 1);
  56.    entid(relaciones[num].m, 0);
  57.    while(relacionesChk[++num] && num<=M);
  58.    Relaciona(num);
  59. }
  60.  
  61. void entid(int num, int tp)
  62. {
  63.    if(!correcto)
  64.        return;
  65.    for(int i=0; i<M; i++)
  66.        if(!relacionesChk[i])
  67.        {
  68.            if(relaciones[i].h==num)
  69.            {
  70.                relacionesChk[i] = 1;
  71.                if(pollos[relaciones[i].m] == -1)
  72.                {
  73.                    pollos[relaciones[i].m] = tp;
  74.                    entid(relaciones[i].m, !tp);
  75.                }
  76.                else if(pollos[relaciones[i].m] == !tp)
  77.                    correcto = false;
  78.            } else if(relaciones[i].m==num) {
  79.                relacionesChk[i] = 1;
  80.                if(pollos[relaciones[i].h] == -1)
  81.                {
  82.                    pollos[relaciones[i].h] = tp;
  83.                    entid(relaciones[i].h, !tp);
  84.                }
  85.                else if(pollos[relaciones[i].h] == !tp)
  86.                    correcto = false;
  87.            }
  88.        }
  89.    return;
  90. }


Título: Re: Retos C/C++
Publicado por: ghastlyX en 20 Agosto 2010, 02:19 am
Parece correcto mirando el código por encima y probando algunos casos. La idea era ver que el problema se puede convertir en un grafo donde los animales son los nodos y las relaciones entre ellos las aristas. Una vez hecho esto, la cuestión era ver si este grafo era bipartido o no (si se pueden partir los nodos en dos grupos tal que cada grupo no tenga aristas entre ellos, que serán los machos y las hembras).

Es fácil de demostrar y ver que si G = (V,E) es un grafo no dirigido, los siguientes enunciados son equivalentes:

1) G es bipartido.
2) G es bicoloreable (2-coloreable).
3) G no contiene ningún ciclo simple de longitud impar.

Como las tres son equivalentes, se puede mirar cualquiera de ellas y la más eficiente de comprobar es la segunda, que mirando tú código supongo que es lo que haces.

Os dejo también la solución que había preparado:
Código
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. typedef vector<int> VI;
  6. typedef vector<VI> VVI;
  7.  
  8. bool bicolor(int u, int c, VVI& G, VI& color) {
  9.    bool res = true;
  10.    for (int i = 0; i < G[u].size(); ++i) {
  11.        int v = G[u][i];
  12.        if (color[v] < 0) {
  13.            color[v] = c;
  14.            res &= bicolor(v, 1 - c, G, color);
  15.        }
  16.        else if (color[v] != c) res = false;
  17.    }
  18.    return res;
  19. }
  20.  
  21. int main() {
  22.    int n, m;
  23.    cin >> n >> m;
  24.    VVI G(n);
  25.    for (int i = 0; i < m; ++i) {
  26.        int a, b;
  27.        cin >> a >> b;
  28.        G[a].push_back(b);
  29.        G[b].push_back(a);
  30.    }
  31.    VI color(n, -1);
  32.    bool res = true;
  33.    for (int i = 0; i < n; ++i) { //Por si hay mas de un componente
  34.        if (color[i] < 0) {
  35.            color[i] = 0;
  36.            res &= bicolor(i, 1, G, color);
  37.        }
  38.    }
  39.    if (res) cout << "Si" << endl;
  40.    else cout << "No" << endl;    
  41. }

PD: Cuidado con las salidas, tu código imprime SI y NO en vez de Si y No. A mí me da igual, pero si eres olímpico como supongo por tu firma, ves con cuidado con estas cosas en los concursos, puesto que el juez automático te daría un WA y estos errores tontos en pleno concurso pueden costar de encontrar, pensando que es problema en el código o el razonamiento.

Edito: Se me olvidaba, dos cosas:
- Para saber si un grafo es bicoloreable basta con ir asignando a cada nodo libre un color cualquiera y a sus vecinos el contrario. Si se encuentra algún vecino con el mismo color es que no es bicoloreable.

- Pon el siguiente reto xDD


Título: Re: Retos C/C++
Publicado por: Og. en 20 Agosto 2010, 03:30 am
jeje, a un amigo le paso que no le contaron los casos por un \n de mas al final del programa xD

Reto #9

Recibes don enteros (X, Y) los cuales representan una caja

y tu quieres partir esa caja en cuadrados exactos. hacer un programa que te diga el mínimo numero de cuadrados exactos dentro de una caja.

Ejemplo1

Entrada
Código:
3 5

Salida
Código:
4
Explicacion
1 caja de 3*3
1 caja de 2*2
2 cajas de 1*1

Ejemplo2

Entrada
Código:
5 6

Salida
Código:
5
Explicacion
2 cajas de 3*3
3 cajas de 2*2


Título: Re: Retos C/C++
Publicado por: ghastlyX en 20 Agosto 2010, 15:35 pm
Supongo que sería así:
Código
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. typedef vector<int> VI;
  6. typedef vector<VI> VVI;
  7.  
  8. const int INF = 1000000000;
  9.  
  10. int dp(int n, int m, VVI& M) {
  11.    if (n < m) return dp(m, n, M);
  12.    if (m == 0) return 0;
  13.    if (M[n][m] == -1) {
  14.        M[n][m] = INF;
  15.        for (int x = 0; x <= m; ++x) {
  16.            M[n][m] = min(M[n][m], 1 + dp(x, m - x, M) + dp(n - x, m, M));
  17.            M[n][m] = min(M[n][m], 1 + dp(n, m - x, M) + dp(n - x, x, M));
  18.        }
  19.    }
  20.    return M[n][m];
  21. }
  22.  
  23. int main() {
  24.    int n, m;
  25.    cin >> n >> m;
  26.    if (n < m) swap(n, m);
  27.    VVI M(n + 1, VI(m + 1, -1));
  28.    cout << dp(n, m, M) << endl;
  29. }
  30.  

A ver si la gente le pierde un poco el miedo a las dinámicas!


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 20 Agosto 2010, 21:08 pm
GhastlyX deja el proximo reto... :xD sin mucho chackra


Título: Re: Retos C/C++
Publicado por: ghastlyX en 21 Agosto 2010, 06:15 am
Reto #10
Una compañía de autobuses sospecha que en una de sus rutas el autobús va demasiado lleno y están estudiando poner otro más para mejorar el servicio. Para ello, han colocado un contador en las puertas que registra en cada parada cuánto varía la cantidad de personas en el bus (este número podrá ser obviamente negativo).

En un cierto momento de la ruta, el conductor activa el contador y se generan los registros y más tarde lo apaga (nótese que esto implica que la suma de las diferencias podrá ser negativa, puesto que podía haber gente dentro del bus). La compañía estudiará después las sumas de subsecuencias consecutivas de la secuencia de registros. Por ejemplo, si la secuencia es -20 -15 30 -15 30, subsecuencias consecutivas son entre otras -15 30, 30 o incluso la propia secuencia completa.

Entrada:
Un número N <= 1000 en una línea. En la siguiente línea, N números indicando registros. Se cumple que los números de los registros serán menores en valor absoluto que 100.

Salida:
Escribe la mayor suma que pueda obtenerse de una subsecuencia consecutiva.

Ejemplos:

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

Salida 1:
Código:
10

Entrada 2:
Código:
5
-20 -15 30 -15 30

Salida 2:
Código:
45

Notas:
- El hecho de que la N pueda ser hasta 1000 implica que una solución trivial de complejidad O(N3) no sirve (es decir, para cada posible inicio y posible final [dos fors anidados], hacer un for más anidado para calcular la suma y quedarse con la mayor). Si alguien no tiene claro si su solución es suficiente rápida (teniendo claro al menos que es correcta), se puede generar 1000 números enteros y ver cómo de rápido es su código. Debería tardar menos de un segundo, si tarda más que eso, el algoritmo no es suficiente bueno (no consiste en optimizar el código).

- Espero una solución de complejidad O(N2) intencionadamente para intentar que el problema sea más sencillo. Este problema se puede solucionar de forma más eficiente, usando una estrategia Divide&Conquer que deja una complejidad de O(NlogN) o incluso una forma ingeniosa para obtener un algoritmo O(N). Si alguien hace algún algoritmo mejor que cuadrático, como los que comento, obviamente el código será correcto.


Título: Re: Retos C/C++
Publicado por: cgvwzq en 21 Agosto 2010, 15:05 pm
Solución trivial O(N³):

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int main(int argc, char **argv) {
  5.  
  6.   int n,*sec,i,j,k;
  7.  
  8.   if (argc != 2) return 1;
  9.  
  10.   n = atoi(argv[1]);
  11.   sec = (int*)calloc(n,sizeof(int));
  12.   for (i=0;i<n;i++) scanf("%d",&sec[i]);
  13.  
  14.   for (i=0;i<n;i++) {
  15.      for (j=i;j<n;j++) {
  16.         sum = 0; for (k=i;k<=j;k++) sum+=sec[k];
  17.         if (sum > max) max = sum;
  18.      }
  19.   }
  20.  
  21.   printf("%d\n",max);
  22.  
  23.   free(sec);
  24.   return 0;
  25.  
  26. }

Solución mejorada, en lugar de sumar cada vez todos los intervalos usamos los datos ya calculados para obtener el nuevo resultado. ¿Es O(N²)?

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int main(int argc, char **argv) {
  5.  
  6.   int n, i, j, **sec, max=0;
  7.  
  8.   if (argc != 2) return 1;
  9.  
  10.   n = atoi(argv[1]);
  11.   if (!(sec = (int**)calloc(n,sizeof(int*)))) return 1;
  12.   for (i=0;i<n;i++) if(!(sec[i] = (int*)calloc(n,sizeof(int)))) return 1;
  13.  
  14.   for (i=0;i<n;i++) scanf("%d",&sec[0][i]);
  15.  
  16.   for (i=1;i<n;i++)
  17.      for (j=i;j<n;j++) {
  18.         sec[i][j] = sec[i-1][j]+sec[0][j-i];
  19.         if (sec[i][j] > max) max = sec[i][j];
  20.      }
  21.  
  22.   printf("%d\n",max);
  23.  
  24.   for (i=0;i<n;i++) free(sec[i]); free(sec);
  25.  
  26.   return 0;
  27.  
  28. }

Una mejora clara sería reservar menos espacio, ya que estoy usando tan solo media matriz...




Título: Re: Retos C/C++
Publicado por: ghastlyX en 21 Agosto 2010, 15:35 pm
No es la solución cuadrática estándar pero también es cuadrática y correcta, por lo tanto perfecta. En tu solución usas programación dinámica por lo que veo para calcular sec(i,j), que representa la suma de i + 1 elementos acabando en j si lo he entendido bien.

La solución cuadrática estándar usa un solo vector que guarda las sumas acumuladas, dejo el código:
Código
  1. #include <vector>
  2. #include <iostream>
  3. using namespace std;
  4. int main() {
  5.    int n;
  6.    cin >> n;
  7.    vector<int> suma(n);
  8.    for (int i = 0; i < n; ++i) {
  9.        cin >> suma[i];
  10.        if (i > 0) suma[i] += suma[i - 1];
  11.    }
  12.    //suma[i] contiene la suma de los i + 1 primeros numeros
  13.    int res = 0;
  14.    for (int i = 0; i < n; ++i) {
  15.        for (int j = 0; j < n; ++j) {
  16.            //Calculamos la suma de cada intervalo aprovechando el vector de sumas calculadas
  17.            //La suma de [i,j] sera suma[j] - suma[i - 1]
  18.            int temp = suma[j];
  19.            if (i > 0) temp -= suma[i - 1];
  20.            res = max(res, temp);
  21.        }
  22.    }
  23.    cout << res << endl;
  24. }
  25.  

La solución lineal que comenté, es decir, O(N), además no requiere espacio en memoria extra. Aunque el código es muy simple, la idea puede costar un poco más de ver, pero si alguien se lo mira con invariantes puede ver que es correcto.
Código
  1. #include <vector>
  2. #include <iostream>
  3. using namespace std;
  4. int main() {
  5.    int n;
  6.    cin >> n;
  7.    int a, res = 0, suma = 0;
  8.    for (int i = 0; i < n; ++i) {
  9.        cin >> a;
  10.        suma += a;
  11.        if (suma < 0) suma = 0;
  12.        res = max(res, suma);
  13.    }
  14.    cout << res << endl;
  15. }

Pon el siguiente reto cuando quieras.


Título: Re: Retos C/C++
Publicado por: cgvwzq en 21 Agosto 2010, 21:38 pm
@ghastlyX, la solución lineal es mu chulaa...XD

El programa generará una matriz "sopa de letras" de N x M, usando una función random. A la vez se le pasará una palabra que buscará en la sopa.

- Las letras de la palabra deberán aparecer en orden consecutivo. Podrán estar en horizontal, vertical, diagonal y en orden inverso.
- La sopa de letras contendrá solo minusculas.
- Una vez se encuentra la palabra la búsqueda termina aunque pueda estar repetida (simplifica el problema)

Al finalizar la búsqueda, se imprimirá la sopa de letras con la palabra en mayúsculas (si es que ha sido encontrada), y un mensaje ("Si" o "No") en función de si ha habido éxito.

Entrada:
Código:
5 5 pi

Salida:
Código:
r v x i l
q l g w f
q c w m n
w q I j j
l q t P q

Si

Entrada:
Código:
5 5 zas

Salida:
Código:
i v t x u
i l f n y
i e f t l
x j w a k
w e d j o

No

Es bastante sencillo, pero nunca me he planteado un problema de estos, y esto es lo primero que se me ha ocurrido...


Título: Re: Retos C/C++
Publicado por: ghastlyX en 22 Agosto 2010, 16:01 pm
Código
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdlib>
  4. using namespace std;
  5.  
  6. int arrf[8] = {-1,-1,-1,0,1,1,1,0};
  7. int arrc[8] = {-1,0,1,1,1,0,-1,-1};
  8.  
  9. int main() {
  10.    int n, m;
  11.    cin >> n >> m;
  12.    vector<vector<char> > S(n, vector<char>(m));
  13.    srand(time(NULL));
  14.    for (int i = 0; i < n; ++i)
  15.        for (int j = 0; j < m; ++j)
  16.            S[i][j] = 'a' + rand()%26;
  17.    string s;
  18.    cin >> s;
  19.    bool busca = true;
  20.    for (int i = 0; i < n and busca; ++i)
  21.        for (int j = 0; j < m and busca; ++j)
  22.            for (int d = 0; d < 8 and busca; ++d) {
  23.                bool ok = true;
  24.                for (int k = 0; k < s.size() and ok; ++k) {
  25.                    int f = i + arrf[d]*k, c = j + arrc[d]*k;
  26.                    if (f < 0 or f >= n or c < 0 or c >= m or S[f][c] != s[k]) ok = false;
  27.                }
  28.                if (ok) {
  29.                    busca = false;
  30.                    for (int k = 0; k < s.size(); ++k) {
  31.                        int f = i + arrf[d]*k, c = j + arrc[d]*k;
  32.                        S[f][c] ^= 32;
  33.                    }
  34.                }
  35.            }
  36.    for (int i = 0; i < n; ++i) {
  37.        for (int j = 0; j < m; ++j) {
  38.            if (j > 0) cout << " ";
  39.            cout << S[i][j];
  40.        }
  41.        cout << endl;
  42.    }
  43.    cout << endl << (busca?"No":"Si") << endl;
  44. }
  45.  

Para el próximo, ¿queréis algo simple o para pensar un poco?


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 22 Agosto 2010, 16:02 pm
:xD no tan simple pero que no rompa craneos.


Título: Re: Retos C/C++
Publicado por: ghastlyX 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).


Título: Re: Retos C/C++
Publicado por: Dznp 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 ;)


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA 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.


Título: Re: Retos C/C++
Publicado por: ghastlyX 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.


Título: Re: Retos C/C++
Publicado por: ghastlyX 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.


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 25 Agosto 2010, 18:15 pm
:xD bueno GhastlyX coloca otro reto, :xD pero que no sea tan fuerte...


Título: Re: Retos C/C++
Publicado por: ghastlyX 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...


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA 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


Título: Re: Retos C/C++
Publicado por: [D4N93R] 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!


Título: Re: Retos C/C++
Publicado por: ghastlyX en 27 Agosto 2010, 02:38 am
No entiendo del todo el código porque no conozco el lenguaje, pero por lo que veo vas de uno en uno dentro del rango y vas haciendo el algoritmo hasta acabar. Hay una manera de hacerlo mucho más rápido.

Como pista, intenta no calcular los pasos para ningún número más de una sola vez ;)


Título: Re: Retos C/C++
Publicado por: [D4N93R] en 27 Agosto 2010, 02:51 am
ghastlyX, dices que hay una manera más rápido de hacerlo, no lo comprendo ya que como se si para un número que aún no he calculado cuál va a ser el resultado?

Es decir, si es un rango [1..10] para que comprobar si ya lo hice con 7 por ejemplo, si se que solo va a salir una sola vez. A menos de que haya entendido mal :D


Título: Re: Retos C/C++
Publicado por: ghastlyX en 27 Agosto 2010, 02:56 am
Si tu intervalo es el [1, 10], por ejemplo cuando mires el 3 pasarás por el 10, que luego volverás a calcular cuando llegues al 10. Lo que comentaba era evitar estas repeticiones de cálculos, puesto que si el intervalo es grande (según el enunciado los números del intervalo pueden llegar a 1000000), la diferencia es notoria.


Título: Re: Retos C/C++
Publicado por: [D4N93R] en 27 Agosto 2010, 03:02 am
Ah ok!! ya lo pillo xD :P vale.. a ver si me sale xD que eso complica un poco las cosas!

Y tienes razón, eso podría mejorar mucho el performance del código.

EDIT: ghastlyX la única forma que se me ocurre de hacerlo como tu dices creo que va a ser muy lenta. Ni idea.. xD


Título: Re: Retos C/C++
Publicado por: ghastlyX en 27 Agosto 2010, 03:20 am
La gracia es que sea más rápido, si no mal vamos. Simplemente guarda lo que hayas calculado una vez. Cada vez que pases por un número, antes de calcularlo mira si ya está hecho.


Título: Re: Retos C/C++
Publicado por: [D4N93R] en 27 Agosto 2010, 03:44 am
Justamente eso había hecho, pero no se, en casos donde esté iterando números muy grandes, tengo que revisar una lista en cada giro. Tengo que hacerle pruebas de rendimiento a ver que tal.
 

Saludos!


Título: Re: Retos C/C++
Publicado por: ghastlyX en 27 Agosto 2010, 03:58 am
Si tienes que consultar una lista es muy lento, la idea es usar un vector, para, por ejemplo, el primer millón de números. Obviamente se pasará de ese límite calculando ciertos números, para esos simplemente si ocurre repetiré los cálculos, puesto que no tenemos memoria infinita. Así al menos el intervalo completo [1, 1000000] lo hace de forma instantánea el siguiente programa (aunque repita cálculos si sale del rango):
Código
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. ll f(ll n, vector<ll>& v) {
  8.    if (n == 1) return 1;
  9.    if (n >= v.size()) return 1 + ((n%2 == 1)?f(3*n + 1, v):f(n/2, v));
  10.    if (v[n] == -1) v[n] = 1 + ((n%2 == 1)?f(3*n + 1, v):f(n/2, v));
  11.    return v[n];
  12. }
  13.  
  14. int main() {
  15.    vector<ll> v(1000000, -1);
  16.    ll a, b;
  17.    while (cin >> a >> b) {
  18.        ll res = 0;
  19.        for (ll i = min(a,b); i <= max(a,b); ++i) res = max(res, f(i, v));
  20.        cout << a << " " << b << " " << res << endl;
  21.    }
  22. }

De hecho esto sería una manera de resolver el problema usando memoization.

Para poder guardar todos los valores, ya que un vector no se puede usar (demasiada memoria) y una lista como tú decías es demasiado lenta (hay que recorrerla entera en el peor caso, coste lineal), la mejor manera que se me ocurre es usar un árbol binario balanceado que permita consultar si está calculado (y su valor) en tiempo logarítmico. Estos están implementados en los contenedores map de la STL de C++. En este problema en concreto no sé qué sería más rápido, si guardar todo con maps aumentando el coste de cada consulta o bien hacer cada consulta instántanea consultando un vector a costa de repetir los cálculos de números fuera del rango del vector.


Título: Re: Retos C/C++
Publicado por: [D4N93R] en 27 Agosto 2010, 04:14 am
Si exacto, ese es el problema, yo pensé usar un binarytree pero no sabes la flojera que me dió. :/

Hice las dos pruebas, con vector y con list. Obviamente Vector es mucho más rápido en grandes intervalos. En pequeños no se nota la diferencia entre ambos.

Un saludo!


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 27 Agosto 2010, 04:28 am
:xD GhastlyX publicaste la respuesta... pon el proximo reto.


Título: Re: Retos C/C++
Publicado por: ghastlyX en 27 Agosto 2010, 04:50 am
Reto #14
Como aún no he mirado los de este año, os dejo uno de la IOI del año pasado, a mi opinión, el más fácil de todos y con diferencia. Es bastante asequible.
http://www.ioi2009.org/GetResource?id=1271


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 1 Septiembre 2010, 03:21 am
:xD 5 dias y sin respuestas... alguien se propone poner algun reto?


Título: Re: Retos C/C++
Publicado por: OwNet en 1 Septiembre 2010, 21:37 pm
mi solucion va quedando asi algun pequeno error que lo corrijo esta noche o alguien de ustedes corrijalo es que estoy de salida :)
Código:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <list>
#include <climits>

using namespace std;
struct participantes
{
    int puntos;
    int resueltas;
    int id;
}conts[2001];
bool operator<(const struct participantes &a, const struct participantes &b)
{
    if (a.puntos!=b.puntos)
        return a.puntos<b.puntos;
    else if (a.resueltas!=b.resueltas)
        return a.resueltas<b.resueltas;
    else
        return a.id<b.id;

}
int main()
{
    ios_base::sync_with_stdio(0);
    int x, y, N, T, P, val;
    while (cin>>N>>T>>P)
    {
        int valor[T];
        for (x=0; x<N; x++)
        {
            conts[x].id=x;
            conts[x].puntos=0;
            for (y=0; y<T; y++)
            {
                cin>>val;
                if (val==1)
                {
                    conts[x].resueltas++;

                }
                else
                    valor[y]++;
            }
        }

        for (x=0; x<N; x++)
        {
            for (y=0; y<T; y++)
            {
                conts[x].puntos+=valor[y];
            }
        }

        cout<<conts[P].puntos<<" ";
        sort(conts, conts+N);
        for (x=0; x<N; x++)
        {
            if (P==conts[x].id)
            {
                cout<<x+1<<endl;
                break;
            }
        }
    }


    return 0;
}


Título: Re: Retos C/C++
Publicado por: OwNet en 2 Septiembre 2010, 07:13 am
Bueno ya lo tengo resuelto les dejo el codigo
Código:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <list>
#include <climits>

using namespace std;
struct participantes
{
    int puntos;
    int resueltas;
    int id;
}conts[2001];
bool operator<(const struct participantes &a, const struct participantes &b)
{
    if (a.puntos!=b.puntos)
        return a.puntos<b.puntos;
    else if (a.resueltas!=b.resueltas)
        return a.resueltas<b.resueltas;
    else
        return a.id<b.id;

}
int main()
{
    ios_base::sync_with_stdio(0);
    int x, y, N, T, P, val;
    while (cin>>N>>T>>P)
    {
        int valor[T];
        int mat[N][T];
        for(x=0; x<T; x++)
        valor[x]=0;
        for (x=0; x<N; x++)
        {
            conts[x].id=x;
            conts[x].puntos=0;
            for (y=0; y<T; y++)
            {
                cin>>mat[x][y];
                if (mat[x][y]==1)
                conts[x].resueltas++;
                else
                    valor[y]++;
            }
        }

        for (x=0; x<N; x++)
        {
            for (y=0; y<T; y++)
            {
                if(mat[x][y]==1)
                conts[x].puntos+=valor[y];
            }
        }

        cout<<conts[P-1].puntos<<" ";
        sort(conts, conts+N);
        //reverse(conts, conts+N);

        for (x=0; x<N; x++)
        {
            if ((P-1)==conts[x].id)
            {
                cout<<x+1<<endl;
                break;
            }
        }
    }


    return 0;
}


Reto #15

Dado un conjunto de mujeres en las cuales en cada una de ellas se representa su belleza, elegancia y educacion. Si dentro de este mismo conjunto una de ellas encuentra que alguien es mas bella mas elegante y mas culta que ella. Ella optara por suicidarse .

Entrada

El primer dato de entrada sera el numero de mujeres que se analizaran las siguientes n lineas seran descritas cada una por los tres atributos antes mencionados
belleza elegancia y educacion

Salida

La salida sera el numero de suicidios que ocurriran tomando en cuenta los datos anteriores

por ejemplo

Entrada
Código:
5
4 4 3
2 3 2
23 3 3
2 3 3
4 4 4

Salida

Código:
2




Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 2 Septiembre 2010, 19:25 pm
Aqui esta el codigo... voy a comer, traigo el reto en aproximadamente 1 hora.
Código
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. struct locas
  6. {
  7.    int b,c,d,e;
  8. };
  9.  
  10. int main()
  11. {
  12. int a,i=0,j=0,t=0,k;
  13. cin>>a;
  14. locas b[a];
  15. for(i;i<a;i++){cin>>b[i].b>>b[i].e>>b[i].c; b[i].d=0;}
  16.  
  17. for(i=0;i<a;i++)
  18. {
  19. for(j=0;j<a;j++)
  20. {
  21. if(b[i].b>b[j].b && b[i].e>b[j].e && b[i].c>b[j].c)
  22. {
  23.    if(b[j].d==1)continue;
  24.    else
  25.    {
  26.                                    t++;
  27.                                    b[j].d=1;
  28.                                    break;
  29.    }
  30.    }
  31.                         }
  32. }
  33. cout<<t<<endl;
  34. }
  35.  


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 3 Septiembre 2010, 00:11 am
Reto #16: Un bloque de masa M, inicialmente en reposo, se jala hacia la derecha a lo largo de una superficie horizontal mediante una fuerza horizontal constante F. Este se mueve una distancia(metros) D sobre una superficie con un coeficiente de friccion N. El resultado debe de ser la velocidad final del bloque exactamente al recorrer esa distancia.

Código:
Entradas:

Masa = 6.0
Fuerza = 12
Distancia = 3.0
Friccion = 0.15

El resultado por pantalla sera:

Velocidad Final del Bloque 1.8 m/s.


Título: Re: Retos C/C++
Publicado por: carlitos_jajajajaja en 9 Septiembre 2010, 07:20 am
Resuelto...


Código
  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  4.  
  5. inline void limpiar()
  6. {
  7. while(getchar() != '\n');
  8. }
  9.  
  10. int main()
  11. {
  12. //aceleracion causada por la gravedad
  13. const float g = 9.81;
  14. //Datos
  15. float M,F,D,N;
  16. //Datos intermedios:
  17. //fuerza causada por friccion, Fuerza neta sobre la masa, aceleracion
  18. float Ff, Fn, a;
  19. //Respuesta:
  20. float v;
  21.  
  22. cout << "Introduzca la masa" << endl;
  23. cin >> M;
  24. limpiar();
  25. cout << "Introduzca la fuerza" << endl;
  26. cin >> F;
  27. limpiar();
  28. cout << "Introduzca la distancia" << endl;
  29. cin >> D;
  30. limpiar();
  31. cout << "Introduzca el coeficiente de friccion" << endl;
  32. cin >> N;
  33. limpiar();
  34.  
  35. Ff = N*M*g;
  36. Fn = F - Ff;
  37. if(Fn < 0)
  38. {
  39. //No hay movimiento, la friccion es mas grande que la fuerza
  40. cout << "Velocidad final del bloque 0 m/s." << endl;
  41. exit(0);
  42. }
  43. a = Fn/M;
  44. v = sqrt(2.0*a*D);
  45. cout.precision(1);
  46. cout << "Velocidad final del bloque ";
  47. cout << fixed << v;
  48. cout << " m/s." << endl;
  49. cin.get();
  50. }
  51.  


Reto #17

Generar aleatoriamente 2 numeros enteros de 30 cifras y mostrar el resultado exacto de su suma


Título: Re: Retos C/C++
Publicado por: Komodo en 9 Septiembre 2010, 09:15 am
Un entero no puede tener tantas cifras....


Título: Re: Retos C/C++
Publicado por: Novlucker en 9 Septiembre 2010, 14:45 pm
Creo que ese es el reto :rolleyes:

Saludos


Título: Re: Retos C/C++
Publicado por: ace332 en 11 Septiembre 2010, 13:59 pm
Creo que ya la tengo!  ;D

Código:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef char ent30[31];

void aleat30(ent30 z);
void sumarn30(ent30 a,ent30 b,ent30 suma,int *acarreo);

int main(void)
{
  ent30 a,b,suma;
  int acarreo;

  srand(time(0));
  aleat30(a);
  aleat30(b);

  sumarn30(a,b,suma,&acarreo);

  printf("   a = %31s\n   b = %31s\nsuma = %d%30s\n",a,b,acarreo,suma);
  return 0;
}

void aleat30(ent30 z)
{
  int i;
  for(i=0;i<30;i++)
  {
    z[i]='0'+rand()%10;
  }
  z[30]='\0';
}

#define CharADig(c) ((int)((c)-'0'))
#define DigAChar(d) ((char)(d)+'0')

void sumarn30(ent30 a,ent30 b,ent30 suma,int *ua)
{
  int i,ap=0;
  suma[30]='\0';
  for(i=29;i>=0;i--)
  {
    const int sumadig=CharADig(a[i])+CharADig(b[i])+ap;
    suma[i]=DigAChar(sumadig%10);
    ap=sumadig/10;
  }
  *ua=ap;
}

Reto #18 (Otro que tiene que ver con números grandes):

Calcular el factorial de un número n, 0<=n<=100. Sin usar tipos de datos de punto flotante (float, double, etc).
Y para los que puedan pensar que es una tarea, pues no, no lo es. :P  :¬¬


Título: Re: Retos C/C++
Publicado por: Og. en 13 Septiembre 2010, 07:30 am
Regrese XD
Código
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int fact(int val)
  6. {
  7.   if(val==0)
  8.      return 1;
  9.   else
  10.      return val*fact(val-1);
  11. }
  12.  
  13. int main(void)
  14. {
  15.    int N;
  16.    cin >> N;
  17.    cout << fact(N) << endl;
  18.    return 0;
  19. }
  20.  

Reto #19

Escalando la piramide

supon que hay una piramide, y quieres saber cual es la cantidad maxima de piedras que puedes recolectar subiendo directamente a la sima.

Entrada

un numero N que dice el numero de pisos en la piramide.
N lineas con el numero de piedras que hay en cada punto de la piramide.
el ultimo piso de la piramide siempre sera de 1 solo bloque, el penultimo de 2 , el ante penultimo de 3 y asi hasta llegar al piso

Salida

Un entero que indique el numero maximo de piedras que se puedan juntar.

Ejemplo
Código:
3
1
2 1
1 0 1

esos datos se deben interpretar asi:

(http://i.elhacker.net/i?i=TrfYV238RD0GdUsaYTgSY2Vo) (http://i.elhacker.net/d?i=TrfYV238RD0GdUsaYTgSY2Vo)

Salida

Código:
4


Título: Re: Retos C/C++
Publicado por: ace332 en 13 Septiembre 2010, 19:32 pm
disculpame compañero pero me parece que no leiste bien el enunciado del problema :o:

Citar
Calcular el factorial de un número n, 0<=n<=100

El programa que pusiste sólo calcula bien hasta el factorial de 12.

Saludos.

PD: Si gustan pongo la solución y pasamos al reto planteado por Og  :)


Título: Re: Retos C/C++
Publicado por: ghastlyX en 13 Septiembre 2010, 20:31 pm
He reaprovechado un código que hice hace un tiempo que multiplica usando Karatsuba, por lo que el código es largo y feo. Si alguien lo prefiere dejo una versión nueva y más legible sin usar Karatsuba. De hecho, Karatsuba sólo se usa si los dos números a multiplicar son suficiente grandes (unos 100 dígitos) en mi código, pero lo dejo por si a alguien le interesa.
Código
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. typedef vector<long long> VL;
  7.  
  8. VL mult(VL& a, int i1, int f1, VL& b, int i2, int f2) {
  9.    if (i1 > f1 or i2 > f2) return VL(1,0);
  10.    if (f1 >= a.size()) return mult(a, i1, a.size() - 1, b, i2, f2);
  11.    if (f2 >= b.size()) return mult(a, i1, f1, b, i2, b.size() - 1);
  12.    if (i1 >= a.size() or i2 >= b.size()) return VL(1,0);
  13.    int n = f1 - i1 + 1, m = f2 - i2 + 1;
  14.    VL c(max(n,m)*2 + 1, 0);
  15.    for (int i = i1; i <= f1; ++i) {
  16.        for (int j = i2; j <= f2; ++j) {
  17.            c[i - i1 + j - i2] += (a[i]*b[j]);
  18.            c[i - i1 + j - i2 + 1] += (c[i - i1 + j - i2]/1000000000);
  19.            c[i - i1 + j - i2] %= 1000000000;
  20.        }
  21.    }
  22.    int pos = c.size() - 1;
  23.    while (pos > 0 and c[pos--] == 0) c.pop_back();
  24.    return c;
  25. }
  26.  
  27. VL suma(VL& a, int i1, int f1, VL& b, int i2, int f2) {
  28.    if (i1 > f1 or i1 >= a.size()) {
  29.        VL cero(1,0);
  30.        return suma(cero, 0, 0, b, i2, f2);
  31.    }
  32.    if (i2 > f2 or i2 >= b.size()) {
  33.        VL cero(1, 0);
  34.        return suma(a, i1, f1, cero, 0, 0);
  35.    }
  36.    if (f1 >= a.size()) return suma(a, i1, a.size() - 1, b, i2, f2);
  37.    if (f2 >= b.size()) return suma(a, i1, f1, b, i2, b.size() - 1);
  38.    int n = f1 - i1 + 1, m = f2 - i2 + 1;
  39.    VL c(n + m + 2, 0);
  40.    int i = i1, j = i2, k = 0;
  41.    while (i <= f1 and j <= f2) {
  42.        c[k] += (a[i] + b[j]);
  43.        c[k + 1] += (c[k]/1000000000);
  44.        c[k] %= 1000000000;
  45.        ++i; ++j; ++k;
  46.    }
  47.    while (i <= f1) {
  48.        c[k] += a[i];
  49.        c[k + 1] += (c[k]/1000000000);
  50.        c[k] %= 1000000000;
  51.        ++i; ++k;
  52.    }
  53.    while (j <= f2) {
  54.        c[k] += b[j];
  55.        c[k + 1] += (c[k]/1000000000);
  56.        c[k] %= 1000000000;
  57.        ++j; ++k;
  58.    }
  59.    int pos = c.size() - 1;
  60.    while (pos > 0 and c[pos--] == 0) c.pop_back();
  61.    return c;
  62. }
  63.  
  64. VL resta(VL& a, int i1, int f1, VL& b, int i2, int f2) {
  65.    VL c;
  66.    c = a;
  67.    for (int i = i2; i <= f2; ++i) {
  68.        c[i] -= b[i];
  69.        while (c[i] < 0) {
  70.            c[i] += 1000000000;
  71.            c[i + 1]--;
  72.        }
  73.    }
  74.    int pos = c.size() - 1;
  75.    while (pos > 0 and c[pos--] == 0) c.pop_back();
  76.    return c;
  77. }
  78.  
  79. VL karatsuba(VL& a, int i1, int f1, VL& b, int i2, int f2) {
  80.    if (i1 > f1 or i2 > f2) return VL(1,0);
  81.    if (f1 >= a.size()) return karatsuba(a, i1, a.size() - 1, b, i2, f2);
  82.    if (f2 >= b.size()) return karatsuba(a, i1, f1, b, i2, b.size() - 1);
  83.    if (i1 >= a.size() or i2 >= b.size()) return VL(1,0);
  84.    int p = f1 - i1 + 1, m = f2 - i2 + 1;
  85.    if (min(p, m) <= 10) return mult(a, i1, f1, b, i2, f2);
  86.    int n = max(p, m);
  87.    VL c1, c2, c3, x, y;
  88.    int mit = n/2;
  89.    c1 = karatsuba(a, i1 + mit, f1, b, i2 + mit, f2);
  90.    c3 = karatsuba(a, i1, i1 + mit - 1, b, i2, i2 + mit - 1);
  91.    x = suma(a, i1, i1 + mit - 1, a, i1 + mit, f1);
  92.    y = suma(b, i2, i2 + mit - 1, b, i2 + mit, f2);
  93.    c2 = karatsuba(x, 0, x.size() - 1, y, 0, y.size() - 1);
  94.    c2 = resta(c2, 0, c2.size() - 1, c1, 0, c1.size() - 1);
  95.    c2 = resta(c2, 0, c2.size() - 1, c3, 0, c3.size() - 1);
  96.    VL res(2*n + 3, 0);
  97.    for (int i = 0; i < c1.size(); ++i) {
  98.        res[i + 2*mit] += c1[i];
  99.        res[i + 2*mit + 1] += (res[i + 2*mit]/1000000000);
  100.        res[i + 2*mit] %= 1000000000;
  101.    }
  102.    for (int i = 0; i < c2.size(); ++i) {
  103.        res[i + mit] += c2[i];
  104.        res[i + mit + 1] += (res[i + mit]/1000000000);
  105.        res[i + mit] %= 1000000000;
  106.    }
  107.    for (int i = 0; i < c3.size(); ++i) {
  108.        res[i] += c3[i];
  109.        res[i + 1] += (res[i]/1000000000);
  110.        res[i] %= 1000000000;
  111.    }
  112.    int pos = res.size() - 1;
  113.    while (pos > 0 and res[pos--] == 0) res.pop_back();
  114.    return res;
  115. }
  116.  
  117. string str(long long x) {
  118.    string s;
  119.    do {
  120.        s += char(x%10 + '0');
  121.        x /= 10;
  122.    } while(x > 0);
  123.    reverse(s.begin(), s.end());
  124.    return s;
  125. }
  126.  
  127. int main() {
  128.    int n;
  129.    cin >> n;
  130.    VL res(1,1);
  131.    for (int i = 1; i <= n; ++i) {
  132.        VL a(1,i);
  133.        VL c;
  134.        c = karatsuba(a, 0, a.size() - 1, res, 0, res.size() - 1);
  135.        res = c;
  136.    }
  137.    cout << res[res.size() - 1];
  138.    for (int i = res.size() - 2; i >= 0; --i) {
  139.        string s = str(res[i]);
  140.        cout << string(9 - s.size(), '0') << s;
  141.    }
  142.    cout << endl;
  143. }
  144.  

Ahora pasemos al reto de Og. y a ver si alguien se anima, que es una dinámica sencillita.


Título: Re: Retos C/C++
Publicado por: ace332 en 14 Septiembre 2010, 03:09 am
Solved  ::)

Código:

#include <stdio.h>
#include <string.h>

#define MAX_TAM_BASE 1000

#define max(a,b) (((a)>(b))?(a):(b))

int main(void)
{
  int N,i,j,maxmax=0,maximos[MAX_TAM_BASE];
 
  scanf("%d",&N);
  memset(maximos,0,sizeof(int)*MAX_TAM_BASE);
  for(i=0;i<N;i++)
  {
    int temp1=0,temp2,piedras;
    for(j=0;j<=i;j++)
    {
      temp2=maximos[j];
      scanf("%d",&piedras);
      maximos[j]=piedras+max(temp1,maximos[j]);
      temp1=temp2;
    }
  }

  for(j=0;j<N;j++)
  {
    if(maximos[j]>maxmax)
      maxmax=maximos[j];
  }
  printf("%d\n",maxmax);
  return 0;
}

Reto #20: Dado un año N (N>=1600), determinar qué día será (o fue) el primero de enero de ese año.

Por ejemplo para una entrada N = 2009, la respuesta seria 'Jueves'.


Título: Re: Retos C/C++
Publicado por: ace332 en 19 Septiembre 2010, 20:19 pm
Bueno parece que nadie se animo a resolver el reto por lo que aqui va la solución:

Código:
#include <stdio.h>
#include <stdlib.h>

#define anyo_ref  2010
#define diainicio Viernes

enum Dia{ Domingo, Lunes, Martes, Miercoles, Jueves, Viernes, Sabado };
const char *strdia[]={"Domingo", "Lunes", "Martes", "Miercoles", "Jueves", "Viernes", "Sabado" };

int esbisiesto(int anyo);

int main(void)
{
  int a, anyo, ai=anyo_ref, af, ndias=0, dia1enero;

  scanf("%d",&anyo);

  af = anyo-1;
  if(anyo < anyo_ref)
  {
    ai = anyo;
    af = anyo_ref-1;
  }
  for(a = ai; a <= af; a++)
    ndias += esbisiesto(a)?2:1;

  dia1enero = (diainicio + ((anyo >= anyo_ref)?1:-1) * ndias) %7;
  if(dia1enero < 0)
    dia1enero += 7;

  printf("%s\n",strdia[dia1enero]);
  return 0;
}

int esbisiesto(int anyo)
{
  return (anyo%4) == 0 && ((anyo%100) != 0 || (anyo%400) == 0);
}


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 27 Septiembre 2010, 00:09 am
Publica el proximo reto.


Título: Re: Retos C/C++
Publicado por: ace332 en 27 Septiembre 2010, 02:37 am
Bueno.. aqui va uno un tanto sencillo.
Citar
Un número perfecto es un número natural que es igual a la suma de sus divisores propios positivos, sin incluirse él mismo. Dicho de otra forma, un número perfecto es aquel que es amigo de sí mismo.

Así, 6 es un número perfecto, porque sus divisores propios son 1, 2 y 3; y 6 = 1 + 2 + 3. Los siguientes números perfectos son 28, 496 y 8128.
fuente: Wikipedia.

Reto #21: Hacer un programa que imprima en pantalla todos los números perfectos hasta un número N dado como entrada.


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 27 Septiembre 2010, 05:23 am
Código
  1. #include <iostream>
  2. int main()
  3. {
  4. int a,b;
  5. std::cin>>a;
  6. for(int i=1;i<=a;i++)
  7. {
  8. b=0;
  9. for(int j=1;j<i;j++)if(i%j==0)b+=j;
  10. if(b==i)std::cout<<b<<std::endl;
  11. }
  12. return 0;
  13. }
  14.  

PsData: En unas horas traigo reto... tengo un sueño que no me deja siquiera pensar.


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 27 Septiembre 2010, 21:05 pm
Reto #22: Dada dos fechas, verificar cuantos dias han transcurrido... se debe de tomar en cuenta los años bisiestos.


Título: Re: Retos C/C++
Publicado por: Wazzp en 29 Septiembre 2010, 00:06 am
Disculpen mi impaciencia pero.. tengo un codigo,que a mi parecer esta bien,pero tiene un error ya que se cuelga y no hace nada.. alguien podria revisarlo? Si lo corrijo creo que solucionaria el reto # 22.. Respondan asi lo posteo,sino,borren este post y busco alguna otra forma de conseguir mi respuesta..

Gracias y Saludos  :)


Título: Re: Retos C/C++
Publicado por: [D4N93R] en 29 Septiembre 2010, 03:24 am
Postealo a ver, lo vamos revisando y arreglando.

Saludos.


Título: Re: Retos C/C++
Publicado por: Wazzp en 29 Septiembre 2010, 21:05 pm
El codigo que tengo es..

Código
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.    void datos(int &d,int &mcont,int &a,int &D,int &Mcont,int &A,int &t)
  5.    {
  6.    cout<<"Ingresa una fecha(DD/MM/AAAA. Debe ser la mas antigua!)"<<endl;
  7.    cin>>d>>mcont>>a;
  8.    cout<<"Ingresaste.."<<d<<"/"<<mcont<<"/"<<a<<endl;
  9.  
  10.    cout<<"Ingresa una segunda fecha. Debe ser la mas reciente."<<endl;
  11.    cin>>D>>Mcont>>A;
  12.    cout<<"Ingresaste.."<<D<<"/"<<Mcont<<"/"<<A<<endl;
  13.    cout<< "Comparar..? 1=si 2=no-quiero cambiar las fechas 3=salir"
  14.   <<endl;
  15.   cin>>t;
  16.    }
  17.  
  18.    void ABis(int a,int A,int m,int M)
  19.    {
  20.        if ( ( ( a % 4 == 0 ) && (a % 100 != 0 ) ) || ( (a % 400 ==0)))
  21.  
  22.            m=1;
  23.             else
  24.                m=2;
  25.  
  26.       if ( ( ( A % 4 == 0 ) &&( A % 100 != 0 ) ) || ( (A % 400 ==0) ) )
  27.  
  28.           M=1;
  29.            else
  30.                M=2;
  31.    }
  32.  
  33.    void meses(int m,int mb,int Mb,int M,int mcont,int Mcont)
  34.    {
  35.        if ((mcont==1)||(mcont==3)||(mcont==5)||(mcont==7)||(mcont==8)||(mcont==10)||(mcont==12))
  36.        {
  37.             mb=31;
  38.        }
  39.  
  40.            else if ((mcont==4)||(mcont==6)||(mcont==9)||(mcont==11))
  41.            {
  42.                mb=30;
  43.  
  44.        };
  45.    if ((Mcont==1)||(Mcont==3)||(Mcont==5)||(Mcont==7)||(Mcont==8)||(Mcont==10)||(Mcont==12))
  46.        {
  47.            Mb=31;
  48.        }
  49.        else if ((Mcont==4)||(Mcont==6)||(Mcont==9)||(Mcont==11))
  50.        {
  51.            Mb=30;
  52.        };
  53.    if ((m==1)&&(mcont==2))
  54.    {
  55.        mb=29;
  56.        }
  57.        else if((m==2)&&(mcont==2))
  58.        {
  59.            mb=28;
  60.        };
  61.  
  62.    }
  63.  
  64.    void calculo(int d,int m,int a,int X,int mcont,int mb,int Mb,int mb1,int A,int M,int Mcont,int R,int Y)
  65.    //Calcularia la cantidad de dias hasta el fin del año
  66.    {
  67.       {
  68.         while (mcont<=12)
  69.         ABis(a,A,m,M);
  70.       meses(m,mb,Mb,M,mcont,Mcont);
  71.     X+=mb;
  72.     mcont++;
  73.     };
  74.     {
  75.          while (Mcont>=1)
  76.          ABis(a,A,m,M);
  77.       meses(m,mb,Mb,M,mcont,Mcont);
  78.     Y+=Mb;
  79.     Mcont--;
  80.     };
  81.     R=(X-Y);
  82.     cout<<"La respuesta seria: "<<R<<" Dias."<<endl;
  83.     }
  84.  
  85.   int main()
  86. {
  87.   int d=0,a=0,D=0,A=0,t=0;
  88.   int mb=0;int Mb=0;int mcont=0;
  89.   int X=0;int Mcont=0;
  90.   int Y=0;int mb1=0;
  91.   int R=0;int m=0;int M=0;
  92.   datos(d,mcont,a,D,Mcont,A,t);
  93.  
  94.  
  95.       switch(t)
  96.       {
  97.            case 1:
  98.            calculo(d,m,a,X,mcont,mb,Mb,mb1,A,M,Mcont,R,Y);
  99.            return 0;
  100.            break;
  101.  
  102.            case 2:
  103.            cout<<"Revisa las fechas.."<<endl;
  104.            calculo(d,m,a,X,mcont,mb,Mb,mb1,A,M,Mcont,R,Y);
  105.            return 0;
  106.            break;
  107.  
  108.            default:
  109.            return 0;
  110.            break;
  111.       };
  112.    }
  113.  

No entiendo porque no funciona!! El codigo compila sin warnings ni errores..


Título: Re: Retos C/C++
Publicado por: [L]ord [R]NA en 1 Octubre 2010, 04:16 am
Termina el plazo de los 3 dias sin respuesta definitiva... Quien pondra el nuevo reto?


Título: Re: Retos C/C++
Publicado por: PiroskY en 2 Octubre 2010, 21:14 pm
Código
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.    short d1,m1,a1,d2,m2,a2,acu=0;
  7.    cout << "Ingrese la primer fecha con el siguiente formato DD-MM-AAAA" << endl;
  8.    cout << "Ingrese el dia" << endl;
  9.    cin >> d1;
  10.    cout << "Ingrese el mes" << endl;
  11.    cin >> m1;
  12.    cout << "Ingrese el año" << endl;
  13.    cin >> a1;
  14.    cout << "Ingrese la segunda fecha con el siguiente formato DD-MM-AAAA" << endl;
  15.    cout << "Ingrese el dia" << endl;
  16.    cin >> d2;
  17.    cout << "Ingrese el mes" << endl;
  18.    cin >> m2;
  19.    cout << "Ingrese el año" << endl;
  20.    cin >> a2;
  21.    if (a2-a1 >=1) //dentro de este if voy a hacer la cuenta para los casos en que las dos fechas no pertenezcan al mismo año
  22.    {
  23.        switch (m1)
  24.        {
  25.            case 1:
  26.            acu+=31-d1+334; //Le sumo la cantidad de dias que faltan para que termine el año
  27.            break;
  28.            case 2:
  29.            acu+=28-d1+306;
  30.            break;
  31.            case 3:
  32.            acu+=31-d1+275;
  33.            break;
  34.            case 4:
  35.            acu+=30-d1+245;
  36.            break;
  37.            case 5:
  38.            acu+=31-d1+214;
  39.            break;
  40.            case 6:
  41.            acu+=30-d1+184;
  42.            break;
  43.            case 7:
  44.            acu+=31-d1+153;
  45.            break;
  46.            case 8:
  47.            acu+=31-d1+122;
  48.            break;
  49.            case 9:
  50.            acu+=30-d1+92;
  51.            break;
  52.            case 10:
  53.            acu+=31-d1+61;
  54.            break;
  55.            case 11:
  56.            acu+=30-d1+31;
  57.            break;
  58.            case 12:
  59.            acu+=31-d1;
  60.            break;
  61.        }
  62.        if (a1%4 == 0 && m1 <= 2) //por si el año era biciesto
  63.        {
  64.            acu++;
  65.        }
  66.        for (int i=a1+1;i<a2;i++) //voy sumando todos los dias de año, hasta un año antes del de la segunda fecha
  67.        {
  68.            if (i%4 == 0)
  69.            {
  70.                acu+=366;
  71.            }
  72.            else
  73.            {
  74.                acu+=365;
  75.            }
  76.        }
  77.        switch (m2) //le sumo los dias transcurridos del ultimo año
  78.        {
  79.            case 1:
  80.            acu+=d2;
  81.            break;
  82.            case 2:
  83.            acu+=31+d2;
  84.            break;
  85.            case 3:
  86.            acu+=59+d2;
  87.            break;
  88.            case 4:
  89.            acu+=90+d2;
  90.            break;
  91.            case 5:
  92.            acu+=120+d2;
  93.            break;
  94.            case 6:
  95.            acu+=151+d2;
  96.            break;
  97.            case 7:
  98.            acu+=181+d2;
  99.            break;
  100.            case 8:
  101.            acu+=212+d2;
  102.            break;
  103.            case 9:
  104.            acu+=243+d2;
  105.            break;
  106.            case 10:
  107.            acu+=273+d2;
  108.            break;
  109.            case 11:
  110.            acu+=304+d2;
  111.            break;
  112.            case 12:
  113.            acu+=334+d2;
  114.            break;
  115.        }
  116.         if (a2%4 == 0 && (m2 <= 2 || (m2==2 && d2 == 29))) //por si el ultimo año era biciesto y la fecha era mayor o igual al 29 de febrero
  117.        {
  118.            acu++;
  119.        }
  120.    }
  121.    if (a1==a2)
  122.    {
  123.        switch (m1) //Calculo cuantos dias pasaron desde que empezo el año hasta la primer fecha
  124.        {
  125.            case 1:
  126.            acu=d1;
  127.            break;
  128.            case 2:
  129.            acu=31+d1;
  130.            break;
  131.            case 3:
  132.            acu=59+d1;
  133.            break;
  134.            case 4:
  135.            acu=90+d1;
  136.            break;
  137.            case 5:
  138.            acu=120+d1;
  139.            break;
  140.            case 6:
  141.            acu=151+d1;
  142.            break;
  143.            case 7:
  144.            acu=181+d1;
  145.            break;
  146.            case 8:
  147.            acu=212+d1;
  148.            break;
  149.            case 9:
  150.            acu=243+d1;
  151.            break;
  152.            case 10:
  153.            acu=273+d1;
  154.            break;
  155.            case 11:
  156.            acu=304+d1;
  157.            break;
  158.            case 12:
  159.            acu=334+d1;
  160.            break;
  161.        }
  162.        switch (m2) //Calculo cuantos dias pasaron desde que empezo el año hasta la segunda fecha, y a ese numero le resto el numero obtenido para la primer fecha
  163.        {
  164.            case 1:
  165.            acu=d2-acu;
  166.            break;
  167.            case 2:
  168.            acu=31+d2-acu;
  169.            break;
  170.            case 3:
  171.            acu=59+d2-acu;
  172.            break;
  173.            case 4:
  174.            acu=90+d2-acu;
  175.            break;
  176.            case 5:
  177.            acu=120+d2-acu;
  178.            break;
  179.            case 6:
  180.            acu=151+d2-acu;
  181.            break;
  182.            case 7:
  183.            acu=181+d2-acu;
  184.            break;
  185.            case 8:
  186.            acu=212+d2-acu;
  187.            break;
  188.            case 9:
  189.            acu=243+d2-acu;
  190.            break;
  191.            case 10:
  192.            acu=273+d2-acu;
  193.            break;
  194.            case 11:
  195.            acu=304+d2-acu;
  196.            break;
  197.            case 12:
  198.            acu=334+d2-acu;
  199.            break;
  200.        }
  201.        if (a2%4 == 0 && (m1 <= 2 || (m1==2 && d1 == 29))) //por si el año es biciesto y la fecha es mayor o igual al 29 de febrero
  202.        {
  203.            acu++;
  204.        }
  205.    }
  206.    cout <<"entre el "<<d1<<"/"<<m1<<"/"<<a1<<" y el "<<d2<<"/"<<m2<<"/"<<a2<<" pasaron "<<acu<<" dias."<< endl;
  207. return 0;
  208. }

no se con que dificultad vienen poniendo los retos, pero ya que nadie tira, pongo este, y si es facil bueno, el que lo haga que ponga otro mas complicado

Reto #23: Ingresar dos cadenas e informar si la segunda está contenida o no dentro de la primera.


Título: Re: Retos C/C++
Publicado por: Komodo en 3 Octubre 2010, 16:37 pm
Código
  1. #include <iostream>
  2. #include <cstring>
  3.  
  4. using namespace std;
  5. int main ()
  6. {
  7.  char str[99];
  8.  char str2[99];
  9.  cout << "Introduce la primera cadena: ";
  10.  fgets(str, 99, stdin);
  11.  if (str[strlen(str)-1] == '\n'){
  12. str[strlen(str)-1] = '\0';
  13.  }
  14.  cout << "\nIntroduce la segunda cadena: ";
  15.  fgets(str2, 99, stdin);
  16.  if (str2[strlen(str2)-1] == '\n'){
  17. str2[strlen(str2)-1] = '\0';
  18.  }
  19.  if(strstr(str,str2)!=NULL){
  20.      cout<<"Found match: "<<str2;
  21.  }
  22.  else{
  23.   cout<<"Error";
  24.  }
  25.  
  26.  return 0;
  27. }
  28.  

RETO: Crear un programa que haga por fuerzabruta una comprobación de una posible pass, la longitud se ha de determinar en el transcurso del programa.


Título: Re: Retos C/C++
Publicado por: ghastlyX en 3 Octubre 2010, 16:52 pm
Si no recuerdo mal, la función strstr realiza la comprovación a lo bestia, es decir, si tenemos una string de n carácteres y queremos buscar en ella otra de m, para cada carácter de la primera mira si los m - 1 siguientes coinciden, quedando así un coste de O(nm).

Por si a alguien le interesa, existen algoritmos más eficientes para realizar esto, que consiguen costes de O(n + m), es decir, lineales sobre la longitud de las strings, como por ejemplo Knuth-Morris-Pratt.


Título: Re: Retos C/C++
Publicado por: Komodo en 3 Octubre 2010, 16:57 pm
Bueno siempre me ha servido para estas pequeñas aplicaciones strstr tampoco creo que sea malo usar strstr, que hayan métodos mejores, pues sseguro..