Saltar a contenido

Soluciones · Refuerzo PUJ 14 de noviembre

UVa 1203, UVa 10341, UVa 11413 y UVa 10810, los problemas propuestos de la sesión, cada uno con la idea, lo que cuesta y el código en Python y en C++. Los archivos están también en la carpeta codigo/.

UVa 1203, Argus

Idea

La cola de prioridad guarda un par por consulta, el instante de su próxima respuesta y su número. Empieza con \((P, \mathit{num})\), porque la primera respuesta llega a los \(P\) segundos. Sale el par menor y la consulta vuelve a entrar con el instante aumentado en su periodo. Comparar pares ya da el desempate del enunciado: en el mismo instante sale primero el número menor.

Complejidad

La cola nunca pasa de \(q\) pares, porque cada extracción trae una inserción. Son \(q\) inserciones y \(K\) vueltas: \(O((q + K) \log q)\).

Python

import heapq
import sys


def primeras(consultas, k):
    # Los números de las primeras k respuestas, en orden.
    periodo = {}
    cola = []
    for num, p in consultas:
        periodo[num] = p
        heapq.heappush(cola, (p, num))
    salida = []
    respondidas = 0
    while respondidas < k:
        instante, num = heapq.heappop(cola)
        salida.append(str(num))
        heapq.heappush(cola, (instante + periodo[num], num))
        respondidas = respondidas + 1
    return salida


def main():
    datos = sys.stdin.read().split()
    pos = 0
    consultas = []
    while datos[pos] != '#':
        consultas.append((int(datos[pos + 1]), int(datos[pos + 2])))
        pos = pos + 3
    k = int(datos[pos + 1])
    print('\n'.join(primeras(consultas, k)))


main()

C++

#include <cstdio>
#include <functional>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

int main() {
  // La cola saca primero el par menor: instante y, si empatan, número.
  priority_queue<pair<int, int>, vector<pair<int, int> >,
                 greater<pair<int, int> > > cola;
  vector<int> periodo(3001);
  char palabra[10];
  int num, p;
  while (scanf("%s", palabra) == 1 && palabra[0] != '#') {
    scanf("%d %d", &num, &p);
    periodo[num] = p;
    cola.push(make_pair(p, num));
  }
  int k;
  scanf("%d", &k);
  for (int i = 0; i < k; i++) {
    pair<int, int> menor = cola.top();
    cola.pop();
    printf("%d\n", menor.second);
    cola.push(make_pair(menor.first + periodo[menor.second], menor.second));
  }
  return 0;
}

UVa 10341, Solve It

Idea

