Commits

danielmaxx committed 657eb53

Traducido statues. Nueva solución a network agregada.

--
danielmaxx

  • Participants
  • Parent commits c39fb94

Comments (0)

Files changed (14)

solutions/network-zyx.cpp

+/*
+ * author: Carlos Guia
+ */
+#include <vector>
+#include <deque>
+#include <limits>
+#include <stdio.h>
+using namespace std;
+
+// BEGIN CUT HERE
+#ifdef _MSC_VER
+#pragma warning(disable:4996)
+#pragma warning(push)
+#pragma warning(disable:4018)
+#endif  //  #ifdef _MSC_VER
+// END CUT HERE
+template<int kMaxN, typename _CapacityType, typename _FlowType = _CapacityType>
+class RelabelToFrontStatic {
+  int N;
+public:
+  void Init(int _N) {
+    N = _N;
+    memset(capacity_, 0, sizeof(capacity_));
+    memset(flow_, 0, sizeof(flow_));
+  }
+  inline _FlowType Capacity(int u, int v) const {
+    return capacity_[u][v] - flow_[u][v];
+  }
+  void AddEdge(int s, int d, const _CapacityType& c) {
+    capacity_[s][d] += c;
+  }
+  _FlowType CreateFlow(int source, int sink) {
+    //for ( int i = 0; i < g.N(); ++i ) flow_[i].assign(g[i].n.size(), 0);
+    memset(excess_, 0, sizeof(_FlowType) * N);
+    memset(height_, 0, sizeof(int) * N);
+    memset(index_, 0, sizeof(int) * N);
+    source_ = source;
+    sink_ = sink;
+    height_[source_] = N;
+    excess_[source_] = numeric_limits<_FlowType>::max();
+    gap_.assign(N + 1, 0);
+    gap_[0] = N - 1;
+    gap_[N] = 1;
+    list_.clear();
+    for ( int i = 0; i < N; ++i ) if ( Capacity(source_, i) >0  )
+      Push(source_, i);
+    while ( !list_.empty() ) {
+      const int u = list_.front(); list_.pop_front();
+      Discharge(u);
+    }
+    return excess_[sink_];
+  }
+private:
+  _FlowType excess_[kMaxN];
+  _FlowType flow_[kMaxN][kMaxN];
+  _CapacityType capacity_[kMaxN][kMaxN];
+  int height_[kMaxN];
+  int index_[kMaxN];
+  vector<int> gap_;
+  deque<int> list_;
+  int source_, sink_;
+
+  bool Internal(int n) const { return n != sink_ && n != source_; }
+  void Push(int u, int v) {
+    _FlowType flow = min(excess_[u], Capacity(u, v));
+    flow_[u][v] += flow;
+    flow_[v][u] -= flow;
+    excess_[u] -= flow;
+    if ( Internal(v) && excess_[v] == 0 ) {
+      if ( list_.empty() || height_[list_.front()] < height_[v] )
+        list_.push_front(v);
+      else
+        list_.push_back(v);
+    }
+    excess_[v] += flow;
+  }
+  void Relabel(int u, int h) {
+    height_[u] = h;
+    index_[u] = 0;
+    if ( h >= gap_.size() ) gap_.resize(h + 1);
+    ++gap_[h];
+  }
+  void Relabel(int u) {
+    const int old = height_[u];
+    int h = old;
+    for ( int i = 0; i < N; ++i ) if ( Capacity(u, i) > 0 )
+      h = min(h, height_[i]);
+    Relabel(u, h + 1);
+    if ( --gap_[old] == 0 ) {
+      for ( int i = 0; i < N; ++i ) if ( Internal(i) && height_[i] > old ) {
+        if ( height_[i] < N + 1 ) {
+          gap_[height_[i]] = 0;
+          Relabel(i, N + 1);
+        }
+      }
+    }
+  }
+  void Discharge(int u) {
+    while ( excess_[u] > 0 ) {
+      if ( index_[u] < N ) {
+        int v = index_[u];
+        if ( Capacity(u, v) > 0 && height_[u] > height_[v] )
+          Push(u, v);
+        else
+          ++index_[u];
+      } else {
+        Relabel(u);
+      }
+    }
+  }
+};
+// BEGIN CUT HERE
+#ifdef _MSC_VER
+#pragma warning(pop)
+#endif  //  #ifdef _MSC_VER
+// END CUT HERE
+
+typedef RelabelToFrontStatic<152, int> Grapth_t;
+
+int d(int x1, int y1, int x2, int y2)
+{
+  int dx = x1 - x2;
+  int dy = y1 - y2;
+  return dx * dx + dy * dy;
+}
+
+int main()
+{
+  freopen("network.in", "rt", stdin);
+  //freopen("network.out", "wt", stdout);
+  int T;
+  scanf("%d", &T);
+  Grapth_t graph;
+  int const source = 0;
+  int const sink = 1;
+  for (int t = 1; t <= T; ++t)
+  {
+    int N, M;
+    scanf("%d%d", &N, &M);
+    graph.Init(N * 2 + M + 2);
+    vector<int> R;
+    vector<int> X;
+    vector<int> Y;
+    for (int i = 0; i < N; ++i)
+    {
+      int c, r, x, y;
+      scanf("%d%d%d%d", &c, &r, &x, &y);
+      graph.AddEdge(i + 2, i + 2 + N, c);
+      graph.AddEdge(i + 2 + N, sink, 1000);
+      R.push_back(r * r);
+      X.push_back(x);
+      Y.push_back(y);
+    }
+    int const base = 2 + 2 * N;
+    for (int i = 0; i < M; ++i)
+    {
+      int x, y;
+      scanf("%d%d", &x, &y);
+      for (int j = 0; j < N; ++j) if (d(x, y, X[j], Y[j]) <= R[j])
+      {
+        graph.AddEdge(base + i, j + 2, 1);
+        graph.AddEdge(source, base + i, 1);
+      }
+    }
+    int flow = graph.CreateFlow(source, sink);
+    printf("Case #%d: %d\n", t, flow);
+  }
+  return 0;
+}

