*Soluţie* oferită de ==user(user="freak93")==
Ne vom folosi de 'Meet in the middle':blog/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 ^ 15 ^$ stări.
O primă soluţie ar fi să facem o parcurgere în lăţime din starea iniţială făcând maxim 30 mutări. La fiecare pas avem $4$ mutări posibile dintre care una ne va duce înapoi deci doar $3$ ne interesează. În total vom trece prin $3 ^ 30 ^$ stări.
Pentru a reduce numărul de stări prin care trecem vom folosi 'Meet in the middle':blog/meet-in-the-middle. În loc să pornim o parcurgere doar din sursă, vom porni una şi din destinaţie şi făcând maxim 15 mutări. Astfel vom încerca să întâlnim din sursă un nod vizitat din destinaţie sau invers. Astfel vom vizita doar $2*3 ^ 15 ^$ stări.
h2. 'B. Manhattan Wiring':http://acm.tju.edu.cn/toj/vcontest/showp9268_B.html
Î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.
Î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ă şi unesc cele două celule cu $2$ şi cele două cu $3$ fără a ieşi din matrice sau a trece prin celulele ocupate.
Recomand citirea 'acestui':http://apps.topcoder.com/forums/?module=Thread&threadID=697369&start=0&mc=22 articol înainte de citirea soluţiei.
O 'problemă':http://www.hsin.hr/ceoi2006/tasks/day2/connect.pdf asemănătoare s-a dat la CEOI 2006. Soluţia ei se găseşte 'aici':http://www.hsin.hr/ceoi2006/tasks/solutions.pdf
*Soluţie*
Se poate observa că fiecare celulă poate fi în următoarele stări: goală, ocupată cu un cablu vertical/orizontal sau cu un cablu în L(4 stări). Se poate observa de asemenea că fiecare secvenţă continuă de fire de pe fiecare linie şi coloană va conţine maxim două L-uri. Altfel am putea scurta lungimea cablului cu 2.
În scrierea soluţiei m-am inspirat de 'aici':http://f0rth3r3c0rd.wordpress.com/2013/04/25/uva-1214-manhattan-wiring/
Fiecare celulă poate fi în următoarele stări: goală, ocupată cu un cablu vertical/orizontal sau cu un cablu în L(4 stări). Vom calcula lungimea minima a cablurilor poziţionate până la linia $i$ iar cele din $stare$ sunt legate de linia anterioară( $0$ nu există legătură, $1$ există legătură iar cablul va fi legat de $2$, $2$ există legătură iar cablul va fi legat de $3$). Pentru a calcula tanziţiile vom genera cu backtracking starea cablurilor de pe coloana următoare şi vom avea grijă să păstrăm următoarea $stare$ corectă.
h2. 'C. Power Calculus':http://acm.tju.edu.cn/toj/vcontest/showp9268_C.html
Problema ne cere să aflăm numărul minim de operaţii pentru a calcula $x ^n^$ pornind de la $x$ fără a folosi puteri negative şi făcând înmulţiri cu numere calculate deja. De exemplu $x ^31^$ poate fi calculat cu $7$ înmulţiri:
Problema ne cere să aflăm numărul minim de operaţii pentru a calcula $x ^n^$ ( $n <= 1000$ ) pornind de la $x$ fără a folosi puteri negative şi făcând înmulţiri cu numere calculate deja. De exemplu $x ^31^$ poate fi calculat cu $7$ înmulţiri:
$x ^2^ = x × x, x ^4^ = x ^2^ × x ^2^, x ^8^ = x ^4^ × x ^4^ , x ^10^ = x ^8^ × x ^2^ , x ^20^ = x ^10^ × x ^10^, x ^30^ = x ^20^ × x ^10^ , x ^31^ = x ^30^ × x$
Acesta poate fi calculat şi cu $6$ operaţii (5 înmulţiri şi o împărţire)
$x ^2^ = x × x, x ^4^ = x ^2^ × x ^2^, x ^8^ = x ^4^ × x ^4^ , x ^16^ = x ^8^ × x ^8^ , x ^32^ = x ^16^ × x ^16^ , x ^31^ = x ^32^ ÷ x$
*Soluţie*
Deşi iniţial pare complicată, problema se rezolvă cu o parcurgere în lăţime. Se observă că nu are sens să calculăm pentru numere mai mari de $2000$. Într-o poziţie din coadă vom reţine toate numerele folosite până la numărul curent. Când dorim să trecem într-o stare nouă trebuie doar să aplicăm operaţiile asupra ultimului număr şi al unui număr calculat pe parcurs.
Deşi iniţial pare complicată, problema se rezolvă cu o parcurgere în lăţime. Se observă că nu are sens să calculăm pentru numere mai mari de $2000$. Într-o poziţie din coadă vom reţine toate puterile calculate până la numărul curent. Când dorim să trecem într-o stare nouă trebuie doar să adunăm sau să scădem ultima putere calculată cu una calculată anterior.
==code(cpp) |
#include <iostream>
*Soluţie* oferită de ==user(user="mugurelionut")==
Ideea soluţiei este încercarea tuturor variantelor: se poate fixa o latură ca fiind prima şi îi încercăm toate orientările spre "dreapta-sus": orizontal, vertical, si, eventual, "oblic" dacă se poate aşeza cu capetele într-un punct întreg). Pe urmă variem ordinea celorlalte laturi ( $5!$ ) şi pentru fiecare dintre celelalte laturi încercăm orientările posibile care pastrează convexitatea poligonului. În plus mai trebuie folosită următoarea optimizare: Fixăm cea mai mare lungime ca fiind prima latură. Dacă lungimile rămase nu ne ajung să "închidem" poligonul atunci ne oprim.
Ideea soluţiei este încercarea tuturor variantelor: se poate fixa o latură ca fiind prima şi îi încercăm toate orientările spre "dreapta-sus": orizontal, vertical, si, eventual, "oblic" dacă se poate aşeza cu capetele într-un punct întreg). Pe urmă variem ordinea celorlalte laturi ( $5!$ ) şi pentru fiecare dintre celelalte laturi încercăm orientările posibile care pastrează convexitatea poligonului. În plus mai trebuie folosită următoarea optimizare: Fixăm cea mai mare lungime ca fiind prima latură. Dacă lungimile rămase nu ne ajung să "închidem" poligonul atunci ne oprim.
