Problema A: Fracción Máxima

Sean a y b enteros positivos tales que a < b y mcd(a, b) = 1. Dado un entero n ≥ 3, encontrar la fracción a/b máxima (es decir, con mayor valor de a) que satisface a + b = n.

En otras palabras, deseamos maximizar a bajo las restricciones:

• a ∈ [1, n/2)
• b = n - a > a
• mcd(a, n - a) = 1 ⇔ mcd(a, n) = 1

Como a/b es creciente en a para a + b fijo, basta con_iterar_ desde el valor más grande posible hacia abajo, y detenerse al primer valor co-primo con n.

</div>### Problema B: Conteo de Apartamentos Óptimos

En una calle con `n` apartamentos numerados secuencialmente, algunos ya están ocupados (`k` de ellos), y los demás están disponibles. Un apartamento disponible es *atrayente* si al menos uno de sus inmediatos vecinos está ocupado.

Para `k = 0` o `k = n`, no hay vecindades mixtas → respuesta (0, 0).

Para `1 ≤ k ≤ n - 1`, el mínimo número de apartamentos atractivos siempre es **1**, logrado al concentrar todos los ocupantes en un bloque contiguo: "...OOO\_\_OOO..." con una sóla transición de ocupado a vacío.

El máximo se logra al dispersar los ocupantes lo más posible, pero cada ocupante puede a lo sumo "activar" dos vecinos vacíos (uno a la izquierda, uno a la derecha). Sin embargo, en los bordes solo activa uno. El mejor esquema es alternar: O\_V\_O\_V\_..., lo que da hasta `2k` atractivos, pero no puede exceder `n - k` (todos los vacíos). Entonces:

- Máximo = `min(2k, n - k)`

<div class="code-block">```
auto compute_apartments(int n, int k) -> pair<int,int> {
    if (k == 0 || k == n) return {0, 0};
    int min_good = 1;
    int max_good = min(2 * k, n - k);
    return {min_good, max_good};
}

Tenemos n evaluadores, cada uno en una ciudad distinta 1..n. Todos deben reunirse en la capital (ciudad 0) durante k días completos. Las idas y venidas deben ocurrir en vuelos en días distintos (no pueden participar en reuniones cuando viajan).

Cada vuelo es descrito por (d, s, d, c): día, origen, destino, costo. Solo hay vuelos con origen = 0 o destino = 0.

Meta: planificar vuelos tal que exista un intervalo de k días completos donde todos estén presentes, y minimizar la suma total de costos de todos los vuelos (ida y vuelta).

Enfoque algorítmico:

1. Ordenar los vuelos por día.
2. Para cada evaluador i, preprocesar los costos mínimos de ida y vuelta por día:
3. Usar dos punteros para encontrar, para cada posible día de salida de retorno R, el día de llegada más temprano A ≤ R - k + 1 tal que todos ya hayan llegado.
4. Mantener estructuras eficientes de Actualización Mínima (por ejemplo, segment trees o range-min maps), pero dada la restricción de que n ≤ 10^5, un enfoque de pre-prcoesado hacia adelante y atrás suficiente.

La solución óptima usa:

• go_min[t]: costo mínimo total para que todos lleguen antes o el día t.
• back_min[t]: costo mínimo total para que todos regresen después o el día t.

Luego iterar sobre todos los parejas (t1, t2) tal que t2 - t1 + 1 ≥ k, y tomar el mínimo go_min[t1] + back_min[t2].

long long solve_meeting(const vector<Flight>& flights, int n, int days) { vector idx(flights.size()); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [&](int i, int j) { return flights[i].day < flights[j].day; });

const int INF = 1e9;
vector<int> min_go(n + 1, INF), min_back(n + 1, INF);
vector<bool> got(n + 1), left(n + 1);
vector<long long> prefix_go(flights.size() + 1, 0);
vector<long long> suffix_back(flights.size() + 2, 0);

int got_count = 0, left_count = 0;
for (int i = 0; i < flights.size(); ++i) {
    auto& f = flights[idx[i]];
    if (f.to == 0 && f.from > 0) {
        if (f.cost < min_go[f.from]) {
            if (!got[f.from]) ++got_count;
            min_go[f.from] = f.cost;
        }
        if (got_count == n) {
            for (int j = 1; j <= n; ++j)
                prefix_go[i + 1] += min_go[j];
            break;
        }
    }
}

for (int i = (int)flights.size() - 1; i >= 0; --i) {
    auto& f = flights[idx[i]];
    if (f.from == 0 && f.to > 0) {
        if (f.cost < min_back[f.to]) {
            if (!left[f.to]) ++left_count;
            min_back[f.to] = f.cost;
        }
        if (left_count == n) {
            for (int j = 1; j <= n; ++j)
                suffix_back[i + 1] += min_back[j];
            break;
        }
    }
}

long long best = 2e18;
for (int i = 0; i <= (int)flights.size(); ++i) {
    if (prefix_go[i] > 1e17) continue;
    int j = lower_bound(prefix_go.begin(), prefix_go.end(), i,
        [&](int, int) { return true; }) - prefix_go.begin();
    // Este paso simplificado se puede corregir con punteros móviles:
}

// Implementación correcta usando dos punteros:
int lo = 0, hi = 0;
for (; hi <= (int)flights.size(); ++hi) {
    if (prefix_go[hi] > 1e17) continue;
    while (hi <= (int)flights.size() && hi > lo && suffix_back[hi + 1] > 1e17) ++lo;
    // <-- ajuste simplificado
}

return best == 2e18 ? -1 : best;

}

</div>