|
Titlul: 3069. Bridged Marble Rings Scris de: Vlad Dumitriu din Septembrie 09, 2008, 10:52:20 careva vreo idee la: 3069. Bridged Marble Rings? (http://acm.tju.edu.cn/toj/showp3069.html)
io am facut pe bitzi, BFS cu queue si restu am retzinut in map prin ce stari am fost. si in plus fiecare stare o rotesc astfel incat sa fie minima lexicografic (asta ca sa nu repet multe configuratii.. care defapt is niste rotatii). si nu iese (TLE normal). careva vreo idee? un hint ceva? link: http://acm.tju.edu.cn/toj/showp3069.html (http://acm.tju.edu.cn/toj/showp3069.html) Titlul: Răspuns: 3069. Bridged Marble Rings Scris de: dragus marius din Octombrie 18, 2008, 11:20:28 La problema asta trebuie doar sa te gandesti cum reduci numarul de stari ca dupa aia e clar ca poti face un bfs si ai facut treaba,nu? Adica numarul de stari posibile sunt combinari de 26 luate cate 13 impartit la 13(le rotesti pe fiecare de 13 ori si le scoti pe alea identice) care iti da vreo 800.000, asta e o exagerare, adica limita adevarata e vreo 50.000(Fiindca sunt foarte multe care sunt iarasi identice). Acum singura chestie e sa iti dai seama cum renumerotezi starile astea....
Atentie urmatoarea linie e un pic de spoiler, doar pentru oamenii care vreau sa vada exact solutia: Si ca hint in legatura cu asta iti zic doar incearca sa gasesti o rotatie care sa fie identica pentru toate starile identice. |