Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Még az előző években a kizáró vagy nagy maffiavezérről, Ocram Civasról szóló filmduológia nagy népszerűségre tett szert, és sokan megkedvelték. Mint a neve is mondja, a duológia két részből állt, melyek az Ocram és Civas nevet viselik. Azonban az első két rész hatalmas népszerűsége miatt, megkezdték a „Sdneirf” nevet viselő harmadik és egyben utolsó rész forgatását is. Ebben a részben Ocram Civas már régen kilépett a maffiából, és boldogságban él családjával. Ám ekkor érkezik egy felkérés az utolsó feladatra…
Hősünk utolsó kalandjában az elsőhöz hasonlóan (mivel az ilyen filmekben fontos a nosztalgia) egy \(N\times M\) méretű titokzatos mátrixban találja magát. A mátrix minden mezőjében egy nemnegatív egész szám szerepel, pontosabban az \(i\)-dik sor és a \(j\)-dik oszlop metszetében található mezőben az \(a_{i,j}\) kezdőérték szerepel. Miután Ocram Civas felocsúdott, rájött, hogy csak egy módon tudja megváltoztatni ennek a mátrixnak az értékeit. Minden lépésben ki tudja választani az \(X\) nemnegatív egész számot, és egy sorozatot az \(N+M-1\) mező közül, amely a bal felső sarokban található mezővel kezdődik, és a jobb alsó sarokban végződik úgy, hogy minden két szomszédos mezőnek van közös oldala ebben a sorozatban, és akkor ezen az úton minden mező az alábbi módon változtatja meg a benne található számot: ha ezen tevékenység előtt a mezőben \(Y\) szám állt, akkor ebben a mezőben az új érték \(Y\text{ xor }X\) lesz.
Már jól tudjuk, hogy Ocram Civas a kizáró vagy nagymestere, és azt a feladatot tűzte ki magának, hogy meghatározza: tetszőleges számú lépést követően mennyi lesz a mátrixban található értékek összegének minimális értéke. Ha sikerül csökkentenie az összeg értékét, akkor úgy néz ki, hogy el tudja hagyni a mátrixot, és végérvényesen maga mögött tudja hagyni a bűnözés világát.
A szabványos bemenet első sora az \(N\) (sorok száma) és \(M\) (oszlopok száma) két egész számot tartalmazza. A következő \(N\) sor mindegyike \(M\) egész számot tartalmaz, ahol a \(j\)-dik szám az \((i+1)\)-dik sorban az \(a_{ij}\) számot képviseli, amely az \(i\)-dik sorban és a \(j\)-dik oszlopban található mező kezdőértékét jelöli.
A szabványos kimenet egyetlen sorában egy egész számot kell kiíratni: a mátrixban található értékek összegének minimális értékét a műveletek elvégzését követően.
1 2
1 01A kezdőösszeg értéke egy. Ez a legkisebb érték, mivel az összeg pozitív a lépések elvégzését követően.
2 3
2 7 5
5 7 20Ocram Civas az első lépésben veheti az \(X=7\)-et és az alábbi mezőket: \((1,1),\) \((1,2),\) \((2,2),\) \((2,3)\), és akkor \(X=5\)-tel végrehajt \(3\) lépést, először az \((1,1),\) \((2,1),\) \((2,2),\) \((2,3)\) mezőkkel, majd az \((1,1),\) \((1,2),\) \((1,3),\) \((2,3)\) mezőkkel, majd végül az \((1,1),\) \((1,2),\) \((2,2),\) \((2,3)\) mezőkkel. ## Korlátozások - \(1 \leq N,M \leq 1.500\) - \(0\leq A_{ij}\leq 1.000.000.000\)
A tesztpéldák öt diszjunkt csoportba vannak sorolva:
A kizáró vagy jelölésére Pascalban a xor-t használják,
míg C++-ban a ^ szimbólummal írjuk le. Az \(x\ \text{xor} \ y\) műveletet az \(x,y\) nemnegatív számok esetén a
folytatásban leírt módon definiálhatjuk. Először a számokat bináris
formában kell felírni. Ha egy szám rövidebb, mint a másik, akkor azt
vezető nullákkal kell kiegészíteni mindaddig, amig a bináris számjegyek
száma nem lesz megegyező. Így a bináris számok két sorozatát kapjuk,
amelyekre \(a_1, \ldots, a_k\) és \(b_1, \ldots b_k\) jelölést használjuk. Majd
minden \(i \in {1, \ldots, k }\)
pozícióra kiszámoljuk a \(c_i\)-t az
alábbi szabályok mentén:
A \(c_1, \ldots, c_k\) bináris számjegyekből alkotott sorozat (amely tartalmazhat vezető nullákat is) az eredmény bináris leírása, vagyis az \(x \ \text{xor} \ y\) számé.
Ha szeretnétek megismerni Ocram Civas előző kalandjait, a verseny után megtekinthetitek az előző évi körzeti verseny feladatsorában a B kategória harmadik feladatát: Ocramot, valamint az előző évi körzeti verseny feladatsorában az A kategória második feladatát: Civast.