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 |
