Lista de probleme 2

În camera copiilor problema spațiului este esențială. De aceea locul unde sunt depozitate jucăriile este asemănător unei matrici pătratice, dispuse vertical, fiecare jucărie ocupând un locație bine stabilită.

Entuziasmul și bucuria copiilor în a se juca este bine cunoscută, dar și ”disponibilitatea” acestora de a ordona (reașeza) jucăriile la locul prestabilit este proverbială. Cum, după o rundă de joacă, întotdeauna urmează un episod din serialul de desene animate preferat, copii așează la întâmplare jucăriile.

Cunoscând numărul M de jucării, iar pentru fiecare jucărie locația în care copii au pus jucăria (linie, coloană), precum și locația unde trebuie corect pusă aceasta (linie, coloană), ajutați bona să reașeze jucăriile astfel încât numărul de mutării să fie minim. În cazul în care locația unde trebuie mutată o jucărie este ocupată, atunci bona depozitează temporar jucăria într-o locație specială, dacă este liberă, până când locația unde trebuie mutată se va elibera.

Să se determine:

• numărul minim de mutări ce nu necesită folosirea locației speciale
• numărul minim de mutări necesar rearanjării tuturor jucăriilor

Fie a un număr natural scris în baza 10. Notăm cu b, baza minimă în care poate fi scris a. Astfel, dacă a=21756, atunci baza minimă în care acesta poate fi scris este b=8.
Definim cifra de control a numărului a scris în baza b, notată cu c=digit(a)b, ca fiind numărul de o cifră obținut prin adunarea în baza b a cifrelor numărului a. Dacă rezultatul obținut este de o cifră, atunci acesta reprezintă valoarea lui c, dacă nu, se aplică repetat asupra rezultatului procedeul de însumare a cifrelor în baza b până când se obține o cifră.

De exemplu:

• c=digit(21756)₈=digit(2+1+7+5+6)₈=25, întrucât c>8 procedeul continuă
• c=digit(25)₈=digit(2+5)₈=7.

Se consideră un interval închis [x,y]. Să se determine:

• a – primul număr prim mai mare sau egal ca x
• b – baza minimă în care poate fi scris numărul prim a
• c – cifra de control a numărului prim a
• n – numărul de numere prime din intervalul [x,y] ce pot fi scrise în baza b și au cifra de control egală cu c.