(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:

Continue reading

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


Posted on by fortytwo_de


Siempre he tenido mucha curiosidad por los exploits. Nunca he entendido realmente cómo funcionan, muchas veces me han parecido brujería. Pero hoy he decidido entender su funcionamiento, y para ello he escrito un programa muy simple, como el típico programa que pregunta el nombre del usuario y luego le saluda.

#include <stdio.h>   

int main(int argc, char** argv) {
    char buffer[100];

    printf("What is your name?\n");
    scanf("%s", buffer);
    printf("Hello, %s!\n", buffer);

    return 0;
}

Puede parecer inocente, pero tiene una vulnerabilidad muy importante: no limita el número de caracteres que el usuario puede almacenar en buffer. Los lenguajes de programación "de alto nivel" (Python, Ruby, Perl, C#...) generalmente se encargan de evitar este tipo de problemas.

En lenguajes de más bajo nivel, como C, es mucho más fácil una vulnerabilidad de buffer overflow. Para entender el problema, hay que conocer los "registros de activación" (activation frames). Simplificando mucho un asunto complicado, podemos entender los registros de activación como una parte de la memoria que contiene la información necesaria para que una función sea ejecutada. Normalmente tienen este aspecto:

Continue reading

Posted on by fortytwo_de | Posted in ASM, Programación


Posted on by fortytwo_de


FizzBuzz es un problema ideado para comprobar que un programador es capaz de resolver problemas sencillos. Aunque es contraintuitivo, resulta que una gran parte de programadores no saben programar fuera de los quince problemas que saben resolver de memoria.

El enunciado del problema es muy sencillo:

Write a program that prints the numbers from 1 to 100. But for multiples of three print "Fizz" instead of the number and for the multiples of five print "Buzz". For numbers which are multiples of both three and five print "FizzBuzz".

La forma más directa de aproximarse a este problema es hacer una implementación al pie de la letra. Es decir (pseudocódigo):

if(n % 3 == 0):
    print "Fizz"
else if(n % 5 == 0):
    print "Buzz"
else if(n % 15 == 0):
    print "FizzBuzz"
else
    print n

Vale, hasta ahí todo bien. Las posibles ramificaciones de este programa son estas:

Continue reading

Posted on by fortytwo_de | Posted in C, Programación