Admitere FMI la UniBuc

Operatorii *, / și % (în Pascal, *, div și mod) au aceeași prioritate, iar evaluarea are loc de la stânga la dreapta. Expresia calculează deci restul lui $(x\bmod20)\cdot x$ la împărțirea prin $26$, apoi câtul întreg al acestui rest la $2$.

Pentru $1\le x\le9$ avem $x\bmod20=x$, deci rămâne restul lui $x^2$ la $26$. Un astfel de rest este cel mult $25$, iar pentru $x=5$ restul este chiar $25$, deoarece $5^2=25$. Câtul întreg al lui $25$ la $2$ este $12$, iar un rest mai mic dă un cât cel mult egal cu $12$.

Prin urmare, valoarea maximă a expresiei este $12$.

Suma gradelor vârfurilor unui graf neorientat este dublul numărului de muchii, deoarece fiecare muchie contribuie cu $1$ la gradul fiecăreia dintre extremitățile ei. Graful are deci $m$ muchii, cu $2m=26\cdot20=520$, adică $m=260$.

Graful este conex, deci are un arbore parțial, iar un arbore cu $26$ de noduri are $25$ de muchii. Prin urmare, trebuie să eliminăm $260-25=235$ de muchii.

Urmărim ce face un apel. Considerăm x scris cu $d$ cifre, eventual cu zerouri la început, și y egal cu $10^{d-1}$. Atunci câtul x / y (în Pascal, x div y) este prima cifră a lui x, iar x % 10 (în Pascal, x mod 10) este ultima. Funcția compară aceste două cifre, apoi le elimină pe amândouă prin x % y / 10 (în Pascal, x mod y div 10) și împarte y la $100$, deci aceeași legătură rămâne valabilă pentru cele $d-2$ cifre rămase. Așadar, când y este $10^{d-1}$, funcția întoarce $1$ exact când cifrele lui x formează un palindrom.

Calculăm cei cinci termeni:

f(20262026, 10000000) este $0$, pentru că prima cifră, $2$, diferă de ultima, $6$.
f(2026202, 1000000) este $1$, pentru că y este $10^6$, iar $2026202$ este palindrom.
f(716617, 100000) este $1$, pentru că y este $10^5$, iar $716617$ este palindrom.
f(6062606, 100000) este $0$, pentru că aici y are cu două cifre mai puțin decât x, deci câtul este $60$, diferit de ultima cifră, $6$.
f(0, 10) este $1$, din primul caz al funcției.

Prin urmare, expresia are valoarea $0+1+1+0+1=3$.

Tabloul obținut prin interclasare trebuie să fie strict crescător, deci $23<x<y<z<29$. Aceste inegalități le includ pe cele din tablourile $a$ și $b$.

Așadar $x$, $y$ și $z$ sunt trei numere distincte alese dintre $24$, $25$, $26$, $27$ și $28$, iar ordinea lor este impusă de inegalități. Prin urmare, există $C_5^3=10$ seturi de valori.

Urmărim cei patru algoritmi pe exemplul $n=12=2^2\cdot3$, pentru care suma divizorilor primi este $2+3=5$.

A3 împarte $n$ la $d$ cât timp împărțirea este exactă, deci elimină toate aparițiile factorului $d$, și adună $d$ o singură dată, când $p\ne0$. Pentru $n=12$ obține $s=2+3=5$. Un divizor $d$ găsit astfel este prim, pentru că factorii lui primi mai mici au fost deja eliminați din $n$.

A1 împarte o singură dată la fiecare $d$. Pentru $n=12$, după $d=2$ rămâne $n=6$, iar după $d=3$ rămâne $n=2$. Cum $d$ a trecut deja de $2$, $n$ nu mai devine $1$ și bucla nu se termină.

A2 adună $d$ la fiecare împărțire, deci obține $2+2+3=7$, adică suma factorilor primi cu multiplicitate.

A4 nu reinițializează $p$ și continuă cât timp $n\ne0$. După ce $n$ devine $1$, nicio împărțire nu mai reușește, deci bucla nu se oprește.

Prin urmare, algoritmul corect este A3.

Algoritmul numără divizorii lui $n$ și afișează restul acestui număr la $2$, deci afișează $1$ exact când $n$ are un număr impar de divizori.

Grupăm divizorii în perechi $d$ și $n/d$. O pereche are un singur element doar când $d=n/d$, adică $d^2=n$. Așadar $n$ are un număr impar de divizori exact când este pătrat perfect.

