lhchavez

#!/usr/bin/python

import Image
import math

# calculates simple two-line intersection. be warned: fails miserably with
# vertical lines and parallelograms.
def intersection(p0, p1, p2, p3):
	m0 = (p1[1] - p0[1]) / float(p1[0] - p0[0])
	m2 = (p3[1] - p2[1]) / float(p3[0] - p2[0])

lhchavez

#!/usr/bin/python

import Image
import ImageDraw
import math
from xml.dom.minidom import parse
import sys
from mpmath import mp

divisions = 2

lhchavez

t ∈ [0, 1];
x(t) = 0.0000000000000000055471625557159340725376176154529062181733718807506255520255*t^302 - 0.000000000000000073364101000888831703733953581037511007054939579810582331399*t^301 + 0.00000000000000019993660043110753520337148440192171752144851216958770618608*t^300 + 0.0000000000000025431459190353075519117623598827064762116187905095073821053*t^299 - 0.000000000000025925946645421675754267336846692479715572284533512884725878*t^298 + 0.000000000000033895461820820261658723914655701363831301259561299803770339*t^297 + 0.00000000000098435998558754374882208672660807298710459239071613885704591*t^296 - 0.0000000000068611167133899914841924408007856853142977551403882403283457*t^295 - 0.0000000000048908713957691280882664471217742259158249732413864474770153*t^294 + 0.00000000029798626331047729269718080398515232860371117604820388543549*t^293 - 0.0000000012579473080466912761750295031070320627008549897730597637288*t^292 - 0.0000000050712723859962030166333419681481068633434285144559824963219*t^291 + 0.0000000672479633

lhchavez

Este problema es especial porque es el primero en omegaUp de solo salida! Usualmente lo que debes esperar cuando te enfrentes con uno de esos problemas es que sea un problema NP que no tiene una solución rápida, y usualmente te pedirán que te aproximes lo más posible a la solución óptima. Esto significa que te vas a tener que valer de técnicas ad-hoc y heurísticas para sacar puntos.

La solución del problema es bastante sencilla de explicar: haz una búsqueda en profundidad intentando todos los posibles movimientos por fuerza bruta hasta que te salga una solución aceptable e imprímela. El problema es que esta estrategia es $O(n!)$, y como $n$ puede valer hasta 30x30, puedes esperar que el programa corria varios milenios antes de encontrar la solución óptima. Hay tres trucos (en orden de importancia) para obtener una solución decente en un tiempo razonable: 

* No repetir estados.
* No "clavarse" con soluciones que parece que son muy buenas, pero en realidad llevan a callejones sin salida.
* Encontrar una maner

lhchavez

import java.io.*;
import java.util.*;

// Todos los problemas en Java _deben_ usar Main como nombre de clase.
class Main {
	public static void main(String[] args) throws IOException {
		// Declaración del scanner para poder leer por tokens.
		Scanner in = new Scanner(System.in);

		int a, b, c;

lhchavez

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(System.in);

		long a, b, c;
		a = in.nextInt();
		b = in.nextInt();

lhchavez

#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

#define IOI 2

struct Arco {

lhchavez

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

// Número de parejas de tubos de vidrio.
int N;

// La cantidad de cada sustancia.

lhchavez

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/max_cardinality_matching.hpp>

using namespace std;

// Un grafo no-dirigido.

lhchavez

Este es un problema que tiene una solución elegante y determinística pero requiere algoritmos avanzados bastante complicados. Lo bueno es que es posible aproximar a la solución utilizando fuerza bruta mediante backtracking.

El problema nos pide encontrar una manera de asignar sustancias a los tubos y después mezclarlas con las dos operaciones disponibles (suma y diferencia absoluta) para terminar con un acomodo homogéneo de sustancias: la diferencia entre el tubo con más cantidad y con menos cantidad de sustancia debe ser lo más pequeña posible. Una manera de hacerlo es proponer un intervalo $[a,b]$ y ver si es posible asignar sustancias y aparear los tubos de manera que la