Un sumator pe un bit este un mic dispozitiv cu 3 intrări şi 2 ieşiri. El primeşte la intrare X1, X2 şi Ti. X1 şi X2 sunt biţii ce trebuie adunaţi, iar Ti este transportul anterior (ca intrare). La ieşire furnizează Y şi To. Y este suma, iar To este transportul următor (ca ieşire).
Pentru a formaliza aceste lucruri putem scrie Y = (X1 + X2 + Ti) mod 2 (mod este restul împărţirii întregi) To = (X1 + X2 + Ti) div 2 (div este câtul împărţirii întregi)
Pentru a aduna numere pe N biţi se folosesc N astfel de sumatoare. Ele sunt legate ca în figura de mai jos, adică transportul de ieşire al unui sumator este transportul de intrare pentru următorul.
Problema cu aceste sumatoare pe mai multi biţi este că un sumator trebuie să aştepte transportul de la unitatea anterioară (exceptând primul sumator).
Dacă unui sumator pe un bit face calculul într-o secundă, atunci pentru un sumator pe N biţi (format din N sumatoare pe un bit) vor fi necesare N secunde.
Pentru a îmbunătăţi performanţa acestor sumatoare pe N biţi s-au introdus nişte unităţi capabile să anticipeze transportul, adică intrarea Ti. Aceste unităţi verifică datele de intrare precedente X1(i-1) şi X2(i-1). Dacă amândouă sunt 0 atunci Ti va fi 0, indiferent de ce primeşte acea unitate ca transport de intrare. De asemenea dacă amândouă sunt 1 atunci Ti va fi 1. Toate sumatoarele care folosind anticipaţia pot calcula transportul de la sumatorul precedent încep calculul odată cu primul sumator. Comunicarea transportului de la un sumator la următorul se realizează instantaneu.
Cercetătorii care au inventat aceste unităţi de transport vor să ştie cu cât îmbunătăţesc performanţa sistemului şi au hotărât să se facă toate adunările posibile, pentru a compara cu vechiul sistem. Prin toate adunările posibile se înţelege că se va aduna orice număr pe N biţi cu orice număr pe N biţi fix o dată (în total 4N adunări). Ei vor să ştie cât au durat aceste operaţii, adică suma tuturor timpilor pentru fiecare adunare.
Cerinţă
Scrieţi un program care să determine numărul total de secunde necesare pentru toate adunările, folosind dispozitivele de anticipare.
Date de intrare
Fişierul de intrare anticip.in conţine o singură linie pe care se află numărul natural N reprezentând numărul de biţi.
Date de ieşire
Fişierul de ieşire anticip.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul de secunde necesare tuturor adunărilor posibile.
Restricţii
0 < N < 51
Problema aceasta nu are nici o legătură cu vreun balaur.
Exemple
anticip.in
anticip.out
Explicaţii
3
128
16 adunări se realizează într-o secundă; 32 adunări se realizează în două secunde; 16 adunări se realizează în trei secunde.
De exemplu, adunarea 010+001 necesită 3 secunde. Adunarea 010+000 necesită 2 secunde. Adunarea 010+110 necesită o secundă (primul sumator adună biţii din dreapta).