Cum $45^2=2025\le2026<46^2=2116$, intervalul $[1,2026]$ conține pătratele perfecte $1^2,2^2,\ldots,45^2$. Prin urmare, algoritmul afișează $1$ pentru $45$ de numere.

Notăm $x_p$ valoarea s.p.x și $x_q$ valoarea s.q.x. Segmentul este paralel cu axa $Ox$, deci extremitățile au aceeași ordonată, iar lungimea lui este $|x_q-x_p|$. Segmentul are lungimea $1$ exact când $(x_q-x_p)^2=1$.

În E2, produsul este $(x_p-x_q)(x_q-x_p)=-(x_q-x_p)^2$, deci E2 este adevărată exact când $(x_q-x_p)^2=1$.

E1 și E4 folosesc s.x și s.y, dar s are doar câmpurile p și q, deci aceste expresii nu sunt corecte sintactic. În E3, ordonatele sunt egale, deci produsul este $0$ și expresia este mereu falsă.

Prin urmare, expresia cerută este E2.

Backtracking-ul generează vectorii în ordine lexicografică. Un vector de tați este valid dacă $t[1]=0$, niciun nod nu este propriul tată și, urcând din orice nod de la tată la tată, ajungem la rădăcina $1$ fără să intrăm într-un ciclu.

Continuăm după primele patru soluții:

$(0,1,2,2)$ este soluția 5.
$(0,1,2,3)$ este soluția 6, pentru că lanțul $4\to3\to2\to1$ ajunge la rădăcină.
Valoarea $t[3]=3$ nu este permisă, deci trecem la $t[3]=4$.
$(0,1,4,1)$ este soluția 7.
$(0,1,4,2)$ este soluția 8.
$(0,1,4,3)$ este respins, pentru că nodurile $3$ și $4$ formează un ciclu.
Valoarea $t[2]=2$ nu este permisă, deci trecem la $t[2]=3$, iar primul vector valid este $(0,3,1,1)$.

Prin urmare, a noua soluție generată este $(0,3,1,1)$.

Folosim sume parțiale. La o primă parcurgere calculăm suma tuturor elementelor impare. La a doua parcurgere, de la stânga la dreapta, păstrăm două sume. Prima este suma elementelor pare aflate înaintea poziției curente $k$. A doua este suma elementelor impare aflate după poziția $k$, pe care o obținem scăzând din total elementele impare de pe pozițiile $1,\ldots,k$, deci și elementul curent, dacă este impar.

Pentru fiecare poziție $k$ comparăm cele două sume și le actualizăm în timp constant, deci cele două parcurgeri fac $O(n)$ operații. Nu putem coborî sub $O(n)$, deoarece orice element poate schimba răspunsul, deci trebuie citit cel puțin o dată.

Prin urmare, complexitatea celui mai eficient algoritm este $O(n)$.

Cum n div 2 este $3$, pe diagonală avem $t[i,i]=|3-i+1|=|4-i|$. Bucla interioară copiază această valoare în restul liniei $i$, la dreapta diagonalei, și în restul coloanei $i$, sub diagonală. Liniile următoare nu mai scriu în aceste poziții, deci

Însumăm elementele de pe chenar. Pe prima linie și pe prima coloană $\min(i,j)=1$, deci toate cele $13$ elemente distincte valorează $3$ și dau $39$. Restul ultimei linii, pentru $j=2,\ldots,7$, dă $2+1+0+1+2+3=9$. Restul ultimei coloane, pentru $i=2,\ldots,6$, dă $2+1+0+1+2=6$.

Prin urmare, secvența afișează $39+9+6=54$.

Un arc duce de la o etichetă la o etichetă care o conține. Verificăm pe rând cele cinci afirmații.

Afirmația 1 este adevărată. Eticheta ar nu conține nicio altă etichetă, deci are gradul interior nul, dar apare în parc, par, arc și altele, deci are gradul exterior nenul.

Afirmația 2 este adevărată. Eticheta parcare nu apare în nicio altă etichetă, dar conține ar, par, arc, parc, arca și re.

Afirmația 3 este falsă. Eticheta banca nu conține nicio altă etichetă și nu apare în nicio altă etichetă, deci vârful banca este izolat.

Afirmația 4 este falsă. Etichetele sunt distincte, deci un arc duce întotdeauna spre o etichetă strict mai lungă. Lungimea crește de-a lungul oricărui drum, așa că nu ne putem întoarce în vârful de plecare.