solutions/network.in

-1
+2
 2 11
 3 9 7 20
 2 14 7 5
 4 10
 12 4
 0 0
+10 0
+2 11
+3 9 7 20
+4 14 7 5
+5 25
+7 23
+11 25
+0 20
+12 20
+4 15
+9 15
+4 10
+12 4
+0 0
 10 0 

solutions/statues-danielmaxx.cpp

 
 char matrix[max_s+2][max_s+2];
 bool mark[max_s][max_s][max_s][max_s][max_s][max_s];
-state parent[max_s][max_s][max_s][max_s][max_s][max_s];
+//state parent[max_s][max_s][max_s][max_s][max_s][max_s];
 
 pos nextPos(const pos& curSt, int d, bool counter) {
     int movi[4] = {-1, 0, 1, 0};
             if(nSt1 == nInd || nSt2 == nInd) continue;
             if(mark[ni][nj][nSt1.I][nSt1.J][nSt2.I][nSt2.J]) continue;
             mark[ni][nj][nSt1.I][nSt1.J][nSt2.I][nSt2.J] = true;
-            parent[ni][nj][nSt1.I][nSt1.J][nSt2.I][nSt2.J] = cur;
+            //parent[ni][nj][nSt1.I][nSt1.J][nSt2.I][nSt2.J] = cur;
             q.push(state(nInd, nSt1, nSt2, cur.step+1));
         }
     }    
     return 1000000000;
 }
 
