Distanciament aviar (pendent de revisar) X68155

En un arbre hi viuen 2ⁿ − 1 ocells, cadascun en el seu niu. Numerem els ocells de 1 a 2ⁿ − 1. El niu que està més avall és el de l’ocell 1, i està just on el tronc es bifurca en dos. A partir d’aquí, anant cap amunt, cada branca es va bifurcant en dos. A cada bifurcació, un ocell té un niu. A més, per a cada ocell i amb 1 ≤ i ≤ 2ⁿ⁻¹ − 1, els dos nius que té a sobre, seguint les dues subbranques, són els dels ocells 2i i 2i+1. Així, l’únic ocell que està a altura 1 és l’ocell 1, els que estan a altura 2 són els ocells 2 i 3, els que estan a altura 3 són els ocells 4, 5, 6, 7, i així succesivament fins a altura n.

L’ocell 1 ha contret una malaltia molt contagiosa. Si un ocell i agafa la malaltia, la transmetrà als dos ocells de sobre (excepte si i està a altura màxima). Alguns dels ocells, espantats, marxen del seu niu. Gràcies a això, no agafen la malaltia i la malaltia no es propaga als ocells de sobre.

Nota: Aquest problema està pendent de revisar

Entrada

L’entrada comença amb un enter n, indicant que hi ha 2ⁿ − 1 ocells, i un enter m, el nombre d’ocells que fugen. A continuació venen m nombres diferents a₁, a₂ … a_m, els ocells que fugen. Direm que un ocell x és inferior a un ocell y si per anar del niu de l’ocell y al de l’ocell 1 seguint les branques, cal passar pel niu de l’ocell x. Se’t garantitza que a_i no és inferior a a_j per a cap parell (i, j) amb i ≠ j.

Sortida

Escriviu un enter: el nombre d’ocells que agafen la malaltia.

Puntuació

• 200 punts: Casos amb n ≤ 16
• 400 punts: Casos amb n ≤ 29, m ≤ 10⁵