NézetNyomtat

Elegáns gyémántok
Címkék > Feladat

Elegáns gyémántok

Forrás: Google Code Jam
A király felbérelt, hogy készíts neki egy elegáns gyémántot. Az elegáns gyémánt olyan kétdimenziós objektum, ami számjegyekből áll, és szimmetrikus egy függőleges és egy vízszintes tengelyre. Például a következők elegáns gyémántok:
   2       8      3     7
  3 3     8 8    2 2
 4 1 4     8      3
  3 3 
   2
Ezek gyémántok, de egyik sem elegáns:
  2       1        3
 1 1     1 2      1 1
  1     1 1 1    3 1 3
         2 1      1 1
          1        2
Ezek nem gyémántok:
  1     2     8   8
 1 1   222      0
        2     00000
Kapsz a királytól egy gyémántot, ami nem feltétlenül elegáns. Az a dolgod, hogy bővítsd elegáns gyémánttá, számjegyek hozzáadásával. Arra is ügyelned kell, hogy a lehető legolcsóbb bővítést találd meg.

Definíciók

A k méretű gyémánt 2k-1 sorból áll, mindegyik sor számjegyek szóközökkel elválasztott sorozata az alábbi módon:
  • Az i. sor (1 ≤ i ≤ k) k-i szóközzel kezdődik, majd i számjegy következik,egy-egy szóközzel elválasztva.
  • Az i. sor (k < i < 2k) i-k szóközzel kezdődik, majd 2k-i számjegy következik,egy-egy szóközzel elválasztva.
A k méretű elegáns gyémánt egy olyan k méretű gyémánt, amelyre a következők teljesülnek:
  • Vízszintes szimmetria: Ha az i. sorban ci számjegy van, akkor az i. sor j. eleme (1-től kezdve a számozást) egyenlő a ci+1-j. elemmel.
  • Függőleges szimmetria: Az i. sor j. eleme egyenlő a (2k-i). sor j. elemével.
A k méretű gyémánt bővítése számjegyek hozzáadásával történik. A bővített gyémánt is gyémánt, és tartalmazza az eredeti alakzatot.
A bővítés költsége a hozzáadott számjegyek száma.

Bemenet

Az első sor a tesztesetek számát adja meg. Minden teszteset a gyémánt k méretével kezdődik (1 ≤ k ≤ 51) , majd utána a gyémánt leírása következik, a fenti definíció szerint.

Kimenet

Minden tesztesetre meg kell adni a legolcsóbb bővítés költségét. Ha az eredeti gyémánt elegáns, akkor a bővítés költsége 0.

Példa

Input Output
4
1
0
2
 1
2 2
 1
2
 1
1 2
 1
3
  1
 6 3
9 5 5
 6 3
  1
Case #1: 0
Case #2: 0
Case #3: 5
Case #4: 7

Tesztadatok

Kicsi

Nagy