Matei vrea să își conecteze cele 40 de difuzoare bluetooth la telefon. Telefonul și fiecare dispozitiv se pot conecta simultan la cel mult 3 alte dispozitive, iar latența fiecărei conexiuni este exact o milisecundă.Care este latența minimă pe care o poate obține Matei între telefon și cel mai depărtat difuzor?
- 3
- 4
- 5
- 6
- 7
- 8
Rețeaua optimă e un arbore înrădăcinat în telefon, cu telefonul având 3 copii direcți și fiecare alt nod având cel mult 2 copii (a treia conexiune fiind folosită pentru legătura spre părinte). La adâncimea r se pot acoperi cel mult 3⋅(2r−1) difuzoare: pentru r=3 sunt cel mult 21 difuzoare (insuficient pentru 40), iar pentru r=4 sunt cel mult 45 (suficient). Latența minimă este deci 4 milisecunde.Țara Numberland are o sută de mii de orașe, numerotate 1,2,…,100000. Între orașul i și orașul j: dacă (i−j)mod5≤2, există o autostradă directă de lungime ∣i−j∣; altfel există o cale ferată directă, tot de lungime ∣i−j∣ (niciodată ambele).Distanța dintre două orașe este cea mai mică lungime totală obținută folosind fie numai autostrăzi, fie numai căi ferate (un traseu nu amestecă cele două rețele) — de exemplu, din orașul 1 în orașul 2 nu există o cale ferată directă (perechea are o autostradă directă), dar un traseu numai pe calea ferată există totuși prin orașul 5, cu lungimea totală 7.Care este suma distanțelor dintre toate perechile de orașe?
- 333333333400000
- 333343333400000
- 166671666750000
- 166666666650000
- 166666766600000
- 366666766600000
Pentru orice două orașe consecutive, diferența este 1, iar 1mod5=1≤2, deci există mereu o autostradă directă de lungime 1 între orașe vecine. Înlănțuind aceste autostrăzi consecutive, distanța „numai cu mașina” dintre oricare orașe i și j este exact ∣i−j∣ — minimul teoretic posibil, pe care nicio combinație de căi ferate nu îl poate coborî. Așadar distanța reală dintre orice două orașe este mereu ∣i−j∣, iar suma cerută este 1≤i<j≤100000∑(j−i)=C1000013=166666666650000Un tată vrea ca numele celor două fete ale sale să fie la aceeași distanță de editare de cuvântul elma. Pentru perechile care conțin *, cele două cuvinte sunt considerate la aceeași distanță de elma dacă există cel puțin un mod de a înlocui fiecare * cu o literă astfel încât cele două cuvinte obținute să fie la aceeași distanță de elma.Distanța de editare este numărul minim de adăugări, modificări sau ștergeri ale unui caracter necesare pentru a transforma un cuvânt în altul (de exemplu, distanța dintre elma și ema este 1, iar dintre elma și calma este 2).Câte din perechile de mai jos sunt la aceeași distanță de elma?ema și alma · riquelma și vero · dana și clema · fra*a și rex*na · fcsb și steaua · lmx și tlma
- 0
- 1
- 2
- 3
- 4
- 5
Distanțele față de elma: (ema,alma) sunt ambele la 1 — la fel; (riquelma,vero) sunt ambele la 4 — la fel; (dana,clema) sunt la 3, respectiv 2 — diferit; pentru (fra*a,rex*na) există o alegere a celor două * care aduce ambele cuvinte la aceeași distanță — la fel; (fcsb,steaua) sunt ambele la 4 — la fel; (lmx,tlma) sunt la 2, respectiv 1 — diferit. În total, 4 din cele 6 perechi sunt la aceeași distanță de elma.În țara Numberland există N orașe, fiecare aflat în câte un fus orar întreg, toate diferite între ele. Decalajul orar dintre oricare două orașe este un număr prim.Care este numărul maxim N de orașe posibil?
- 3
- 4
- 5
- 13
- 15
- 17
Dacă două orașe au fusuri de aceeași paritate, decalajul lor e par, deci trebuie să fie exact 2 (singurul număr prim par) — iar 3 fusuri de aceeași paritate ar cere ca toate diferențele perechi dintre ele să fie 2, ceea ce e imposibil (dacă a<b<c diferă toate cu 2, atunci c−a=4=2). Deci cel mult 2 fusuri pot avea fiecare paritate, adică N≤4. Un exemplu cu N=4: fusurile 0,2,5,7 — toate decalajele (2,5,7,3,5,2) sunt prime. Deci maximul este 4.Dat un număr X, Matei poate fie să îl transforme în 5X, fie — dacă ultima cifră a lui X este 0 sau 5 — să îl transforme în X+1, X+2, X+3 sau X+4.Care este numărul minim de transformări pentru a ajunge din 0 în 202520252025?
- 24
- 25
- 26
- 27
- 28
- 29
Fiecare secvență de transformări corespunde exact scrierii lui X în baza 5: o operație „+d” (cu d∈{1,2,3,4}) plasează o cifră nenulă, iar o operație „×5” trece la cifra următoare. Numărul minim de pași este (numărul de cifre în baza 5, minus 1, pentru operațiile de înmulțire) plus (numărul de cifre nenule, pentru operațiile de adunare). Scriind 202520252025 în baza 5 se obțin 17 cifre, dintre care 12 sunt nenule, deci minimul este (17−1)+12=28.