B - PermutácieČasový limit: 20s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3Počet bodov: 2 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] ÚlohaDané sú dve slová rovnakej dĺžky N a zoznam P permutácií. Úlohou je zistiť, či sa prvé slovo dá premeniť na druhé použitím daných permutácií na nanajvýš L krokov (pričom jeden krok je použitie jednej permutácie). Každá permutácia sa môže použiť ľubovoľný počet krát a permutácie sa môžu použiť v ľubovoľnom poradí. V prípade, že sa to dá, je potrebné nájsť minimálny počet krokov. Permutácie sú zapísané pomocou prvých N znakov malej anglickej abecedy (sú rovnako dlhé ako vstupné slová). Pod použitím permutácie na slovo sa myslí preusporiadanie písmen v danom slove podľa písmen danej permutácie. Na miesto písmena 'a' pôjde prvé písmeno pôvodného slova, na miesto písmena 'b' pôjde druhé písmeno, atď. Napríklad použitím permutácie cbdae na slovo PALMA dostaneme slovo LAMPA. VstupPrvý riadok vstupu obsahuje počet testovacích sád T (1≤T≤30). Prvý riadok každej testovacej sady obsahuje tri celé čísla oddelené medzerou: N, P a L (1≤N≤26, 1≤P;≤10, 1≤L≤10). Druhý riadok obsahuje dve slová dĺžky N, oddelené medzerou. Slová sa skladajú len z písmen veľkej anglickej abecedy ('A' až 'Z'). Ďalej obsahuje P riadkov, ktoré obsahujú povolené permutácie.VýstupPre každú testovaciu sadu by výstup mal obsahovať jediný riadok a na ňom jediné číslo: minimálny počet krokov v ktorých sa prvé slovo dá premeniť na druhé, alebo -1 ak sa to nedá, alebo je na to potrebných viac ako L krokov.PríkladVstup2 5 1 1 PALMA LAMPA cbdae 5 2 4 ABCDE DCEAB bcdea bacde Výstup1 3Príklad prevzatý z IDI Open 2007. |