Lista de probleme 8

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

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

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

#1255 Lipsa

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

#1435 Biti

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?

#3694 tomi

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.

#3770 Bisectoare C++

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?

Se dau Q interogări de tipul : n , st , dr , r , k. Pentru fiecare din aceste interogări să se determine care este numărul maxim din șirul [n xor st , n xor (st+1) , n xor (st+2) , .... , n xor dr] care dă restul k prin împărțire la r , precum și numărul de numere din secvența care dau restul k prin împărțire la r.

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.