Al analizar el patrón de cambio de posición, observamos que sigue la secuencia -1, 2, -3, 4, ..., por lo que solo necesitamos determinar la paridad de n para resolver el problema.
#include <bits>
using namespace std;
int main() {
int casos;
cin >> casos;
while (casos--) {
int num;
cin >> num;
if (num % 2 == 1) {
cout << "Kosuke" << endl;
} else {
cout << "Sakurako" << endl;
}
}
return 0;
}
</bits>
Problema B
Para maximizar las operaciones seleccionadas, podemos extender las diagonales tanto como sea posible. La estrategia consiste en encontrar el valor mínimo en cada diagonal. La diagonal para una posición (i,j) puede identificarse con i-j, y como puede ser negativo, añadimos un desplazamiento.
#include <bits>
using namespace std;
const int MAX = 505;
int matriz[MAX][MAX];
int diagonal[MAX * 2];
int main() {
int tamano;
cin >> tamano;
memset(diagonal, 63, sizeof(diagonal));
for (int i = 1; i <= tamano; i++) {
for (int j = 1; j <= tamano; j++) {
cin >> matriz[i][j];
diagonal[i - j + MAX] = min(diagonal[i - j + MAX], matriz[i][j]);
}
}
long long resultado = 0;
for (int i = 0; i < MAX * 2; i++) {
resultado -= diagonal[i];
}
cout << resultado << endl;
return 0;
}
</bits>
Problema C
Este prolbema se resolvió con programación dinámica. Definimos dp[i][0/1] como la contribución mínima considerando los primeros i elementos, sin intercambiar o intercambiando el elemento i con el elemento n-i+1. Cada estado solo depende del anterior, lo que simplifica las transiciones.
#include <bits>
using namespace std;
const int MAX = 100005;
int n;
int valores[MAX];
int dp[MAX][2];
int main() {
int casos;
cin >> casos;
while (casos--) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> valores[i];
}
for (int i = 1; i <= n; i++) {
dp[i][0] = dp[i][1] = 0;
}
if (n % 2 == 1) {
int medio = n / 2 + 1;
if (valores[medio] == valores[medio + 1]) dp[medio + 1][0]++;
if (valores[medio] == valores[medio - 1]) dp[medio + 1][0]++;
dp[medio + 1][1] = dp[medio + 1][0];
for (int i = medio + 2; i <= n; i++) {
dp[i][0] = min(dp[i-1][0] + (valores[i] == valores[i-1]) + (valores[n-i+1] == valores[n-(i-1)+1]),
dp[i-1][1] + (valores[i] == valores[n-(i-1)+1]) + (valores[n-i+1] == valores[i-1]));
dp[i][1] = min(dp[i-1][0] + (valores[n-i+1] == valores[i-1]) + (valores[i] == valores[n-(i-1)+1]),
dp[i-1][1] + (valores[n-i+1] == valores[n-(i-1)+1]) + (valores[i] == valores[i-1]));
}
} else {
int medio = n / 2 + 1;
if (valores[medio] == valores[medio - 1]) dp[medio][0] = dp[medio][1] = 1;
for (int i = medio + 1; i <= n; i++) {
dp[i][0] = min(dp[i-1][0] + (valores[i] == valores[i-1]) + (valores[n-i+1] == valores[n-(i-1)+1]),
dp[i-1][1] + (valores[i] == valores[n-(i-1)+1]) + (valores[n-i+1] == valores[i-1]));
dp[i][1] = min(dp[i-1][0] + (valores[n-i+1] == valores[i-1]) + (valores[i] == valores[n-(i-1)+1]),
dp[i-1][1] + (valores[n-i+1] == valores[n-(i-1)+1]) + (valores[i] == valores[i-1]));
}
}
cout << min(dp[n][0], dp[n][1]) << endl;
}
return 0;
}
</bits>
Problema D
Para identificar intervalos "hermosos", podemos utilizar sumas prefijas. Si definimos un array de sumas prefijas b, cuando b_i = b_j, el intervalo [i+1, j] es hermoso. El problema se reduce a seleccionar el máximo número de intervalos no superpuestos, lo cual es un problema clásico de greedy. La estrategia es ordenar los intervalos por su extremo derecho y seleccionar aquellos que no se superpongan con el último seleccionado.
#include <bits>
using namespace std;
const int MAX = 100005;
long long n;
long long numeros[MAX];
long long sumas[MAX];
int main() {
int casos;
cin >> casos;
while (casos--) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> numeros[i];
sumas[i] = sumas[i-1] + numeros[i];
}
map<long long=""> indiceUltimo;
long long resultado = 0;
long long ultimoFin = -1;
indiceUltimo[0] = 0;
for (int i = 1; i <= n; i++) {
if (indiceUltimo.count(sumas[i])) {
if (indiceUltimo[sumas[i]] > ultimoFin) {
resultado++;
ultimoFin = i;
}
}
indiceUltimo[sumas[i]] = i + 1;
}
cout << resultado << endl;
}
return 0;
}
</long></bits>
Problema E
Este problema involucra permutaciones y ciclos. Al conectar cada elemento i con p_i, obtenemos una estructura de ciclos. La solución requiere que cada ciclo tenga un tamaño de como máximo 2. La estrategia óptima es realizar operaciones que reduzcan el tamaño de los ciclos. Para un ciclo de tamaño x, se requieren (x-1)/2 operaciones para reducirlo a ciclos de tamaño 1 o 2.
#include <bits>
using namespace std;
const int MAX = 1000005;
int n;
int permutacion[MAX];
int padre[MAX];
int tamano[MAX];
bool visitado[MAX];
int encontrar(int x) {
if (padre[x] == x) return x;
return padre[x] = encontrar(padre[x]);
}
void unir(int x, int y) {
x = encontrar(x);
y = encontrar(y);
if (x != y) {
tamano[x] += tamano[y];
padre[y] = x;
}
}
int main() {
int casos;
cin >> casos;
while (casos--) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> permutacion[i];
padre[i] = i;
tamano[i] = 1;
visitado[i] = false;
}
for (int i = 1; i <= n; i++) {
unir(i, permutacion[i]);
}
int operaciones = 0;
for (int i = 1; i <= n; i++) {
int raiz = encontrar(i);
if (!visitado[raiz]) {
operaciones += (tamano[raiz] - 1) / 2;
visitado[raiz] = true;
}
}
cout << operaciones << endl;
}
return 0;
}
</bits>
Problema F
Al analizar la secuencia de Fibonacci módulo k, observamos que se forma un patrón periódico. La solución consiste en encontrar la primera posición donde el valor de Fibonacci módulo k es 0. Una vez encontrado este índice, el resultado es n multiplicado por este índice.
#include <bits>
using namespace std;
const int MOD = 1000000007;
long long n, k;
long long fibo[1000005];
int main() {
int casos;
cin >> casos;
while (casos--) {
cin >> n >> k;
fibo[1] = fibo[2] = 1;
long long posicion, i = 3;
while (true) {
fibo[i] = (fibo[i-1] + fibo[i-2]) % k;
if (fibo[i] == 0) {
posicion = i;
break;
}
i++;
}
if (k == 1) posicion = 1;
cout << (n % MOD) * (posicion % MOD) % MOD << endl;
}
return 0;
}
</bits>