Considerăm pentru un număr natural n şirul tuturor numerelor naturale cuprinse între 1 şi 2n - 2, numerele fiind într-o ordine oarecare. Un astfel de şir pentru n=3 este format din numerele de la 1 la 6, de exemplu 3, 1, 5, 4, 6, 2. Reprezentăm fiecare număr din şir pe n biţi, scriind biţii pe verticală. Mai jos este scris sub fiecare număr din şir reprezentarea sa în baza 2:
3 1 5 4 6 2
0 0 1 1 1 0
1 0 0 0 1 1
1 1 1 0 0 0
Se obţine astfel o matrice binară cu n linii şi 2n - 2 coloane (în cazul de mai sus, cu 3 linii şi 6 coloane). Se observă că plecând de la bitul 0 de pe prima coloană şi mergând doar pe valori de 0 învecinate pe linii şi coloane (nu şi diagonale), se poate ajunge pe un 0 de pe ultima coloană. Un astfel de şir îl numim accesibil. Sunt mai multe astfel de şiruri accesibile. Pentru n = 3 şirurile 2, 3, 1, 5, 4, 6 şi 2, 6, 4, 5, 1, 3 sunt de asemenea accesibile. Dintre acestea îl alegem pe cel minim din punct de vedere lexicografic.
Cerinţă
Pentru că şirul accesibil minim lexicografic poate fi foarte lung, nu trebuie să-l determinaţi, ci să scrieţi un program care pentru o valoare dată a lui n şi pentru patru numere naturale x1, x2, x3, x4 cuprinse între 1 şi 2n - 2, determină poziţia acestora în şirul accesibil minim lexicografic.
Date de intrare
Fişierul de intrare accesibil.in
conţine pe prima linie numărul natural n, iar pe următoarele 4 linii câte un număr natural: pe linia 2 se află numărul x1, pe linia 3 este numărul x2, pe linia 4 numărul x3, iar pe ultima linie numărul x4.
Date de ieşire
Fişierul de ieşire accesibil.out
conţine patru linii, pe fiecare linie aflându-se un singur număr. Linia i conţine un număr natural reprezentând poziţia numărului xi în şirul accesibil minim lexicografic.
Restricţii
3 <= n <= 1 000
1 <= x1, x2, x3, x4 <= 2n - 2
Poziţiile în şir se numerotează de la 1 la 2n - 2
Spunem că şirul a1, a2, ..., ak este mai mic lexicografic decât b1, b2, ..., bk dacă există o poziţie p, 1 <= p <= k, astfel încât a1=b1, a2=b2, ..., ap-1=bp-1 şi ap <bp.