Afirmația 5 este adevărată. În arc intră doar arcul de la ar, iar din arc pleacă arce spre parc, arca și parcare.

Prin urmare, sunt adevărate $3$ afirmații.

Comutatoarele din stânga-sus și din dreapta-jos schimbă aceleași două becuri, cele de pe diagonala secundară. La fel, comutatoarele din dreapta-sus și din stânga-jos schimbă ambele becurile de pe diagonala principală.

Ordinea apăsărilor nu contează, iar două schimbări ale aceleiași perechi se anulează. Așadar orice șir de apăsări are unul dintre patru efecte: nu schimbă nimic, schimbă diagonala principală, schimbă diagonala secundară sau schimbă toate becurile.

Putem stinge toate becurile exact când configurația inițială provine din panoul stins printr-unul dintre aceste efecte. Acestea sunt toate becurile stinse, doar diagonala principală aprinsă, doar diagonala secundară aprinsă și toate becurile aprinse.

Prin urmare, există $4$ configurații inițiale din care putem obține panoul stins.

Pentru fiecare literă a lui s, $k$ este poziția ei în alfabet numărată de la $0$, iar bucla interioară adaugă de $k$ ori la t sufixul lui s care începe cu acea literă. În C/C++, s + i este sufixul care începe la indicele i, iar în Pascal copy(s, i, 100) dă același sufix, cu indicii numărați de la $1$.

Literele d, e, c, a, d, a dau $k=3,4,2,0,3,0$, iar sufixele corespunzătoare au lungimile $6,5,4,3,2,1$. Lungimea lui t este

Prin urmare, șirul t are lungimea $52$.

Notăm cu $a(n)$ numărul permutărilor lui $\{1,2,\ldots,n\}$ pe care o singură trecere le ordonează. Fie $k$ poziția maximului $n$ în permutare.

Pe primele $k-1$ poziții, trecerea lucrează exact ca o trecere separată asupra lor, iar comparația cu maximul nu produce interschimbare. Când trecerea ajunge la maxim, acesta este mai mare decât toate elementele următoare, deci este interschimbat la fiecare pas și ajunge pe ultima poziție. Elementele de după el se mută cu o poziție la stânga, fără să-și schimbe ordinea.

Tabloul final este ordonat exact când elementele de după maxim sunt, în ordine, $k,k+1,\ldots,n-1$, iar primele $k-1$ elemente formează o permutare a lui $\{1,\ldots,k-1\}$ pe care o trecere o ordonează. Pentru poziția $k$ avem deci $a(k-1)$ posibilități, cu $a(0)=1$. Însumând după $k=1,\ldots,n$, obținem

Scăzând relația scrisă pentru $n-1$, rezultă $a(n)=2a(n-1)$ pentru $n\ge2$. Cum $a(1)=1$, avem $a(n)=2^{n-1}$, deci

Prin urmare, $x\in(256,512]$.

Căutăm cea mai mică și cea mai mare valoare pe care o poate întoarce foo(N).

Valoarea minimă este $N$. Dacă la primul apel randInt întoarce $0$, atunci foo(0) este $0$ și rezultatul este $N+0=N$. Orice alt apel adaugă numere nenegative.

Valoarea maximă o obținem când randInt alege de fiecare dată cel mai mare argument posibil, $x$ div $2$. Ea este

unde suma din stânga se oprește când termenii devin nuli. Așadar orice valoare întoarsă este cel mult $2N-1$, iar pentru $N$ putere a lui $2$ maximul este chiar $2N-1$. De exemplu, pentru $N=4$ obținem $4+2+1=7$.

Pentru un $N$ fixat, cel mai scurt interval care conține toate valorile este $\displaystyle \left[N,\ N+\left\lfloor\frac N2\right\rfloor+\left\lfloor\frac N4\right\rfloor+\cdots\right]$, iar acesta poate fi mai scurt decât $[N,2N-1]$. De exemplu, pentru $N=5$ valorile posibile sunt $5$, $6$, $7$ și $8$, deci cel mai scurt interval este $[5,8]$, nu $[5,9]$. Enunțul cere însă un interval scris în funcție de $N$, ales dintre cele propuse, valabil pentru orice $N\ge2$.

Prin urmare, dintre intervalele propuse, cel mai scurt care conține garantat toate valorile este $[N,2N-1]$.