-void printPath(int M, int N) {
+/*void printPath(int M, int N) {
     state cur = final;
     state end(pos(-1, -1), pos(-1, -1), pos(-1, -1), -1);
     int top = 100, iters = 0;
         cur = parent[cur.ind.I][cur.ind.J][cur.st1.I][cur.st1.J][cur.st2.I][cur.st2.J];
         iters++;
     }
-}
+}*/
 
 int main() {
     
-    #ifndef _JUDGE
+    /*#ifndef _JUDGE
         freopen("estatuas.in", "r", stdin);
         freopen("estatuas.out", "w", stdout);
-    #endif
+    #endif*/
     
     int c; scanf("%d", &c);
     for(int ic=0; ic<c; ++ic) {
         memset(matrix, 0, sizeof(matrix));
-        memset(parent, -1, sizeof(parent));
+        //memset(parent, -1, sizeof(parent));
         pos K, L, P;
         scanf("%d %d %d %d %d %d", &K.I, &K.J, &L.I, &L.J, &P.I, &P.J);
         pos Kp, Lp;
         scanf("%d %d %d", &M, &N, &T);
         for(int i=0; i<M; ++i)
             scanf("%s", &matrix[i]);
-        printf("Indiana");
+        printf("Caso #%d: ", ic+1);
         int ans = answer(K, L, P, Kp, Lp, M, N);
         //printf("ans = %d\n", ans);
         if(ans<=T)
-            printf(" obtiene La Espada Maestra en %d pasos\n", ans)/*, printPath(M, N)*/;
+            printf("%d\n", ans)/*, printPath(M, N)*/;
         else
-            printf(", mala suerte\n");
+            printf("-1\n");
     }
     return 0;
 }

solutions/trip

Binary file removed.

statement/generar.sh

-#!/bin/bash
-
-latex --output-format=pdf problemas.tex
-rm -f problemas.aux problemas.log

statement/generar1.sh

+#!/bin/bash
+
+latex --output-format=pdf problemas1.tex
+rm -f problemas1.aux problemas1.log

statement/generar2.sh

+#!/bin/bash
+
+latex --output-format=pdf problemas2.tex
+rm -f problemas2.aux problemas2.log

statement/network/sample.in

 2
-
+2 11
+3 9 7 20
+2 14 7 5
+5 25
+7 23
+11 25
+0 20
+12 20
+4 15
+9 15
+4 10
+12 4
+0 0
+10 0
+2 11
+3 9 7 20
+4 14 7 5
+5 25
+7 23
+11 25
+0 20
+12 20
+4 15
+9 15
+4 10
+12 4
+0 0
+10 0 

statement/network/sample.out

-Case #1:
-Case #2:
+Caso #1: 5
+Caso #2: 7

statement/network_esp.tex

 \problem{Red Celular}{network}
 
 \noindent
-Una red celular es una red radial distribuida sobre espacios geogr\'aficos denominadas celdas, cada una es servida por al menos por un transmisor fijo denominado estaci\'on base. Cuando se unen todas esas celdas se permite una cobertura radial sobre un \'area geogr\'afica amplia. Cada transmisor tiene un rango (medido en metros) y una capacidad de clientes (medida en clientes por hora). Un transmisor puede atender a un cliente si est\'a dentro del rango de transmisi\'on y si el transmisor no ha sobrepasado su capacidad.\\ 
+Una red celular es una red radial distribuida sobre espacios geogr\'aficos denominados celdas, donde cada una es servida por al menos por un transmisor fijo denominado estaci\'on base. Cuando se unen todas esas celdas se permite una cobertura radial sobre un \'area geogr\'afica amplia. Cada transmisor tiene un rango (medido en metros) y una capacidad de clientes (medida en clientes por hora). Un transmisor puede atender a un cliente si est\'a dentro del rango de transmisi\'on y si el transmisor no ha sobrepasado su capacidad.\\ 
 
 \noindent
 WTFComm quiere saber si su red celular es lo suficientemente buena para manejar cierta demanda, para ello han generado unos datos artificiales basados en las estad\'isticas reales acerca de la ubicaci\'on de los clientes deseando saber cu\'antos clientes pueden atender en una hora con los transmisores que poseen.

statement/ovni2012.sty

 \usepackage[latin1]{inputenc}
+\usepackage[spanish]{babel}
 \usepackage{ifthen}
 
 \oddsidemargin  0.0in

statement/problemas.pdf

Binary file removed.

statement/problemas2.tex

+% Template for a problem -- CEIMEC 2010
+
+\documentclass[12pt]{article}
+\usepackage{epsfig}
+\usepackage{ovni2012}
+\usepackage{moreverb}
+
+% Choose one of the following styles for input files
+
+\inputstd        % input from stdin
+\outputstd       % output to stdin
+%inputfile       % input from named file
+%\outputfile      % output to named file
+
+\begin{document}
+\input{network_esp.tex}
+\input{beehive_esp.tex}
+\input{guitar_esp.tex}
+\input{statues_esp.tex}
+\end{document}

statement/statues_esp.tex

+\problem{Estatuas Sagradas}{statues}
+
+\noindent
+!`Indiana Jones est\'a de vuelta! Esta vez se encuentra tras el rastro de una antigua reliquia llamada La Espada Maestra. Dentro del gran Templo del Tiempo se encuentra frente a una dificil prueba. Dos estatuas sagradas se plantan delante de \'el y le dicen: \textit{Solo aquel que logre colocarnos en el lugar correcto lograr\'a llegar a La Espada Maestra}. El problema es que Indiana cuenta con tiempo limitado para resolver el misterio pues La Gran Roca caer\'a sobre el recinto si no resuelve el acertijo en menos del tiempo T.\\
+
+%Ra\'ul tiene una biblioteca inmensa. Es tan grande que no cabe en sus repisas, a\'un cuando \'el tiene muchas en su casa. Por ende, \'el ha decidido hacer una quema de libros (a la usanza fachista) y mantener los libros importantes en sus repisas. Sin embargo, \'el no ha le\'ido todos sus libros, as\'i que no est\'a seguro de cu\'ales libros debe quedarse. Por lo tanto, decidi\'o clasificar sus libros bas\'andose en su tem\'atica y asign\'andole un valor num\'erico, por lo que cada libro ha sido clasificado y marcado en una categor\'ia. Siendo un f\'isico de profesi\'on, \'el obviamente tiene preferencia por los libros de ciencia sobre los libros de moda y cosm\'etica.\\
+
+\noindent
+Las estatuas se mueven regidas por unas reglas bastante peculiares:\\
+
+\begin{itemize}
+\item Inicialmente, ambas estatuas est\'an en las posiciones $K$ y $L$, e Indiana se encuentra en la posici\'on $P$. Igualmente, suponiendo que al inicio Indiana est\'e orientado hacia el norte, la estatua 1 estar\'a orientada al sur y la estatua 2 estar\'a orientada al norte.
+\item Indiana Jones s\'olo se puede mover a las posiciones adyacentes a la suya, sin incluir las diagonales.
+\item Cada vez que Indiana se mueve en una direcci\'on, una estatua se mueve en la misma direcci\'on y la otra se mueve en la direcci\'on contraria. Por ejemplo, si Indiana se mueve hacia el Norte, la primera estatua se mover\'a hacia el Sur y la segunda estatua se mover\'a hacia el Norte.
+\item En el caso que el movimiento de Indiana Jones conduzca a una (o ambas) estatua a una posici\'on fuera del tablero o a una posici\'on inv\'alida, esta permanecer\'a en la misma posici\'on.
+\item Las estatuas pueden aplastar a Indiana si coinciden en la misma posici\'on, por lo que Indiana nunca tomar\'a una decisi\'on que conlleve a su aplastamiento.
+\item Si dos estatuas coinciden en una misma posici\'on, rebotar\'an y regresar\'an a sus posiciones anteriores.
+\item Indiana Jones jam\'as podr\'a salir del tablero ni caer en una posici\'on inv\'alida.
+\item Cada movimiento que hace Indiana le toma una unidad de tiempo.
+\item El tiempo comienza siempre en 0.
+\end{itemize}
+
+%\'El ha decidido que desea mantener sus libros en s\'olo dos repisas, conservando espacio para nuevos libros. Cada repisa tiene una capacidad, medida en cent\'imetros y no debe ser sobrepasada.\\
+
+\noindent
+Para resolver el acertijo, Indiana Jones debe llevar las estatuas desde sus posiciones iniciales $K$ y $L$ a las  posiciones $K'$ y $L'$, ambas al mismo tiempo.\\
+%Ayuda a Ra\'ul a determinar cuales libros debe quedarse para maximizar el valor de su biblioteca personal.\\
+
+\subsection*{Entrada}
+\noindent
+La primera l\'inea contendr\'a un entero $T$ indicando la cantidad de casos a evaluar. Seguidamente, la descripci\'on de $T$ casos de prueba
+
+\noindent
+La primera l\'inea contendr\'a seis enteros $K_i$, $K_j$, $L_i$, $L_j$, $P_i$ y $P_j$, referentes a la posici\'on inicial de la primera estatua, segunda estatua e Indiana Jones, respectivamente. Las posiciones estar\'an dadas en forma de fila y columna, donde la esquina superior izquierda es la posici\'on (0, 0). La segunda l\'inea contendr\'a cuatro enteros $K_i'$, $K_j'$, $L_i'$ y $L_j'$, referentes a la posici\'on final de la primera y segunda estatua. La tercera l\'inea contendr\'a tres enteros $M$, $N$ y $t$. Seguidamente, $M$ l\'ineas, cada una con $N$ caracteres representando el tablero donde se mover\'a Indiana Jones. El car\'acter `\#' representar\'a una posici\'on v\'alida del tablero. En cambio, el car\'acter `*' representar\'a una posici\'on inv\'alida.
+
+\inputnotice{statues}
+
+\subsection*{Salida}
+\noindent
+Por cada caso de prueba usted debe imprimir una l\'inea con el string \verb|"Caso #i: "|, donde $i$ es el n\'umero del caso de prueba, seguido por un entero indicando la cantidad de pasos necesarios para que Indiana obtenga la espada maestra. En caso que Indiana no pueda obtener la Espada Maestra se debe imprimir -1.\\
+
+\outputnotice{status}
+
+\sampleio{sample}\\
+
+\subsection*{Restricciones}
+
+\begin{itemize}
+\item $T$ $\leq$ 100
+\item 1 $\leq$ $N$ $\leq$ 10
+\item 1 $\leq$ $M$ $\leq$ 10
+\item 1 $\leq$ $t$ $\leq$ 50000000
+\end{itemize}
+