$ cd preparacion/editoriales/clasificatoria-2026/zelma

La leyenda de Zelma

Cuatro fragmentos triangulares, tres uniones mágicas y un poder que calcular. El problema con el enunciado más largo esconde un secreto: el máximo no hace falta buscarlo.

Autor: Denilson Fiesta Inocente 100 puntos · 5 subtareas

// el problema

La historia, en corto

El héroe Enlace tiene que armar el Triángulo del Poder para sellar a Ganandor. En el pedestal hay un fragmento central, de cabeza, que no se puede sacar pero sí girar. Alrededor hay tres ranuras, A, B y C, donde Enlace pone sus tres fragmentos sueltos: puede elegir qué fragmento va en cada ranura y girarlos. Lo que no puede es voltearlos como en un espejo.

Cada fragmento tiene un número en cada punta. En las tres uniones internas se juntan tres puntas, y para que el triángulo funcione los tres números de cada unión deben ser iguales. El poder es la suma de las tres puntas de afuera (a + e + i). Hay que dar el poder máximo, o decir que es imposible.

abc A def B ghi C xyz centro
Cada fragmento suelto da sus valores en orden: abajo a la izquierda, arriba, abajo a la derecha. El central: abajo, arriba a la izquierda, arriba a la derecha. Las uniones son b = d = y, f = h = z y c = g = x.
Arma el Triángulo del Poder· gira e intercambia

Empieza con el ejemplo 1 del enunciado, todavía desarmado. Gira los fragmentos e intercámbialos hasta que los tres puntos de las uniones se pongan verdes. O deja que la computadora pruebe todo.

girar
intercambiar ranuras
fragmentos

// qué hay que programar

Una función con vectores

Tu función poder_maximo recibe los tres fragmentos sueltos (un vector de vectores) y el central, y devuelve el poder máximo o la constante IMPOSIBLE (que vale −1000000 y ya viene definida en zelma.h). El grader lee las cuatro líneas del archivo, llama a la función y escribe el número, o la palabra IMPOSIBLE.

archivo de prueba
8 3 10
5 15 3
20 5 8
5 3 8
grader (lo pone la OBI) lee la entrada y llama a poder_maximo({{8,3,10},{5,15,3},{20,5,8}}, {5,3,8})
tu función, en zelma.cpp int poder_maximo(std::vector<std::vector<int>> sueltos, std::vector<int> centro);
el grader escribe
45

Más sobre el grader en la página de inicio de las editoriales.

// la escalera de puntos

Probar de a poco, y después probar todo

Cada bloque es una subtarea, tan ancho como sus puntos. Tócalo para ir a su explicación.

La entrada son solo 12 números. Aquí no hace falta un algoritmo rápido: hace falta organizarse para probar todas las formas de armar el triángulo sin olvidar ninguna. Cada subtarea te deja probar solo una parte: las ranuras, las rotaciones, o ninguna de las dos.

Un enunciado largo asusta, pero no siempre es el problema más difícil.

Subtarea 1

Un centro con tres puntas iguales

+11 puntos

Las tres puntas del centro son iguales

Si el centro tiene las tres puntas iguales a v, las tres uniones necesitan el valor v. Cada fragmento suelto toca dos uniones con dos de sus puntas, y la tercera queda hacia afuera. Entonces:

  • cada fragmento necesita al menos dos puntas iguales a v; si alguno no las tiene, es imposible;
  • da igual en qué ranura va cada uno: lo giramos para que la punta que sobra quede hacia afuera;
  • el poder es la suma de las tres puntas que sobran: todo menos 2v por cada fragmento.

Pruébalo con el botón «Centro igual» de arriba.

zelma.cpp · subtarea 1 11 pts
#include "zelma.h"

#include <algorithm>
#include <vector>
using namespace std;