La función viene dada, así que lo que queda es comprobarle dos cosas. Derivando, cada sumando de \(f'\) es menor o igual que cero en \([0,1]\) por los rangos del enunciado, de modo que \(f\) no crece y hay a lo sumo una raíz. Y hay raíz exactamente cuando \(f(0) \geq 0 \geq f(1)\): sin esa comprobación el ciclo igual termina y devuelve un número que no es raíz de nada. Cien vueltas dejan el intervalo en \(2^{-100}\) del original y evitan discutir la tolerancia.

Complejidad

Cien evaluaciones por caso, o sea constante; el total es lineal en la cantidad de casos.

Python

import math
import sys


def f(p, q, r, s, t, u, x):
    # El lado izquierdo de la ecuación, evaluado en x.
    return (p * math.exp(-x) + q * math.sin(x) + r * math.cos(x)
            + s * math.tan(x) + t * x * x + u)


def resolver(p, q, r, s, t, u):
    # f es decreciente en [0, 1]: hay raíz solo si f(0) >= 0 >= f(1).
    if f(p, q, r, s, t, u, 0.0) < 0.0 or f(p, q, r, s, t, u, 1.0) > 0.0:
        respuesta = 'No solution'
    else:
        lo = 0.0
        hi = 1.0
        vuelta = 0
        while vuelta < 100:
            medio = (lo + hi) / 2.0
            if f(p, q, r, s, t, u, medio) > 0.0:
                lo = medio
            else:
                hi = medio
            vuelta = vuelta + 1
        respuesta = '%.4f' % ((lo + hi) / 2.0)
    return respuesta


def main():
    salida = []
    for linea in sys.stdin:
        datos = linea.split()
        if len(datos) == 6:
            p = int(datos[0])
            q = int(datos[1])
            r = int(datos[2])
            s = int(datos[3])
            t = int(datos[4])
            u = int(datos[5])
            salida.append(resolver(p, q, r, s, t, u))
    print('\n'.join(salida))


main()

C++

#include <cmath>
#include <cstdio>

double f(int p, int q, int r, int s, int t, int u, double x) {
  // El lado izquierdo de la ecuacion, evaluado en x.
  return p * exp(-x) + q * sin(x) + r * cos(x) + s * tan(x) + t * x * x + u;
}

int main() {
  int p, q, r, s, t, u;
  while (scanf("%d %d %d %d %d %d", &p, &q, &r, &s, &t, &u) == 6) {
    if (f(p, q, r, s, t, u, 0.0) < 0.0 || f(p, q, r, s, t, u, 1.0) > 0.0) {
      printf("No solution\n");
    } else {
      double lo = 0.0, hi = 1.0;
      for (int vuelta = 0; vuelta < 100; vuelta++) {
        double medio = (lo + hi) / 2.0;
        if (f(p, q, r, s, t, u, medio) > 0.0) {
          lo = medio;
        } else {
          hi = medio;
        }
      }
      printf("%.4f\n", (lo + hi) / 2.0);
    }
  }
  return 0;
}

UVa 11413, Fill the Containers

Idea

La pregunta que se contesta de una pasada es si alcanza la capacidad \(t\): se llena el contenedor actual mientras quepa el recipiente siguiente, se abre otro cuando no cabe, y \(t\) alcanza si usa a lo más \(m\). Con más capacidad nunca hacen falta más contenedores, así que la decisión es monótona y se biseca entre el recipiente más grande y la suma de todos.

Complejidad

\(O(\log S)\) decisiones de \(O(n)\), con \(S\) la suma de los recipientes: \(O(n \log S)\) por caso, sin importar \(m\).

Python

import sys


def alcanza(c, m, t):
    # Con capacidad t, ¿bastan m contenedores?
    usados = 1
    lleno = 0
    for x in c:
        if lleno + x > t:
            usados = usados + 1
            lleno = x
        else:
            lleno = lleno + x
    return usados <= m


def menorCapacidad(c, m):
    # El menor t en [max(c), sum(c)] que cumple alcanza(c, m, t).
    lo = max(c)
    hi = sum(c)
    while lo < hi:
        medio = (lo + hi) // 2
        if alcanza(c, m, medio):
            hi = medio
        else:
            lo = medio + 1
    return lo


def main():
    datos = sys.stdin.read().split()
    pos = 0
    salida = []
    while pos < len(datos):
        n = int(datos[pos])
        m = int(datos[pos + 1])
        pos = pos + 2
        c = [int(x) for x in datos[pos:pos + n]]
        pos = pos + n
        salida.append(str(menorCapacidad(c, m)))
    print('\n'.join(salida))


main()

C++

#include <cstdio>
#include <vector>

using namespace std;

bool alcanza(const vector<int> &c, int m, int t) {
  // Con capacidad t, bastan m contenedores?
  int usados = 1;
  int lleno = 0;
  for (size_t i = 0; i < c.size(); i++) {
    if (lleno + c[i] > t) {
      usados = usados + 1;
      lleno = c[i];
    } else {
      lleno = lleno + c[i];
    }
  }
  return usados <= m;
}

int menorCapacidad(const vector<int> &c, int m) {
  // El menor t en [max(c), suma(c)] que cumple alcanza(c, m, t).
  int lo = 0;
  int hi = 0;
  for (size_t i = 0; i < c.size(); i++) {
    if (c[i] > lo) {
      lo = c[i];
    }
    hi = hi + c[i];
  }
  while (lo < hi) {
    int medio = lo + (hi - lo) / 2;
    if (alcanza(c, m, medio)) {
      hi = medio;
    } else {
      lo = medio + 1;
    }
  }
  return lo;
}

int main() {
  int n, m;
  while (scanf("%d %d", &n, &m) == 2) {
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
      scanf("%d", &c[i]);
    }
    printf("%d\n", menorCapacidad(c, m));
  }
  return 0;
}

