Lista de probleme 11

Într-un şir trebuie determinată lungimea maximă a unei secvenţe de numere care în scrierea binară au numai cifra 1.

Fie un număr natural n, n < 262. Să se afişeze toate numerele naturale mai mici sau egale cu n, cu proprietatea că reprezentarea lor in baza 2 are exact două cifre 1.

Se dau n numere naturale. Doar unul are frecvență impară. Să se identifice acel număr.

Fiind date n - 1 numere de la 1 la n, să se găseasca numărul lipsă.

Zoli a primit de la doamna profesoară un șir cu n elemente, numere naturale. Lui Zoli i se cere să răspundă corect la întrebarea: “Câte numere din șir au în reprezentarea binară doar biți setați – adică au toți biții 1?

Tomi este primarul ales în orașul Bittown. În oras sunt N locuitori și fiecare are un gard format din exact 60 de scânduri, fiecare dintre ele fiind vopsită în alb sau negru. Fiecare gard este codificat de Tomi printr-un număr natural a cărui reprezentare binară reproduce configurația gardului, de la stânga spre dreapta, scândurile negre fiind asimilate cu bitul 1 iar cele albe cu bitul 0. Astfel, ca exemplu, gardul care are doar ultimele două scânduri vopsite în negru va fi codificat de Tomi cu numărul 3. Tomi decide să-și construiască un gard care să fie reprezentativ pentru Bittown, adică să respecte toate regulile următoare:
1. Gardul primarului Tomi trebuie să aibă exact 60 de scânduri;
2. Trebuie să existe cel puțin K locuitori în Bittown care constată că pentru toate scândurile negre din gardul propriu, scândurile situate pe aceeași poziție în gardul primarului Tomi sunt vopsite tot în negru;
3. Numărul reprezentând codul gardului primarului Tomi trebuie să fie minim posibil.

RAU-Gigel are un șir de puncte, nu neapărat distincte, aflate pe prima bisectoare. Punctele sunt caracterizate prin câte două coordonate (abscisă și ordonată), ambele numere întregi. Când le-a copiat pe caiet, din neatenție, RAU-Gigel a amestecat coordonatele celor N puncte și omis ordonata unuia dintre ele. Care este aceasta, puteți să îl ajutați?

Fie un număr natural nenul n, cunoscut. RAU-Gigel alege un număr oarecare între 1 și n, fie acesta x. Apoi calculează “suma XOR” S = 1 ^ 2 ^ ... ^ (x-2) ^ (x-1) ^ (x+1) ^ (x+2) ^ ... ^ n pe care v-o comunică. Puteți să-l ghiciți pe x ? RAU-Gigel nu prea are răbdare, el vrea repede un răspuns de la voi.

RAU-Gigel se gândește la un joc cu piesele de șah. El desenează o tablă de șah sub forma unei matrici pătratice de latură N și așează în fiecare dintre cele N x N celule câte o piesă de șah. Se consideră că dispune de N X N exemplare din fiecare piesă posibilă (regi, regine, ture, nebuni, cai, pioni), iar culoarea nu este relevantă. RAU-Gigel se întreabă care este numărul minim de căsuțe (celule) prin care trebuie să treacă un rege oarecare ca să ajungă la o regină oarecare. Regele se poate deplasa câte o celulă în patru direcții posibile: N, E, S, V.

Dar asta nu e tot. La începutul jocului, toți regii au 16 vieți. Atunci când RAU-Gigel mută un rege (oarecare) peste primul pion, acesta pierde o viață. Vestea bună este că, după aceea, regele respectiv poate lua oricâți pioni fără ca numărul său de vieți să fie afectat. Când ia un cal, regele pierde două vieți, dar după aceea poate lua, fără pierderi, oricâți cai. La fel se întâmplă și în cazul nebunilor, primul nebun îl costa patru vieți și, respectiv al turelor, care îl costă opt vieți.

RAU-Gigel dorește să afle ce rege să aleagă și pe ce traseu trebuie să meargă acesta către o regină oarecare, astfel încât la sfârșitul jocului să îi rămână cât mai multe vieți, iar traseul să fie cât mai scurt.

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.