// Subtarea 1 (x = y = z = v): las tres uniones necesitan el valor v. Da igual
// en qué ranura va cada pieza: cada una necesita dos puntas iguales a v, y su
// tercera punta queda hacia afuera.
int poder_maximo(vector<vector<int>> sueltos, vector<int> centro) {
    int v = centro[0], poder = 0;
    for (auto &pieza : sueltos) {
        if (count(pieza.begin(), pieza.end(), v) < 2) return IMPOSIBLE;
        poder += pieza[0] + pieza[1] + pieza[2] - 2 * v;  // la punta que sobra
    }
    return poder;
}
Subtarea 2

Sin girar: probar las 6 formas de repartir

+16 puntos

Ningún fragmento necesita rotarse

Si nadie necesita girar, solo falta decidir qué fragmento va en cada ranura. Con tres fragmentos hay 3 × 2 × 1 = 6 formas. Las probamos todas y nos quedamos con el mejor poder.

Para recorrer las 6 formas, C++ tiene next_permutation: empieza con el orden 0 1 2 y en cada vuelta lo cambia al siguiente (0 2 1, 1 0 2, …) hasta agotarlos. La función valido revisa las tres uniones; la vamos a reusar en todas las subtareas siguientes.

zelma.cpp · subtarea 2 16 pts
#include "zelma.h"

#include <algorithm>
#include <vector>
using namespace std;

// ¿Las tres uniones tienen valores iguales? A, B y C son las piezas de las
// ranuras de abajo a la izquierda, de arriba y de abajo a la derecha; X es el centro.
bool valido(vector<int> A, vector<int> B, vector<int> C, vector<int> X) {
    bool izquierda = A[1] == B[0] && B[0] == X[1];
    bool derecha = B[2] == C[1] && C[1] == X[2];
    bool abajo = A[2] == C[0] && C[0] == X[0];
    return izquierda && derecha && abajo;
}

// Subtarea 2 (nadie necesita rotar): probamos las 6 formas de repartir las
// tres piezas en las tres ranuras.
int poder_maximo(vector<vector<int>> sueltos, vector<int> centro) {
    int mejor = IMPOSIBLE;
    vector<int> orden = {0, 1, 2};
    do {
        vector<int> A = sueltos[orden[0]], B = sueltos[orden[1]], C = sueltos[orden[2]];
        if (valido(A, B, C, centro)) mejor = max(mejor, A[0] + B[1] + C[2]);
    } while (next_permutation(orden.begin(), orden.end()));
    return mejor;
}
Subtarea 3

Sin cambiar de ranura: probar las rotaciones

+19 puntos

Si se puede, se puede sin cambiar de ranura

Ahora al revés: cada fragmento ya está en su ranura, pero hay que girarlos. Cada fragmento tiene 3 rotaciones, y el central también: 3 × 3 × 3 × 3 = 81 combinaciones. Cuatro for anidados las recorren. Girar es mover los valores en círculo: p q r pasa a r p q.

Aquí sí puede ser imposible. Por eso mejor empieza en IMPOSIBLE: si ninguna combinación sirve, eso es lo que devolvemos.

zelma.cpp · subtarea 3 19 pts
#include "zelma.h"

#include <algorithm>
#include <vector>
using namespace std;

// Gira una pieza k veces: p q r -> r p q -> q r p.
vector<int> rotar(vector<int> t, int k) {
    for (int i = 0; i < k; i++) t = {t[2], t[0], t[1]};
    return t;
}

bool valido(vector<int> A, vector<int> B, vector<int> C, vector<int> X) {
    bool izquierda = A[1] == B[0] && B[0] == X[1];
    bool derecha = B[2] == C[1] && C[1] == X[2];
    bool abajo = A[2] == C[0] && C[0] == X[0];
    return izquierda && derecha && abajo;
}

// Subtarea 3 (cada pieza ya está en su ranura): probamos las 3 rotaciones de
// cada pieza suelta y del centro: 3 * 3 * 3 * 3 = 81 ensamblajes.
int poder_maximo(vector<vector<int>> sueltos, vector<int> centro) {
    int mejor = IMPOSIBLE;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                for (int m = 0; m < 3; m++) {
                    vector<int> A = rotar(sueltos[0], i), B = rotar(sueltos[1], j);
                    vector<int> C = rotar(sueltos[2], k), X = rotar(centro, m);
                    if (valido(A, B, C, X)) mejor = max(mejor, A[0] + B[1] + C[2]);
                }
    return mejor;
}
Subtarea 4