UVa 10810, Ultra-QuickSort

Idea

Cada intercambio de vecinos arregla exactamente una pareja fuera de orden, así que lo que se pide es el número de parejas \((i,j)\) con \(i<j\) y \(a_i > a_j\). Las de un tramo se reparten en tres clases: las dos puntas en la mitad izquierda, las dos en la derecha, y una en cada mitad. Las dos primeras son el mismo problema más chico; la tercera se cuenta al mezclar, porque cuando sale un elemento de la derecha todos los pendientes de la izquierda son mayores que él.

Complejidad

Hay \(\log_2 n\) niveles de llamadas y en cada uno la mezcla mueve los \(n\) elementos una vez, de modo que el total es \(\Theta(n \log n)\). El contador va en long long. Medido con \(n = 499\,999\): 0,20 s en C++ y 5,1 s en Python, así que al juez se envía la de C++.

Python

import sys


def mezclar(a, aux, ini, medio, fin):
    # Mezcla a[ini:medio) con a[medio:fin) y cuenta las parejas que cruzan:
    # cada elemento que sale de la derecha aporta los que faltan a la izquierda.
    i = ini
    j = medio
    k = ini
    cruzadas = 0
    while k < fin:
        if i < medio and (j >= fin or a[i] <= a[j]):
            aux[k] = a[i]
            i = i + 1
        else:
            aux[k] = a[j]
            j = j + 1
            cruzadas = cruzadas + (medio - i)
        k = k + 1
    a[ini:fin] = aux[ini:fin]
    return cruzadas


def contar(a, aux, ini, fin):
    # Ordena a[ini:fin) en el lugar y devuelve cuántas inversiones tenía.
    total = 0
    if fin - ini > 1:
        medio = (ini + fin) // 2
        total = contar(a, aux, ini, medio)
        total = total + contar(a, aux, medio, fin)
        total = total + mezclar(a, aux, ini, medio, fin)
    return total


def main():
    datos = sys.stdin.buffer.read().split()
    pos = 0
    salida = []
    n = int(datos[pos])
    pos = pos + 1
    while n != 0:
        a = [0] * n
        i = 0
        while i < n:
            a[i] = int(datos[pos])
            pos = pos + 1
            i = i + 1
        aux = [0] * n
        salida.append(str(contar(a, aux, 0, n)))
        n = int(datos[pos])
        pos = pos + 1
    sys.stdout.write('\n'.join(salida) + '\n')


main()

C++

#include <cstdio>
#include <vector>

using namespace std;

long long mezclar(vector<int> &a, vector<int> &aux, int ini, int medio, int fin) {
  // Mezcla a[ini:medio) con a[medio:fin) y cuenta las parejas fuera de orden.
  int i = ini, j = medio, k = ini;
  long long cruzadas = 0;
  while (k < fin) {
    if (i < medio && (j >= fin || a[i] <= a[j])) {
      aux[k] = a[i];
      i = i + 1;
    } else {
      aux[k] = a[j];
      j = j + 1;
      cruzadas = cruzadas + (medio - i);
    }
    k = k + 1;
  }
  for (k = ini; k < fin; k++) {
    a[k] = aux[k];
  }
  return cruzadas;
}

long long contar(vector<int> &a, vector<int> &aux, int ini, int fin) {
  // Ordena a[ini:fin) en el lugar y devuelve cuantas inversiones tenia.
  long long total = 0;
  if (fin - ini > 1) {
    int medio = (ini + fin) / 2;
    total = contar(a, aux, ini, medio);
    total = total + contar(a, aux, medio, fin);
    total = total + mezclar(a, aux, ini, medio, fin);
  }
  return total;
}

int main() {
  int n;
  while (scanf("%d", &n) == 1 && n != 0) {
    vector<int> a(n), aux(n);
    for (int i = 0; i < n; i++) {
      scanf("%d", &a[i]);
    }
    printf("%lld\n", contar(a, aux, 0, n));
  }
  return 0;
}