Sums

Explicación

Una observación crucial es que si podemos formar un número $x$, podemos formar cualquier número $x + k\cdot a_0$, donde k es un entero no negativo. Podríamos sentirnos tentados a reescribir esto así: si podemos formar $x$, podemos formar todos los $y \equiv x \mod a_0$. Si esto fuera efectivamente el caso, podemos ejecutar una DP 0/1 simple para averiguar qué módulos podemos ensamblar, y para responder una consulta $b_i$, simplemente podemos imprimir $\texttt{dp}[b_i \mod a_0]$. ¡Sin embargo, esta solución tiene un fallo; hay que pensar por qué antes de seguir!

El problema ocurre cuando $x > a_0$. Por ejemplo, si $n = 2$ y $a = \{3, 5\}$, podemos construir 8, pero no podemos construir 2, aunque $2 \equiv 8 \mod a_0$. Por suerte, esto solo requiere un arreglo menor para nuestra DP. Hay que intentar pensarlo uno mismo, pero se puede consultar la implementación de abajo si uno se traba.

Implementación

Complejidad temporal: $\mathcal{O}(NA)$

El límite de tiempo es bastante ajustado para este problema. Con $n \leq 5000$ y $a_i \leq 50000$, terminamos teniendo alrededor de $2.5\text{e}8$ operaciones. Aquí hay algunas optimizaciones que tuve que usar:

• Uso un arreglo $\texttt{vis}$ en mi implementación, y limpiarlo en cada iteración resultó ser demasiado lento. Así que, en lugar de simplemente guardar verdadero/falso para si un elemento está visitado, guardé cuántas veces ese elemento había sido visitado a lo largo de todas las iteraciones, aprovechando el hecho de que en cada iteración, todos los elementos se visitarán exactamente una vez, lo que implica que después de la iteración $i$, cada elemento debería haber sido visitado un total de $i$ veces. Otra alternativa es simplemente invertir $\texttt{vis}$ en cada iteración siguiente: es decir, en la iteración 1, false = no visitado, true = visitado; pero en la iteración 2, false = visitado, true = no visitado; etc.
• Teóricamente, todos los $a_0$ del editorial de arriba se pueden reemplazar por un $a_i$ arbitrario; de hecho, ni siquiera importa la condición de que $a$ esté ordenado. Sin embargo, lo elegimos simplemente por ser el valor más pequeño, lo que mejora marginalmente el tiempo de ejecución; usar $a_1$ en su lugar realmente causa TLE para el siguiente código.

Mientras se lee el siguiente código, puede ser útil considerar que nuestra DP es equivalente a ejecutar un algoritmo de camino más corto sobre un grafo donde cada nodo $i \in [0, a_0)$ tiene $n$ aristas salientes ponderadas hacia $(i + a_j) \text{ \% }a_0$ con peso $a_j$, para cada $j \in [0, n).$

#include <bits/stdc++.h>
using namespace std;
 
const int N = 5000;
const int K = 50000;
const int INF = 1e9;
 
int a[N], d[K], vis[K];  // se necesitan arreglos y E/S rápida por el límite de tiempo
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, k;
	cin >> n;
	for (int i = 0; i < n; i++) { cin >> a[i]; }
	// d[i] -> valor mínimo que podemos formar congruente con i (mod a[0])
	fill(d, d + a[0], INF);
	d[0] = 0;
	for (int i = 0; i < n; i++) {
		// observación importante: las aristas de un solo peso formarán varios
		// ciclos disjuntos
		for (int j = 0; j < a[0]; j++)
			if (vis[j] <= i) {
				// índice del valor mínimo d[j] en este ciclo
				int min_index = j;
				for (int k = j; k == j || (k - j) % a[0]; k += a[i]) {
					if (d[k % a[0]] < d[min_index]) { min_index = k % a[0]; }
				}
				for (int k = min_index; vis[k] <= i; k = (k + a[i]) % a[0]) {
					d[(k + a[i]) % a[0]] = min(d[(k + a[i]) % a[0]], d[k] + a[i]);
					++vis[k];
				}
			}
	}
 
	cin >> k;
	for (int i = 0; i < k; i++) {
		int x;
		cin >> x;
		cout << (d[x % a[0]] <= x ? "TAK" : "NIE") << '\n';
	}
}