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 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