Lista de probleme 13

Filtrare

JocDeSah

#3542

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.

RAU-Coder 2020

Fișiere Daniela Alexandra Crisan concurs Clasa 10 Structuri de date liniare Coada Operații pe biți

Rezolvă

D-BitwiseParadise

#3838

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.

infoleague.net runda antrenament 2, problema D.

Fișiere Tudor Iacob concurs Clasa 10 Probleme diverse Combinatorică Programare dinamică Combinari Exponentiere rapida Invers modular Precalculare number theory Formula Operații pe biți

Rezolvă

Josephus Sequence

#3897

Josephus este un matematician înrăit.
Într-o zi acesta se joacă cu primele N numere prime, când se decide să își construiască propiul său șir circular format din aceste numere. Pe prima poziție se va afla primul număr prim, adică 2, iar mai apoi se parcurge circular șirul din K în K, completându-se cu restul de numere prime, până la repartizarea tuturor.

ad-hoc

Fișiere Bucă Mihnea-Vicențiu, Ovidiu Mihail Dumitrescu dificilă Clasa 11 Structuri de date arborescente Structuri de date Parsare ciurul lui Eratostene Operații pe biți Arbori de intervale Arbori indexați binar set

Rezolvă

Du-te sus!