Solucionario TAP 2015

Logramos que nuestra universidad fuera sede por primera vez! Muchas gracias a Exequiel Rivas por la organización.


Problemset

http://torneoprogramacion.com.ar/wp-content/uploads/2015/09/pruebaTAP2015.pdf

Scoreboard Final

http://torneoprogramacion.com.ar/2015/09/27/resultados-tap-2015/

Juez Online

A: http://coj.uci.cu/24h/problem.xhtml?pid=3381
B: http://coj.uci.cu/24h/problem.xhtml?pid=3382
C: http://coj.uci.cu/24h/problem.xhtml?pid=3383
D: http://coj.uci.cu/24h/problem.xhtml?pid=3384
E: http://coj.uci.cu/24h/problem.xhtml?pid=3385
F: http://coj.uci.cu/24h/problem.xhtml?pid=3386
G: http://coj.uci.cu/24h/problem.xhtml?pid=3387
H: http://coj.uci.cu/24h/problem.xhtml?pid=3388
I: http://coj.uci.cu/24h/problem.xhtml?pid=3389
J: http://coj.uci.cu/24h/problem.xhtml?pid=3390
K: http://coj.uci.cu/24h/problem.xhtml?pid=3391

Soluciones


Problema A – AM/FM



Problema B – Buen kilo de pan Flauta



Problema C – CompuTenis recargado



Problema D – Directo a la felicidad



Problema E – Empaquetamiento perfecto



Problema F – Favoritismo inducido



Problema G – Genética alienígena II



Problema H – Haciendo la tarea



Problema I – Invasión extraterrestre



Problema J – Jugando con Piedras II



Problema K – Kimetto, Kipsang y Kipchoge



11 comentarios:

  1. Me pudieran ayudar a corregir el bug en mi solucion al problema D Directo a la felicidad porque hago eso mismo usando disjoint set, gracias de antemano

    #include
    #define MAX 1001
    using namespace std;

    int P[MAX], level[MAX], ady[MAX][MAX], nodos[MAX], rutas[MAX];
    bool state[MAX];

    void create_set(int x){
    P[x] = x;
    level[x] = 0;
    }

    int set_of(int x){
    if(x != P[x]) P[x] = set_of(P[x]);//while(x != P[x]) x = P[x]; otra variante
    return P[x];
    }

    void join(int x, int y){
    int xx, yy;
    xx = set_of(x);
    yy = set_of(y);
    if ( level[xx] > level[yy] )
    {
    P[yy] = xx ; nodos[xx]++;
    }
    else
    {
    P[xx] = yy;nodos[yy]++;
    }
    if( level[xx] == level[yy] ) level[yy]++;
    }


    int main()
    {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M, R, E;
    cin >> N>> M>> R>>E;

    for( int i = 1; i <= N; i++ )
    {
    create_set(i);nodos[i] = 1;
    }

    for( int i = 1; i <= M; i++ )
    {
    int x, y; cin >> x >> y;
    ady[x][y] = 1;
    ady[y][x] = 1;

    if( set_of(x) != set_of(y) )
    {
    join(x, y);
    }
    }


    for( int i = 1; i < N; i++ )
    {
    for( int j = i+1; j <= N; j++ )
    {
    if( ady[i][j] == 0 && set_of(i)==set_of(j) ) rutas[set_of(i)]+=R;
    }
    }
    long long sum = 0;
    for( int i = 1; i <= N; i++ )
    {
    int tt = set_of(i);
    if( state[tt] == 0 && nodos[tt] != 1 )
    {
    //cout << rutas[P[i]] << endl;
    state[tt] = true;sum+=min(nodos[tt]*E,rutas[tt]);
    }
    }

    cout << sum << "\n";

    return 0;
    }

    ResponderEliminar
    Respuestas
    1. Me parece que tu error está en que join une dos componentes, no dos nodos. Cuando hacés nodos[xx]++ deberías agregarle el tamaño de la otra componente, no sumarle uno. De todas maneras usar union-find es un overkill para el problema. Es más fácil hacer dfs teniendo en cuenta que la cantidad de aristas en un grafo completo K_n es (n*(n-1))/2

      Eliminar
  2. Pueden dar mas detalles sobre como resolver el problema A? Tengo varios intentando resolverlo, y no entiendo cual es la solucion propuesta. Pueden extender mas la solucion?

    ResponderEliminar
    Respuestas
    1. Para cada circulo:
      Agrego su centro a candidatos

      Para cada par de círculos:
      Si se interesecan en los puntos p y q:
      Agrego p y q a candidatos

      Respuesta=0
      Para cada punto p en candidatos:
      Q=0
      Para cada estación e:
      Si p está dentro de e:
      Q++
      Respuesta =max( respuesta, Q)

      imprimir respuesta

      Eliminar
  3. Hola me podrían decir como sacaron los puntos de intersección entre dos circunferencias en c++, por que se sacarlos analíticamente pero no pasarlo a código. gracias.

    ResponderEliminar
    Respuestas
    1. http://math.stackexchange.com/questions/256100/how-can-i-find-the-points-at-which-two-circles-intersect
      es sólo escribir la formula(s)

      Eliminar
  4. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  5. Buenas, antes que nada gracias por compartir esta ayuda.

    Estoy tratando de resolver todos los problemas utilizando el lenguaje Swift, pero no puedo conseguir más inputs/outputs de prueba para verificar mis soluciones.

    Entré, por ejemplo, a http://coj.uci.cu/24h/problem.xhtml?pid=3381, luego de crear una cuenta en ese sitio, pero allí tampoco he encontrado datos de prueba. He revisado las FAQ de ese sitio, pero tampoco.

    Si pudieran postearlos por aquí o pasarme un link a donde se encuentran o las instrucciones, me vendrían de maravillas.

    ¡Gracias!

    ResponderEliminar
    Respuestas
    1. Los casos de prueba no son públicos, por lo que no los vas a conseguir. Intenta buscar el error en el código y hacer más inputs/outputs propios para debuggear. Si después de varios días no encontrás el error en tu código, siempre podés pedir ayuda a alguien más. Por ejemplo está el grupo de ICPC Latinoamérica: https://groups.google.com/forum/#!forum/latinoamerica-icpc , donde te pueden dar una mano.

      Eliminar
  6. Martín, ¡gracias por la respuesta!

    Lo que estaba buscando no era solucionar un error en particular sino que revisar si lo que hice funciona con más casos Tendré que elaborar varios casos propios entonces.

    ¡Saludos!

    ResponderEliminar