Lista de probleme 3

Filtrare

#2621 spower2

Un număr natural M se numește număr spower2 dacă poate fi descompus astfel: M=2x+2y, cu x≠y. Exemplu: 6 este un număr spower2 (6=2+4), pe când 8 nu este.

Cerința

Se consideră un șir A de n numere naturale. Pentru fiecare element al șirului Ai să se determine cel mai apropiat număr spower2 mai mare sau egal cu Ai, unde 1≤i≤n.

După ce Le. Quack a avut mare succes cu noul lui joc de cărți a decis să se apuce de scamatorii, pentru ca este pasionat de cărți îi cere patronului N cărți. Acesta așează toate cărțile pe față și se pregătește să facă o scamatorie. Acesta vrea să întoarcă toate cărțile pe spate, o operație constă în alegerea a mai multor cărți pe față adiacente și întoarcerea lor. Ca să facă totul mai interesant el alege Q persoane din public si acestea îi spun două numere, X Y, cu semnficația ca Le. Quack să facă toate trucurile posibile cu X cărți inițial pe față toate și exact Y operații de întoarcere astfel încât să ajungă cu toate cele X cărți alese pe spate. După fiecare dintre cele Q persoane el repune toate cărțile pe față. Le. Quack trebuie să numere toate posibilitățile de a face fiecare truc de magie doar că nu este bun la informatică așa că vă cere ajutorul!

Se dă N și Q, apoi Q interogări de tipul K X pentru fiecare interogare să se afișeze separate prin spațiu ( ficare interogare pe un rând diferit ):

1. Câți vectori de exact N elemente din intervalul \([0, {2}^{K})\) ( mai mari sau egale cu \(0\) și strict mai mici ca \({2}^{K}\) ) există astfel încât valoarea \(a_1\) & \(a_2\) & ... & \(a_N\) să fie X-frumoasă. Un număr este X-frumos dacă în reprezentare binară are exat X biți setați ( cu valoare = 1 ). Cu & am notat operația pe biți AND.

2. Câți vectori de exact N elemente din intervalul \([0, {2}^{K})\) ( mai mari sau egale cu \(0\) și strict mai mici ca \({2}^{K}\) ) există astfel încât valoarea \(a_1\) | \(a_2\) | ... | \(a_N\) să fie X-frumoasă. Un număr este X-frumos dacă în reprezentare binară are exat X biți setați ( cu valoare = 1 ). Cu | am notat operația pe biți OR.

3.Câți vectori de exact N elemente din intervalul \([0, {2}^{K})\) ( mai mari sau egale cu \(0\) și strict mai mici ca \({2}^{K}\) ) există astfel încât valoarea \(a_1\) ^ \(a_2\) ^ ... ^ \(a_N\) să fie X-frumoasă. Un număr este X-frumos dacă în reprezentare binară are exat X biți setați ( cu valoare = 1 ). Cu ^ am notat operația pe biți XOR.