Solutii la concursul acm 2013 etapa nationala partea a doua

Petru Trimbitas
21 iunie 2013

Revin cu partea a doua a articolului cu soluţii la problemele de la faza naţională a concursului ACM ICPC. Acestea sunt problemele grele şi au fost rezolvate de puţine echipe. Vă invit să discutaţi soluţiile la comentarii.

A. Cubic Eight-Puzzle

Problema ne dă un grid de 3×3 acoperit cu 8 cuburi fiecare aşezat într-una din celule. Fiecare are două dintre feţele opuse colorate cu albastru(B) iar celelalte două colorate cu alb(W) şi cu roşu( R ) . La o mutare poate fi rostogolit unul din cuburi în celula liberă. Problema ne cere să aflăm numărul minim de mutări necesare pentru a ajunge într-o configuraţie dată. Se ştie că iniţial cuburile sunt cu faţa albă in sus iar faţa albastră e în dreapta. Celula goală se află în stânga-jos. Dacă numărul de mutări e mai mare de 30 se va afişa -1

Soluţie oferită de •Adrian Budau

Ne vom folosi de Meet in the middle făcând un bfs, fiecare nod din graf fiind o stare a gridului, din starea iniţială şi din cea finală pană la distanţa 15. La fiecare pas avem 4 mutări posibile dintre care una ne va duce înapoi deci doar 3 ne interesează. Astfel vom trece prin 3 ¹⁵ stări.

B. Manhattan Wiring

În această problemă ni se dă o matrice de NxM ( N<=9 M<=9 ) cu unele celule ocupate. Două dintre celulele matricei sunt marcate cu 2 şi două cu 3. Trebuie afişată suma minimă a lungimii a două lanţuri care nu se intersectează care unesc cele două celule cu 2 şi cele două cu 3 fără a ieşi din matrice sau a trece prin celulele ocupate.

C. Power Calculus

Problema ne cere să aflăm numărul minim de operaţii pentru a calcula x ⁿ pornind de la x fără a folosi puteri negative. De exemplu x ³¹ poate fi calculat cu 6 operaţii (5 înmulţiri şi o împărţire) x ² = x × x, x ⁴ = x ² × x ², x ⁸ = x ⁴ × x ⁴ , x ¹⁶ = x ⁸ × x ⁸ , x ³² = x ¹⁶ × x ¹⁶ , x ³¹ = x ³² ÷ x

D. Polygons on the Grid

În această problemă trebuie să aflăm aria maximă a unui poligon cu colţurile în puncte laticeale care are lungimile laturilor date. Poligonul are maxim 6 laturi iar lungimea maximă a unei laturi e 300