El secreto: el poder siempre es el mismo

+21 puntos

Seguro que existe un ensamblaje válido

Mira un ensamblaje válido. En la unión izquierda, b y d valen y; en la derecha, f y h valen z; abajo, c y g valen x. O sea, las seis puntas de adentro suman 2(x + y + z), sin importar cómo se armó. Las tres de afuera son lo que sobra:

poder = (suma de las 9 puntas sueltas) − 2 × (x + y + z)

¡Todos los ensamblajes válidos tienen el mismo poder! Pedir «el máximo» era una distracción. Si sabes que existe al menos uno, la respuesta es esta fórmula y no hace falta armar nada. Compruébalo con el botón «Probar los 486 ensamblajes»: entre los válidos aparece un solo poder.

zelma.cpp · subtarea 4 21 pts
#include "zelma.h"

#include <vector>
using namespace std;

// Subtarea 4 (seguro que se puede armar): en cualquier ensamblaje válido, las
// seis puntas sueltas que tocan el centro valen x, y, z dos veces cada una.
// Las tres que sobran son el poder: la suma de todo menos 2 * (x + y + z).
int poder_maximo(vector<vector<int>> sueltos, vector<int> centro) {
    int total = 0;
    for (auto &pieza : sueltos)
        for (int valor : pieza) total += valor;
    return total - 2 * (centro[0] + centro[1] + centro[2]);
}
Subtarea 5

Probar todo

+33 puntos

Sin restricciones adicionales

Para el problema completo juntamos las subtareas 2 y 3: las 6 formas de repartir, por las 81 rotaciones. Son 6 × 81 = 486 ensamblajes, y una computadora los revisa en mucho menos de un milisegundo. Si ninguno es válido, devolvemos IMPOSIBLE.

zelma.cpp · solución completa 100 pts
#include "zelma.h"

#include <algorithm>
#include <vector>
using namespace std;

vector<int> rotar(vector<int> t, int k) {
    for (int i = 0; i < k; i++) t = {t[2], t[0], t[1]};
    return t;
}

bool valido(vector<int> A, vector<int> B, vector<int> C, vector<int> X) {
    bool izquierda = A[1] == B[0] && B[0] == X[1];
    bool derecha = B[2] == C[1] && C[1] == X[2];
    bool abajo = A[2] == C[0] && C[0] == X[0];
    return izquierda && derecha && abajo;
}

// Solución completa: probamos todo. 6 formas de repartir las piezas, 3 rotaciones
// de cada una y 3 del centro: 6 * 81 = 486 ensamblajes, nada para una computadora.
int poder_maximo(vector<vector<int>> sueltos, vector<int> centro) {
    int mejor = IMPOSIBLE;  // si nada es válido, queda IMPOSIBLE
    vector<int> orden = {0, 1, 2};
    do {
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                for (int k = 0; k < 3; k++)
                    for (int m = 0; m < 3; m++) {
                        vector<int> A = rotar(sueltos[orden[0]], i);
                        vector<int> B = rotar(sueltos[orden[1]], j);
                        vector<int> C = rotar(sueltos[orden[2]], k);
                        vector<int> X = rotar(centro, m);
                        if (valido(A, B, C, X)) mejor = max(mejor, A[0] + B[1] + C[2]);
                    }
    } while (next_permutation(orden.begin(), orden.end()));
    return mejor;
}

// para la próxima

Errores comunes

  • Empezar el máximo en 0. El poder puede ser negativo (las puntas van de −1000 a 1000), y entonces nunca se actualiza. Empieza en IMPOSIBLE.
  • Voltear los fragmentos (invertir el orden de sus puntas). El enunciado no lo permite, y así aparecen ensamblajes que no existen.
  • Llenar las ranuras con el primer fragmento que encaje. Puede gastar un fragmento que otra ranura necesitaba: hay que probar todas las combinaciones.
  • Olvidar comparar con el centro y revisar solo que los fragmentos sueltos coincidan entre ellos.