Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | hansha.in, hansha.out | Sursă | Algoritmiada 2017 Runda 2 |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Hansha
Dupa numeroasele probleme cu palindromuri pe care le-a compus Dani, colegii sai de echipa i-au spus sa-si mai improspateze ideile, fiindca toata lumea s-a plictisit de ele. Dani a fost de-acord, dar n-a renuntat la pasiunea sa mai generala pentru simetrie. De aceasta data, el s-a inspirat din istoria imperiului antic Hansha, a carui dezvoltare i s-a parut foarte interesanta. Initial, imperiul Hansha era constituit dintr-un singur oras, iar acesta avea un numar pe post de nume: numarul 1. Apoi, in fiecare secol, timp de K secole, imperiul s-a dezvoltat astfel: Numarul sau de orase s-a dublat, iar daca orasele sale erau numerotate pana acum cu valori de la 1 la N, noile orase vor lua drept nume valorile N + 1, N + 2... 2 * N. Mai mult, aceste N noi orase vor avea exact aceeasi structura de drumuri ca orasele initiale. Mai exact, va exista drum intre orasul N + i si orasul N + j, unde 1 ≤ i, j ≤ N daca si numai daca exista deja un drum intre orasele i si j. Astfel, se poate spune ca in acest moment al fazei de dezoltare, imperiul s-a "oglindit", formand doua copii identice. Pentru a conecta aceste copii, se va mai construi un singur nou drum care va conecta un oras duplicat de corespondentul sau. Mai exact, pentru un unic 1 ≤ x &le N, se va adauga un drum intre nodurile x si N + x. Acest x poate varia de la o faza de dezvoltare la alta.
Dani are in fata mai multe scenarii posibile ale dezvoltarii imperiului Hansha. Un scenariu este definit printr-un numar K, care reprezinta numarul de faze de dezvoltare si descrierea celor K valori x, numerele oraselor care vor fi conectate cu duplicatul lor la fiecare dintre cele K faze ale dezvoltarii. Pentru fiecare scenariu, Dani va intreaba care este numarul minim de drumuri pe care trebuie sa-l parcurga pentru a ajunge din orasul A in orasul B dupa ce s-au finalizat toate etapele de dezvoltare in scenariul respectiv.
Date de intrare
Fişierul de intrare hansha.in ...
Date de ieşire
În fişierul de ieşire hansha.out ...
Restricţii
- 1 ≤ T ≤ 1.000
- 1 ≤ K ≤ 30
- Pentru 40 de puncte 1 ≤ K ≤ 10
Exemplu
| hansha.in | hansha.out |
|---|---|
| 3 4 1 2 3 4 1 16 4 1 2 4 7 2 13 5 1 2 4 6 10 3 30 | 6 7 11 |
