En nuestro problema se trata del cambio entre la moneda por excelencia en los intercambios (futuros) en Internet y nuestro querido (y cada vez más deseado) Euro.
El programa que se busca (como todos los de este concurso) es una aplicación de consola, es decir sin entorno gráfico, que tiene que leer los datos de su entrada standard (cin en el lenguaje C++) y escribir los resultados en su salida standard (cout). Tanto los datos de entrada como los de salida son ASCII, es decir, texto legible por los humanos corriente y moliente. Las utilidades para la presentación de las soluciones en el concurso se ocuparán de redirigir la entrada y salida de nuestra aplicación para que los datos adecuados fluyan por ellos para poner a prueba nuestra propuesta de solución y verificar que es correcta. Todo esto es común para todos los problemas del concurso, ya no incidiré más sobre ello (¡prometo!).
La aplicación debe resolver un número determinado de casos distintos. Esto nos obliga a mejorar la rapidez de resolución de nuestro algoritmo para que éste encuentre la respuesta en un tiempo razonable. En este primer problema el número máximo de casos propuestos será de 100.
Cuando el problema indica claramente los límites de los parámetros nos facilita la vida enormemente. Sobre todo cuando esos límites deben traducirse en reserva de memoria (dimensionamiento de variables). No va a ser el caso de esta aplicación.
El valor que nos llegará en la primera línea de datos a nuestra entrada va a ser el número de casos a estudiar. Como los casos son completamente independientes entre sí el resolver un número variable de casos solamente va a implicar en nuestra aplicación la existencia de un bucle en cuyo interior se encierre el verdadero algoritmo.
Lo codificaremos así:
int T;
cin >> T;
for (int t=0; t<T; t++)
{
// algoritmo
}
Poco que comentar. Leemos el número de casos a resolver (T) y ejecutamos un bucle, controlado por la variable t, que repita el algoritmo el número adecuado de veces. Es una costumbre, a la que nadie nos obliga por supuesto, en los bucles de C y C++ que el índice que lo controla comience en cero y termine en uno menos que el número de repeticiones. Esto es así por coherencia con la forma de indexar los arrays en estos lenguajes, aunque en este caso concreto no haya ningún array al que acceda el bucle.
Para cada caso recibiremos la cantidad de euros con la que comenzamos en una sola línea y, en la siguiente línea, un número indeterminado de valores de la cotización (euros por bitcoin) sucesivos.
Nuestra misión es calcular la máxima cantidad de euros que podemos tener al final del periodo si hacemos las compras y ventas de moneda en los momentos más adecuados.
Nos indican que nunca compraremos ni venderemos fracciones de moneda ni la cotización de las monedas va a ser fraccionaria. Esto nos dice que las variables que emplearemos serán de tipo int (admite en C++ un valor máximo razonable para ser muy rico). Es un tipo de datos que se maneja muy bien en C++.
Cuando no se limita, como en este caso, la cantidad de datos que debemos manejar nos entra un nerviosismo especial a los programadores porque no tenemos ni idea de cuánto dimensionar la variable que va a contener los datos con los que trabajaremos para no quedarnos cortos pero sin pasarnos para no obtener errores de memoria agotada.
Esta dificultad desaparece cuando no se necesitan guardar los datos que se manejan sino que se puede ir aplicando sobre ellos el algoritmo conforme los vamos adquiriendo. ¿Será este nuestro caso? ¡Ojalá!
El algoritmo del primer problema del concurso, para no desmoralizar, es muy sencillo. ¿Cuándo debemos comprar bitcoins? Cuando vayan a empezar a subir. ¿Y cuándo venderlos? Cuando vayan a empezar a bajar. Así que es un problema que se resume en encontrar máximos y mínimos relativos en la serie de datos que vamos recibiendo. Es una buena noticia porque sólo necesitamos guardar dos datos de la serie para localizar los máximos y los mínimos relativos, el valor anterior y el valor actual. Así que definiremos dos valores int: last, para el valor del cambio anterior y cambio para el actual. Cuando acabemos el ciclo pasaremos el valor de cambio al valor de last, perdiendo el valor guardado en ésta, y leeremos el siguiente valor de la serie en cambio.
Es evidente que cuando sea bueno comprar bitcoins será mejor vender todos los euros que sólo parte. Y lo mismo al revés. Así que primero compraremos bitcoins y después compraremos euros y así sucesivamente. Como comprar o vender euros y las condiciones que lo rigen son iguales, inversas en realidad, no haremos dos trozos de programa diferentes sino uno mismo controlando la transacción que toque por medio de una variable de tipo bool (valores true o false) que llamaremos buyBit y que valdrá true cuando toque vender euros y comprar bitcoins.
Como he dicho antes en cada transacción venderemos toda la moneda que tengamos por la otra. O sea que podemos caer en la tentación de usar una única variable para la cantidad de dinero que tenemos en cada momento y, por medio de la variable buyBit saber qué moneda representa. Sería un error porque nos han especificado que no podemos comprar o vender fracciones de moneda y, como el cambio se expresa en euros por bit (y tampoco puede ser fraccionario) cuando cambiemos bitcoins por euros siempre podremos cambiar todos los bitcoins por euros, pero lo contrario no es cierto puesto que al dividir los euros que tengamos por los euros por bitcoin del cambio nos puede quedar un resto de euros que no podemos cambiar. Estos euros quedarán en nuestra variable de euros para ser sumados a los euros que obtengamos por la venta de los bitcoins. Así necesitaremos una variable por cada moneda. Las llamaremos euro y bitcoin.
Empecemos a escribir el interior del bucle definiendo las variables que vamos a emplear y dándoles, o leyendo según el caso, sus valores iniciales:
int euro,bitcoin,cambio,last;
bitcoin=0;
cin >> euro;
cin >> last;
bool buyBit=true;
Comenzamos con 0 bitcoins y la cantidad en euros que nos digan. buyBit vale true porque la primera operación que debemos hacer es comprar bitcoins. Como con el primer valor de la serie de cambios no podemos hacer nada (porque no hay valor anterior que guardar) leemos directamente el primer valor en la variable last.
Y ahora comenzará un bucle en el que en cada repetición procesaremos cada valor de la serie de cambios que recibamos. Cuando no sé qué valor poner en la comparación de finalización de un bucle pongo true (como si no fuera a terminar nunca) y después, según lo vea más sencillo, o escribo la comparación en el lugar normal o hago una comparación en mitad del bucle y programo una instrucción break para que salga del bucle.
Quedaría algo así:
while (true)
{
cin >> cambio;
if (buyBit)
{
if (cambio>last) // buy bitcoin at last
{
bitcoin=euro/last;
euro-=last*bitcoin;
buyBit=false;
}
}
else
{
if (cambio<last) // buy euros at last
{
euro+=bitcoin*last;
bitcoin=0;
buyBit=true;
}
}
last=cambio;
}
Creo que necesita poca explicación. Leemos un nuevo valor de cambio. Según el valor de buyBit hacemos la comparación en un sentido o la inversa. Si toca comprar bitcoins esperaremos a que el cambio empiece a subir (cambio>last) y en ese momento cambiamos al valor de cambio guardado en last. Para el cambio inverso lo mismo pero al revés. La única diferencia entre ambos procesos es que en un caso obtenemos la cantidad de la nueva moneda mediante una división y en el inverso por una multiplicación, por lo que en el primer caso nos pueden quedar unos euros de resto mientras que en el segundo siempre se cambian todos los bitcoins. Cuando se cambia de moneda cambiamos el valor de la variable buyBit. Al final del bucle guardamos el valor de cambio en last.
La condición de final del bucle es que se termine la línea de datos, es decir, toda la serie de cambios están en una única línea.
Yo sé que las variables de tipo stream (como cin) tienen un método eof que vale true después de que intentamos hacer una lectura después del final de un fichero. ¿Habrá algo parecido para detectar el final de una línea? Como no lo sé la solución es buscar en la ayuda de la clase stream. En otros lenguajes el método se denomina eol (end of line), así que busco algo que se parezca a eso sin suerte. No digo que no exista, digo que yo no lo he encontrado.
El inconveniente, para este caso particular, es que a la hora de procesar la entrada de caracteres la librería de C++ trata los finales de línea como si fueran espacios.
Hay un método que lee una línea de caracteres entera y la almacena en una variable de tipo string. Desde esta variable string podríamos procesar la lectura de los enteros.
Yo me he decidido por otra forma usando el método peek de cin que devuelve el siguiente carácter que va a ser leído del stream pero sin quitarlo, es decir que se usará en la siguiente lectura. Me beneficio de que, después de leer un entero de cin el siguiente carácter listo para ser leído es el que está justo detrás del último número leído (normalmente el espacio que separa las cantidades). ¿Cómo me aseguro de que realmente las cosas funcionan así? Usando el debug y ejecutando paso a paso el programa para ver cómo se comporta. ¡Qué gran invento para la programación!
Lo que voy a hacer es, al comienzo del bucle, comprobar si el próximo carácter que se va a leer es un final de línea ('\n') y el bucle debe terminar sin procesar nada más porque significará que el anterior número leído, en la repetición del bucle anterior, era el último de la línea de datos. Añado una comprobación anterior que, usando el mismo método peek, va a ir leyendo todos los caracteres espacio en blanco de tal forma que nos funcione el algoritmo aunque detrás del último número de la línea haya espacios en blanco. El comienzo del bucle quedaría:
while (cin.peek()==' ') cin.get(); // salto espacios
if (cin.peek()=='\n') break; // EOL
Cuando ha terminado el bucle, si la última transacción que hemos hecho ha sido compra de bitcoins, deberemos cambiarlos a euros por el último cambio que se habrá quedado guardado en la variable last. Es la mejor opción porque ni no los habríamos cambiado antes.
if (!buyBit)
euro+=bitcoin*last;
Así que ya sólo queda, para terminar el algoritmo, escribir en la salida del programa el resultado que nos piden que es la cantidad de euros que obtendremos:
cout << euro << endl;
Y eso es todo. Compilar, ejecutar y enviar la solución.
De aquí se puede descargar el programa completo.
No hay comentarios:
Publicar un comentario