Día 03: ConneR and the A.R.C. Markland-N
Hay \(k\) restaurantes cerrados, así encontraremos la respuesta en \(O(k)\) estados, por eso una solución fuerza bruta es suficiente.
Code
#include <bits/stdc++.h>
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <ll> vll;
int main () {
ios::sync_with_stdio(false); cin.tie(0);
int tc;
cin >> tc;
while (tc--) {
int n, s, k;
cin >> n >> s >> k;
set <int> st;
for (int i = 0; i < k; i++) {
int a;
cin >> a;
st.insert(a);
}
int ans = INT_MAX;
for (int d = 0; ; d++) {
for (int sign: {1, -1}) {
int cur = s + sign * d;
if (1 <= cur and cur <= n and st.count(cur) == 0) {
ans = d;
}
}
if (ans != INT_MAX) break;
}
cout << ans << '\n';
}
return (0);
}Día 02: Number of Triplets
Si fijamos \(A, C\) con dos for podemos obtener cuál es el valor de \(B\) que necesitamos. Además, como todos los puntos son enteros podemos chequear si \(A_x + C_x \land A_y + C_y\) son pares para evitar trabajar con flotantes. Así, hemos fijado \(B = ((A_x + C_x) / 2, (A_y + C_y) / 2)\) y necesitamos chequear si este punto está en la entrada. Podemos hacer esto con un set (obtendrás TLE si usas un map) y así resolver el problema en \(O(n^2 \log n)\).
Code
#include <bits/stdc++.h>
using namespace std;
int main () {
int n;
cin >> n;
vector <pair <int, int>> point(n);
set <pair <int, int>> st;
for (int i = 0; i < n; i++) {
cin >> point[i].first >> point[i].second;
st.insert(point[i]);
}
int ans = 0;
for (int a = 0; a < n; a++) {
for (int c = a + 1; c < n; c++) {
pair <int, int> b;
int x = point[a].first + point[c].first;
int y = point[a].second + point[c].second;
if (x % 2 or y % 2) continue;
b.first = x / 2;
b.second = y / 2;
if (st.count(b)) ans++;
}
}
cout << ans << endl;
return (0);
}Además, podemos chequear si un punto está en la entrada en \(O(1)\) guardando los puntos en una matriz de booleanos. Pero, como las coordenadas pueden tomar valores negativos en \([-1000, 1000]\) podemos asociar a cada punto \((x, y) \to (x + 1000, y + 1000)\) (esto es una biyección). Usando esto, cada coordenada es no negativa, así podemos guardarla en nuestra matriz sin problemas.
Día 01: White poison gargle
Tenemos:
\[S = 1 + a + a^2 + a^3\dots + a^k\]
Podemos hallar una fórmula condensada de S y obtenemos:
\[S = \frac{a^{k + 1} - 1}{a - 1}\]
Ahora el problema se reduce a calcular \(S \bmod m\), donde \(m = 10^9 + 7\) (primo).
Para ello recordamos que podemos calcular \(a^{k + 1} \bmod m\) en \(O(\log k)\) usando exponenciación rápida y que tenemos las siguientes propiedades de aritmética modular:
\[(a + b) \bmod m = ((a \bmod m) + (a \bmod m)) \bmod m\]
\[(a * b) \bmod m = ((a \bmod m) * (a \bmod m)) \bmod m\]
\[(a - b) \bmod m = (((a \bmod m) - (a \bmod m)) \bmod m + m) \bmod m\]
Además podemos expresar \(S\) así:
\[S = (a^{k + 1} - 1) \cdot (a - 1)^{-1}\]
Y como \(m\) es primo, podemos calcular \((a - 1)^{-1}\) usando el pequeño teorema de Fermat y exponenciación rápida si \((a - 1) \bmod m \not = 0\). Sino, si \((a - 1) \bmod m = 0 \to a \bmod m = 1\) de modo que \(S = (k + 1) \bmod m\) en ese caso.
Lo anterior podemos implementarlo así:
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll m = 1e9 + 7;
ll add (ll a, ll b) { return ((a) % m + (b % m)) % m; }
ll sub (ll a, ll b) { return (((a) % m - (b % m)) + m) % m; }
ll mul (ll a, ll b) { return ((a) % m * (b % m)) % m; }
ll binpow (ll a, ll b) {
if (b == 0) return 1;
a %= m;
ll res = binpow(a, b / 2);
res = mul(res, res);
if (b % 2 == 1) res = mul(a, res);
return res;
}
ll inverse (ll a) { return binpow(a, m - 2); }
int main () {
ll a, k;
cin >> a >> k;
if (sub(a, 1) == 0) {
cout << add(k, 1) << '\n';
} else {
cout << mul(sub(binpow(a, k + 1), 1), inverse(a - 1)) << '\n';
}
return (0);
}