(void *) blog

Posted on by fortytwo_de


Los últimos dos concursos amistosos de la olimpiada informática han sido temáticos, teniendo a Beremiz Samir como protagonista. Los problemas eran generalmente muy interesantes, aunque quizás más matemáticos, comparados con otros problemas de la olimpiada.

En cualquier caso, he podido resolver un par de ellos, que me gustaría compartir. El primero de ellos es el de “El hombre que calculaba”. El enunciado, sin la floritura del PDF original, es el siguiente:

Se quieren repartir x caballos entre tres hermanos. A cada uno de ellos le corresponde una fracción de los camellos (f1, f2, f3), pero la división no es exacta. Calcula el número de camellos que tendría que haber originalmente para que al añadir uno al lote, sobren dos y las divisiones sean exactas.

Después de darle varias vueltas, expresé así el problema:

$$ f_1 x + f_2 x + f_3 x = x - 2 \\ f x = x - 2 $$

(donde f es la suma de f1, f2 y f3)

Entonces, sólo es cuestión de despejar para x:

$$ fx - x = -2 \\ (f-1)x = -2 \\ x = \frac{-2}{f-1} $$

Entonces, hacer el programa para resolver el problema es muy sencillo:

#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
using namespace std;

float evaluate(string frac) {
    int num = -1, denum = -1;
    string buf;
    for(size_t i = 0; i < frac.length(); i++) {
        if(frac[i] == '/') {
            num = atoi(buf.c_str());
            buf = "";
        } else {
            buf += frac[i];
        }
    }
    denum = atoi(buf.c_str());

    return (float)num / denum;
}

bool check(float n) {
    return floor(n) == (int)n && n >= 1;
}

int main() {
    int cases;
    cin >> cases;

    for(int i = 0; i < cases; i++) {
        string frac1, frac2, frac3;
        cin >> frac1 >> frac2 >> frac3;

        float f1 = evaluate(frac1), f2 = evaluate(frac2), f3 = evaluate(frac3);
        float sum = f1 + f2 + f3;
        float coefficent = sum - 1;
        float x = -2 / coefficent;

        // Comprobar que no hay que partir ningún animal
        bool valid = true;
        valid &= check(f1 * x);
        valid &= check(f2 * x);
        valid &= check(f3 * x);
        if(valid) 
            cout << x-1 << endl;
        else
            cout << "no" << endl;
    }
}

El enunciado completo del problema está disponible aquí.

El siguiente problema que me ha parecido interesante es el de "Los 60 melones". El enunciado es:

La entrada consiste en diversos casos. Cada caso consiste en el número total de melones m, el precio de los melones de la primera partida (x por un dinar), el precio de los melones de la segunda partida (y por un dinar), y el beneficio total deseado t. Todos los números son naturales entre 1 y 10^6. Se cumple x ≤ m, y ≤ m, y x ̸= y.

Bien. Lo he planteado como un sistema de ecuaciones:

Ups. Sí que ha quedado grande.

Una vez se conoce la fórmula para calcular el número de melones en la primera partida, el programa es, otra vez, muy sencillo:

#include <iostream>
#include <cmath>

using namespace std; 

bool check(float n, int m) {
    float intpart;
    return modf(n, &intpart) == 0 && n >= 0 && n <= m;
}

int main() {
    int m, x, y, t;
    while(cin >> m >> x >> y >> t && m != -1) {
        float n1 = (t * x * y - x * m) / (float)(y - x);
        if(check(n1, m)) {
            cout << (unsigned int) n1 << endl;
        } else {
            cout << "no" << endl;
        }
    }
    return 0;
}

El enunciado original se puede descargar aquí.

Posted on by fortytwo_de | Posted in Matemáticas, Programación


9 Responses to Olimpiada Informática 2013

  1. Ricardo Antonio says:


    Hola amigo,yo llegue a la misma conclusión que tú,solo que el juez no me lo acepta…,ves el fallo?

    #include
    #include

    int main(int argc, char *argv[])
    {
    long long int m,x,y,t,check;
    while(scanf("%lli%lli%lli%lli",&m,&x,&y,&t)>0)
    {
    check=1;
    long long int a=((t*x*y)-(x*m));
    long long int b=(y-x);
    long long int result=1;
    if (b==0)
    check=0;
    else
    result=a/b;
    if(check && a%b==0 && result>=0 && result<=m )
    printf("%llu\n",(unsigned long long int)result);
    else
    printf("no\n");
    }
    return 0;
    }


    • fortytwo_de says:


      Hola,

      La verdad es que ni idea de por qué no te lo acepta, en principio parece que está bien.

      A mí tampoco me lo daba como válido, dice que Time Limit.


  2. Ricardo Antonio says:


    Si verdad?el tuyo lo he probado en c++,modificando algunas cosas como usar int en lugar de float y quitar la funcion check es decir,mi mismo codigo pero en c++ y me da Time Limit también..haber que nos contesta Omer


  3. Jose says:


    Mi solución también se parece a la de ustedes, pero me sale: No supera los juegos de pruebas: tiempo de CPU superado (0 puntos)

    Así que envié tu código para probar y también sale: No supera los juegos de pruebas: tiempo de CPU superado (0 puntos)


    • Jose says:


      Una consulta fortytwo_de, el análisis y tu intención de ayudarnos a los novatos esta bien,pero porque postear código que no acepta el juez? o es que a ti si te acepto? , porque en mi desesperación para probar mandé tu codigo y pues lo dicho: No supera los juegos de pruebas: tiempo de CPU superado (0 puntos)


      • fortytwo_de says:


        Hola Jose,

        Principalmente posteo en este blog para tener una “biblioteca” de cosas que me he ido encontrando en los problemas de la Olimpiada para las que he tenido que “sentarme a pensar” y luego puedo usarlas como resultado en otros problemas similares.

        A mí también me da TL, pero en principio el código está bien. Omer dice que es posible que el tiempo que el Juez da no sea suficiente para el caso de pruebas, está investigándolo. De todas formas, te recomiendo que te suscribas al grupo de la olimpiada: https://groups.google.com/forum/#!forum/olimpiada-informatica


  4. Cash Advance Online says:


    famous please click the next website page


  5. young tightpussy says:


    Nice post. I learn something totally new and challenging on websites
    I stumbleupon on a daily basis. It’s always exciting to read through content from other authors and practice
    something from other sites.


  6. Amie says:


    Attractive section of content. I just stumbled upon your
    weblog and in accessin capital to assert that I acquire actually enjoywd account youur
    blog posts. Any way I’ll be subscribing to your augment and even I
    achievement you access consistently quickly.


Leave a Reply to young tightpussy Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>