Pregătire cu un profesor

Problema Sort
Fis, ier de intrare: sort.in
Fis, ier de ies, ire: sort.out
Fie A un s, ir de N numere naturale. Construit, i un s, ir B de N numere naturale care respect˘a urm˘atoarele
propriet˘at, i:
• Pentru tot, i 1 ≤ i ≤ N − 1, B[i] ≤ B[i + 1].
• Pentru tot, i 1 ≤ i ≤ N , B[i] poate fi obt, inut din A[i] printr-un num˘ar de permut˘ari circulare ale
cifrelor lui A[i]. Acest num˘ar poate fi 0, ˆın acest caz B[i] = A[i].
Operat, ia de permutare circular˘a mut˘a toate cifrele, ˆın afar˘a de prima, cu o pozit¸ie spre stˆanga ¸si aduce
prima cifr˘a pe ultima pozit¸ie. De exemplu, din num˘arul 12345 putem obt, ine, printre altele, numerele
34512 s, i 51234 folosind permut˘ari circulare, dar nu putem obt, ine num˘arul 14325.
Se garanteaz˘a c˘a pentru tot, i 1 ≤ i ≤ N , A[i] nu cont, ine cifra 0.
Date de intrare
Prima linie va cont, ine num˘arul N . A doua linie va cont, ine s, irul A, constˆand din N numere naturale
separate prin cˆate un spat, iu.
Date de ies, ire
Dac˘a nu exist˘a niciun s, ir B care respect˘a propriet˘at, ile din enunt, , afis, at, i cuvˆantul N U pe prima linie.
Altfel, afis, at, i cuvˆantul DA pe prima linie. Pe a doua linie afis, at, i orice s, ir B care respect˘a propriet˘at, ile
din enunt, .
Subtask-uri
# Punctaj Restrict, ii
1 21 N = 2
2 22 1 ≤ N ≤ 6
3 57 1 ≤ N ≤ 10 000
Pentru toate subtask-urile, 1 ≤ A[i] ≤ 108.
Trebuie s˘a rezolvat, i corect toate testele din cadrul unui subtask pentru a primi punctajul aferent acestuia.
Exemple
sort.in sort.out
3
2435 2134 1135
DA
2435 3421 3511
3
511 765 4
NU
Explicat, ii
ˆIn al doilea exemplu, B[2] poate fi 765, 657 sau 576, dar niciuna din aceste variante nu este mai mic˘a sau
egal˘a cu 4.
1

Subiect · pagina 2

Problema Kscale
Intrare: kscale.in
Ies, ire: kscale.out
Definim funct, ia scale(A, k1, k2) care primes, te ca argumente o matrice binar˘a A, dou˘a numere naturale
nenule k1 s, i k2 s, i ˆıntoarce o matrice binar˘a ˆın care fiecare celul˘a din A a fost ˆınlocuit˘a cu o submatrice
de dimensiune k1 × k2 de aceeas, i valoare cu cea original˘a.
De exemplu, dac˘a:
A = 1 0
0 1
scale(A, 2, 3) =
1 1 1 0 0 0
1 1 1 0 0 0
0 0 0 1 1 1
0 0 0 1 1 1
Fie B o matrice de dimensiune N ×M . Voi trebuie s˘a construit, i o matrice A de arie minim˘a, pentru care
exist˘a k1 s, i k2 astfel ˆıncˆat scale(A, k1, k2) = B. Orice matrice valid˘a A de arie minim˘a va fi acceptat˘a.
Date de intrare
Fis, ierul de intrare kscale.in cont, ine pe prima linie dou˘a numere naturale n si m reprezentˆand num˘arul
de linii, respectiv coloane ale matricei B. Urm˘atoarele n linii cont, in cˆate m caractere de tip 0 sau 1.
Date de ies, ire
Fi¸sierul de ie¸sire kscale.out va cont, ine pe prima linie dou˘a numere naturale p s, i t reprezentˆand num˘arul
de linii, respectiv de coloane ale matricei A. Pe urm˘atoarele p linii se va afis, a matricea A ˆın format similar
cu cel din fis, ierul de intrare.
# Punctaj Restrict, ii
1 21 puncte N = 1; 1 ≤ M ≤ 100
2 18 puncte 1 ≤ N, M ≤ 100 s, i se garanteaz˘a c˘a exist˘a solut, ie cu k1 = k2.
3 49 puncte 1 ≤ N, M ≤ 100
3 12 puncte 1 ≤ N, M ≤ 1 000
Anumite teste din interiorul unui subtask pot fi grupate, dar nu neaparat toate.
Exemple
kscale.in kscale.out
1 10
0000001100
1 5
00010
4 6
111000
111000
000111
000111
2 2
10
01
2

Subiect · pagina 3

Problema Secretariat
Fis, ier de intrare: secretariat.in
Fis, ier de ies, ire: secretariat.out
La Secretariat exist˘a N ghis, ee, numerotate de la 1 la N . Un num˘ar de persoane a format deja N cozi,
cˆate una la fiecare ghis, eu.
Fiecare persoan˘a are o singur˘a problem˘a de rezolvat.Exist˘a K tipuri de probleme, numerotate de la 1 la
K, unde K ≤ N . Exist˘a cel put, in cˆate o persoan˘a cu fiecare problem˘a dintre cele K.
Personalul Secretariatului ar aprecia dac˘a fiecare coad˘a ar cont, ine persoane cu un singur tip de problem˘a.
Pentru a realiza acest lucru, poate fi nevoie s˘a rearanj˘am cozile. Pentru a reraranja cozile, se poate face
un singur tip de operat, ie:
Operat, ia (i, j) ia prima persoan˘a din coada de la ghis, eul i s, i o plaseaz˘a ˆın spatele cozii de la ghis, eul j.
Este permis (des, i trist) ca i = j.
Dorim s˘a efectu˘am un num˘ar minim de operat, ii pentru a satisface proprietatea cerut˘a. Din fericire,
asocierea ghis, eu-problem˘a nu este fixat˘a ˆın acest moment s, i poate fi decis˘a de noi pentru a minimiza
num˘arul de operat, ii.
Date de intrare
Prima linie va cont, ine numerele N s, i K, separate printr-un spat, iu.
Cont, inutul urm˘atoarelor N linii va fi urm˘atorul: linia i va ˆıncepe cu un num˘ar natural Ni reprezentˆand
num˘arul de persoane din coada de la ghis, eul i, urmat de Ni numere ˆıntre 1 s, i K, separate prin cˆate un
spat, iu, reprezentˆand tipul problemelor avute de persoanele aflate la coad˘a, ˆın ordine dinspre fat, a cozii
ˆınspre spatele ei.
Date de ies, ire
Prima linie va cont, ine o singur˘a valoare, ANS reprezent˘and num˘arul minim de operat, ii cerut de problem˘a.
Urm˘atoarele ANS linii vor fi de forma i j (unde i s, i j sunt separate de un spat, iu) reprezentˆand faptul
c˘a prima persoan˘a din coada de la ghis, eul i merge s, i se as, eaz˘a ˆın spatele cozii de la ghis, eul j.
Subtask-uri
# Punctaj Restrict, ii
1 32 N = K = 2
2 25 1 ≤ N ≤ 1 000 s, i K = N
3 43 1 ≤ K ≤ N ≤ 1 000
Pentru toate testele, pentru tot, i 1 ≤ i ≤ N , se respect˘a 1 ≤ Ni ≤ 2 000, iar totalul de oameni aflat, i la
coad˘a este cel mult 500 000.
Trebuie s˘a rezolvat, i corect toate testele din cadrul unui subtask pentru a primi punctajul aferent acestuia.
Exemple
secretariat.in secretariat.out
4 3
4 2 2 1 1
3 3 3 3
4 1 2 1 2
1 1
5
3 4
3 3
1 3
3 1
1 3
3

Subiect · pagina 4

Exemplul descrie urm˘atoarea situat, ie:
Ghis, eul 1: 2 2 1 1
Ghis, eul 2: 3 3 3
Ghis, eul 3: 1 2 1 2
Ghis, eul 4: 1
Se poate ar˘ata c˘a nu exist˘a solut, ie cu mai put, in de 5 operat, ii. Dup˘a cele 5 operat, ii descrise ˆın fis, ierul de
ies, ire, cozile vor ar˘ata astfel:
Ghis, eul 1: 1 1 1
Ghis, eul 2: 3 3 3
Ghis, eul 3: 2 2 2 2
Ghis, eul 4: 1 1
4

Subiect · pagina 5

Problema Grile
Intrare: standard input
Ies, ire: standard output
S˘a facem un exercit, iu de imaginat, ie. S˘a zicem c˘a ai participat la un examen online de tip gril˘a cu un
total de N = 20 ˆıntreb˘ari, structurat astfel:
• Primele 10 ˆıntreb˘ari us, oare, fiecare valorˆand 2 puncte s, i avˆand 5 variante de r˘aspuns.
• Urm˘atoarele 6 ˆıntreb˘ari au fost medii, fiecare valorˆand 3 puncte s, i avˆand 5 variante de r˘aspuns.
• Urm˘atoarele 4 ˆıntreb˘ari au fost dificile, fiecare valorˆand 5 puncte s, i avˆand 10 variante de r˘aspuns.
Fiecare ˆıntrebare are exact un r˘aspuns corect s, i pot, i alege s˘a nu r˘aspunzi deloc la o ˆıntrebare.
Dup˘a ce ai finalizat testul s, i ai trimis r˘aspunsurile, ai observat c˘a ai primit imediat scorul t˘au total, des, i
concursul nu se terminase ˆınc˘a, iar unii concurent, i ˆınc˘a rezolvau subiectul. Asta ˆıt, i d˘a de gˆandit: oare
cineva care are mai multe conturi poate folosi scorul total pentru a extrage informat, ii despre r˘aspunsurile
corecte?
ˆIn practic˘a acest lucru nu s-a ˆıntˆamplat, dar ˆın teorie este perfect posibil. ˆIn aceast˘a problem˘a trebuie s˘a
concepet, i o strategie care s˘a minimizeze num˘arul de conturi pe care ar fi trebuit s˘a le avet, i ca s˘a putet, i
obt, ine punctaj maxim la acest examen imaginar de tip gril˘a.
Interact, iune
Programul vostru va fi evaluat pe 10 teste, fiecare valorˆand 10 puncte. ˆIn cadrul unui test, programul
vostru va simula T = 200 de examene. Fiecare examen este structurat conform descrierii de mai sus s, i
are un set de r˘aspunsuri corecte generate aleator uniform.
Init, ial vet, i citi valoarea lui T . Apoi, ˆıncepet, i examenul 1. Cˆat timp nu at, i obt, inut punctaj maxim pentru
examenul curent, putet, i trimite un set de r˘aspunsuri c˘atre evaluator. Un set de r˘aspunsuri cont, ine exact
N = 20 numere naturale, codificˆand r˘aspunsurile voastre pentru fiecare ˆıntrebare. Pentru o ˆıntrebare
cu M variante de r˘aspuns, variantele sunt numerotate de la 0 la M − 1 inclusiv. Valoarea −1 semnific˘a
faptul c˘a nu dorit, i s˘a r˘aspundet, i la ˆıntrebarea respectiv˘a.
Dup˘a ce afis, at, i un set de r˘aspunsuri, putet, i citi scorul obt, inut de acest set. Dac˘a acest scor este maxim,
examenul curent s-a terminat, iar evaluatorul va trece tacit la urm˘atorul examen (iar voi trebuie s˘a facet, i
la fel). Altfel, evaluatorul as, teapt˘a urm˘atorul set de r˘aspunsuri. Putet, i trimite cel mult 200 de seturi de
r˘aspunsuri ˆın cadrul unui examen.
Atent, ie! Protocolul de interact, iune trebuie respectat cu strictet, e. ˆInc˘alcarea protocolului poate afecta
evaluarea solut, iei ˆın feluri neas, teptate. ˆIn cazul anumitor tipuri de gres, eli (spre exemplu, afis, at, i o variant˘a
invalid˘a pentru o anumit˘a ˆıntrebare sau dep˘as, it, i limita de 200 de seturi per examen), evaluatorul va afis, a
valoarea −1 ˆın loc de scorul total s, i va ˆıncheia interact, iunea cu 0 puncte. Putet, i folosi acest semnal
pentru a v˘a opri programul.
Punctaj
Dac˘a programul vostru obt, ine punctaj maxim pentru un examen, evaluatorul va ret, ine num˘arul de seturi
pe care le-at, i trimis ca s˘a realizat, i acest lucru. Fie aceast˘a valoare S. La finalul interact, iunii, programul
va face media valorilor S pentru toate cele 200 de examene, fie aceast˘a valoare Smed. Atunci punctajul
pentru un test este dat de formula 0.1 · f (Smed), unde
f (x) =



100, dac˘a x ≤ 30
152.5 − 1.75 · x, dac˘a 30 < x ≤ 70
45.62 − 0.22 · x, dac˘a 70 < x ≤ 200
5

Subiect · pagina 6

Exemple
intrare ies, ire
2
3
4
0
3
4
0 0 0 0
0 0 0 1
0 1 -1 0
1 0 0 0
1 0 1 0
Explicat, ii
Din cauza limit˘arilor de spat, iu, vom ilustra o interact, iune pentru un test fictiv ˆın care avem T = 2
examene cu N = 4 ˆıntreb˘ari, fiecare cu 2 variante s, i valorˆand cˆate 1 punct. Amintim c˘a toate testele
folosite pentru evaluare vor respecta restrict, iile descrise ˆın enunt, .
Concurentul cites, te ˆın primul rˆand de la tastatur˘a valoarea lui T . Apoi trimite un set de r˘aspunsuri
pentru primul examen (r˘aspunde cu prima variant˘a la toate cele 4 ˆıntreb˘ari). Evaluatorul ˆıi spune c˘a
a obt, inut astfel scorul 3. Concurentul trimite un nou set de r˘aspunsuri (ˆın care schimb˘a r˘aspunsul la a
patra ˆıntrebare) s, i printr-un noroc semnificativ obt, ine 4 puncte, adic˘a punctaj maxim.
ˆIn acest moment, interactorul ˆıncepe un nou examen, iar concurentul trimite seturi de r˘aspunsuri pentru
acesta. Observat, i c˘a ˆın primul set, concurentul alege s˘a nu r˘aspund˘a deloc la ˆıntrebarea cu num˘arul 3.
Dup˘a ˆınc˘a dou˘a seturi trimise, concurentul obt, ine din nou punctaj maxim, iar interact, iunea se termin˘a.
Concurentul a folosit 2, respectiv 3 seturi pentru a rezolva cele dou˘a examene, deci Smed = 2.5
6

Deschide documentul original

Barem · 4 pagini

Barem · pagina 1

MateInfoUB Informatic˘a
Runda 2
Descrierea Solut, iilor
1 Sort
Merit˘a s˘a ne gˆandim la o abordare care construies, te s, irul B incremental, ad˘augˆand cˆate un element la final. ˆIn
acest caz ne ˆıntreb˘am ˆın primul rˆand ce valoare ar trebui s˘a alegem pentru B[1]. Este natural s˘a alegem cea mai
mic˘a valoare posibil˘a, fiindc˘a aceast˘a decizie ne ofer˘a mai mult˘a libertate ˆın alegerea lui B[2].
Acest argument se generalizeaz˘a us, or pentru a obt, ine solut, ia complet˘a: pentru fiecare i, alegem cel mai mic B[i]
care este permutare circular˘a a lui A[i] s, i satisface B[i] ≥ B[i − 1].
Pentru a analiza complexitatea de timp, not˘am c˘a ˆın general un num˘ar de C cifre are cel mult C permut˘ari circulare,
iar timpul necesar pentru a itera peste toate este proport, ional cu C (dac˘a gener˘am urm˘atoarea permutare ˆın timp
constant) sau C2 (dac˘a gener˘am urm˘atoarea permutare ˆın timp O(C)). ˆIn cazul nostru C <= 7, deci atˆat solut, iile
ˆın O(n × C), respectiv O(n × C2) ruleaz˘a suficient de repede pentru a obt, ine punctaj maxim.
2 Kscale
Subtask-ul (N = 1)
Adesea, ˆın cazul problemelor care implic˘a o matrice sau alte structuri multidimensionale, este util s˘a analiz˘am
cazurile de dimensiune mai mic˘a: ˆın acest caz, o matrice 1-D.
La problema de fat, ˘a putem testa efectiv toate variantele de scalare cu k1 = 1; k2 ∈ 1, 2, ..M . Pentru arie minim˘a
trebuie s˘a g˘asim k2 maxim. Pentru a testa dac˘a un k2 este valid, putem ˆımp˘art, i matricea unidimensional˘a ˆın
intervale compacte de lungime k2 ce nu se suprapun (k2 trebuie s˘a fie divizor al lui M ). Dac˘a toate intervalele
compacte astfel formate cont, in un singur tip de caracter (’0’ sau ’1’), atunci exist˘a un A asociat cu valoarea k2
care s˘a reprezinte o solut, ie valid˘a pentru funct, ia scale. Ret, inem s, i construim matricea solut, ie, A, folosind valoarea
maxim˘a k2 ce a fost validat˘a.
Subtask-ul (k1 = k2)
Similar cu subtask-ul 1-D, trebuie s˘a verific˘am toate variantele k1 = k2 = x, cu x ∈ 1, 2..min(N, M ). Complexitatea
de timp este O(N 3).
Subtask-ul (1 ≤ N, M ≤ 100)
O abordare similar˘a se poate aplica dac˘a fix˘am separat k1 s, i k2.
1

Barem · pagina 2

Complexitatea timp O(N 4) se reduce la O
(
N 2
(√N
)2)
dac˘a lu˘am ˆın considerare c˘a putem fixa k1, k2 doar
printre divizorii lui N , respectiv M .
Subtask-ul (1 ≤ N, M ≤ 1000)
Exist˘a cel put, in dou˘a abord˘ari care pot obt, ine punctaj maxim.
Prima variant˘a este s˘a r˘amˆanem pe ideea de a fixa toate valorile fezabile pentru k1, k2, dar s˘a optimiz˘am faza de
validare a perechii, observˆand faptul c˘a putem verifica dac˘a un anumit dreptunghi cont, ine doar valori de 0 sau doar
valori de 1 ˆın timp constant, construind sumele part, iale ale matricei. Astfel, pentru o pereche k1, k2, complexitatea
de verificare se schimb˘a din O(N ∗ M ) ˆın O(N ∗ M/(k1 ∗ k2)), iar suma rezultant˘a este suficient de mic˘a pentru ca
solut, ia s˘a se ˆıncadreze ˆın timp.
A doua variant˘a este s˘a nu mai fix˘am valori pentru k1, k2, ci s˘a ˆıncerc˘am s˘a le deducem din structura matricei. S˘a
revenim la cazul 1-D pentru a dobˆandi nis, te intuit, ie.
ˆIn cazul 1-D trebuie s˘a g˘asim k maxim pentru care exist˘a A astfel ˆıncˆat scale(A, 1, k) = B. Observ˘am c˘a este
necesar s, i suficient ca orice interval maximal de caractere egale s˘a aib˘a lungimea multiplu de k. Pentru a g˘asi k
optim putem, deci, aplica cmmdc pe toate lungimile de intervale maximale cu acelas, i caracter.
Pentru cazul general, N, M ≤ 1000, putem aplica aceeas, i abordare de tip cmmdc, doar c˘a independent pe intervale
maximale orizontale s, i intervale maximale verticale.
Astfel, pentru cazul: B =
1 1 1 1 0 0
1 1 1 1 0 0
0 0 1 1 1 1
0 0 1 1 1 1
k2 va fi egal cu cmmdc dintre lungimile celor 8 intervale maximale 1-D orizontale:
k2 = cmmdc(4, 2, 4, 2, 2, 4, 2, 4) → k2 = 2
s, i k1 va fi calculat prin cmmdc dintre lungimile celor 10 intervale maximale 1D verticale:
k1 = cmmdc(2, 2, 2, 2, 4, 4, 2, 2, 2, 2) = 2.
Pentru a demonstra corectitudinea solut, iei, trebuie s˘a ar˘at˘am dou˘a lucruri:
• Perechea (k1, k2) este valid˘a. Putem imparti matricea B in submatrice disjuncte de dimensiune (k1, k2). Daca
lu˘am ˆın considerare c˘a orice lungime de interval maximal 1D orizontal este multiplu de k2 si orice lungime
de interval maximal 1D vertical este multiplu de k1, atunci avem certitudinea c˘a orice submatrice formata
anterior contine un singur tip de caracter ’0’ sau ’1’.
• Perechea (k1, k2) este optim˘a. S˘a presupunem prin absurd c˘a exist˘a o pereche (k′
1, k′
2) cu k′
1 ∗ k′
2 > k1 ∗ k2.
Atunci k′
1 > k1 sau k′
2 > k2. Putem analiza primul caz f˘ar˘a a restrˆange generalitatea. S, tim c˘a exist˘a un
interval vertical care nu este multiplu de k′
1 (altfel cmmdc-ul calculat nu ar fi de fapt maxim). Putem ar˘ata
c˘a acel interval invalideaz˘a solut, ia (k′
1, k′
2).
Aceast˘a solut, ie poate fi implementat˘a ˆın complexitate O(N ∗ M )
3 Secretariat
Vom face cˆateva observat, ii generale, dup˘a care vom dezvolta solut, ia pe structura subtaskurilor.
1. Pentru a muta o persoan˘a de la o coad˘a este necesar s˘a mut˘am toate persoanele din fat, a ei.
2. ˆIn solut, ia optim˘a fiecare persoan˘a va fi mutat˘a cel mult o dat˘a: din coada la care se afl˘a init, ial la una dintre
cozile asociate ˆın final problemei pe care ˆıncearc˘a s˘a o rezolve. Notat, i c˘a aceste dou˘a cozi pot coincide.
2

Barem · pagina 3

Putem astfel s˘a reformul˘am problema din minimizarea num˘arului de persoane mutate ˆın maximizarea num˘arului
de persoane care nu sunt mutate ˆın timpul operat, iilor. S˘a numim o astfel de persoan˘a fixat˘a.
ˆIn ce condit, ii poate o persoan˘a s˘a r˘amˆan˘a fixat˘a? S˘a lu˘am un exemplu de coad˘a:
Ghis, eul X: 3 2 4 2 2 2
Observ˘am c˘a dac˘a asociem ghis, eului X o alt˘a problem˘a decˆat 2, ultima persoan˘a este nevoit˘a s˘a plece, deci vom
fi nevoit, i s˘a mut˘am ˆıntreaga coad˘a (datorit˘a Observat, iei 1). Dac˘a ˆın schimb ˆıi asociem problema 2, putem fixa
ultimele 3 persoane de la coad˘a (dar nu mai mult, fiindc˘a persoana cu problema 4 trebuie s˘a plece, iar toate
persoanele din fat, a ei trebuie s˘a fac˘a la fel).
S˘a not˘am cu suffixLen[i] lungimea sufixului maximal de persoane cu aceeas, i problem˘a pentru coada cu num˘arul i,
respectiv cu suffixProb[i] indicele acestei probleme. ˆIn general, dac˘a asociem problema SuffixProb[i] ghiseului
i, vom fixa SuffixLen[i] persoane la acest ghiseu. Altfel, vom fixa 0 persoane.
ˆIn acest punct putem calcula usor, dat˘a fiind o asociere ˆıntre ghis, ee s, i probleme, num˘arul maxim de persoane care
pot fi fixate. Fie AssignedProb[i] problema asociat˘a ˆın final ghis, eului i. Num˘arul total de persoane fixate este
atunci suma valorilor SuffixLen[i] pentru tot, i i care respect˘a AssignedProb[i] = SuffixProb[i].
Ne r˘amˆane problema g˘asirii unui AssignedProb[] optim, pe care o vom analiza pentru fiecare subtask.
Subtask-ul (N = K = 2)
ˆIn acest caz exist˘a doar dou˘a variante de a asocia probleme ghis, eelor (1 2 s, i 2 1), putem pur s, i simplu s˘a le ˆıncerc˘am
pe ambele s, i s˘a o alegem pe cea mai bun˘a.
Subtask-ul (N = K ≤ 1 000)
ˆIn acest caz exist˘a N ! asocieri, deci nu avem timp s˘a le ˆıncerc˘am pe toate. Totus, i, s, tim c˘a pentru fiecare problem˘a va
exista exact un ghis, eu asociat, deci putem ˆıncerca s˘a analiz˘am independent alegerea corect˘a pentru fiecare problem˘a.
Este tentant, de exemplu, s˘a asociem fiec˘arei probleme i un ghis, eu j cu SuffixProb[j] = i si SuffixLen[j] maxim
posibil. Observ˘am c˘a unele probleme nu vor g˘asi deloc un astfel de ghis, eu. Vom numi aceste probleme simple,
fiindc˘a ele nu pot contribui la totalul de persoane fixate. Din acest motiv, problemele simple au prioritate sc˘azut˘a
s, i putem s˘a ne imagin˘am c˘a le vom asocia arbitrar ghis, eele r˘amase dup˘a ce prioritiz˘am problemele care pot fixa
persoane.
Ne conduc aceste alegeri la o solut, ie optim˘a global? Din fericire, da. Deoarece un ghis, eu poate contribui cu un
num˘ar de persoane fixate pentru o singur˘a problem˘a, s, tim c˘a dou˘a probleme diferite nu vor concura pe acelas, i
ghis, eu decˆat ˆın cazul ˆın care ambele sunt simple, caz ˆın care sunt irelevante.
Subtask-ul (K ≤ N ≤ 1 000)
ˆIn subtask-ul cel mai general solut, ia optim˘a poate asocia mai multe ghis, ee aceleias, i probleme. Este natural s˘a
ˆıncerc˘am s˘a generaliz˘am solut, ia precedent˘a.
ˆIn acest sens, putem ˆıncerca s˘a hot˘arˆam problema fiec˘arui ghis, eu iterˆand peste ghis, ee ˆın ordine descresc˘atoare a
valorilor SuffixLen[]. Ideal, am dori s˘a asociem cˆat mai des ghis, eul i problemei SuffixProb[i]. Care sunt situat, iile
ˆın care nu putem face acest lucru?
Singura situat, ie este cea ˆın care prin asocierea problemei SuffixProb[i] la ghis, eul i am face imposibil ca problemele
r˘amase ˆınc˘a f˘ar˘a niciun ghis, eu s˘a mai g˘aseasc˘a vreunul. Dar aceast˘a situat, ie poate fi verificat˘a us, or: ˆın timpul
iter˘arii putem p˘astra un contor pentru ghis, eele r˘amase libere, respectiv pentru problemele care nu au primit ˆınc˘a
m˘acar un ghis, eu. Init, ial ambele contoare sunt egale cu N . Apoi la fiecare pas putem calcula cum se modific˘a aceste
contoare dac˘a asociem ghis, eului i problema SuffixProb[i], respectiv dac˘a ˆıl l˘as˘am liber. La final, mai facem o
trecere s, i asociem problemele r˘amase ghis, eelor l˘asate libere.
Dac˘a not˘am cu M num˘arul total de persoane, complexitatea de timp a solut, iei este O(M + sort(N )) unde sort(N )
este complexitatea sort˘arii folosite pentru N elemente. Avˆand N ≤ 1 000, o sortare de complexitate O(N 2) ar fi
intrat ˆın timp f˘ar˘a probleme.
3

Barem · pagina 4

4 Grile
Vom enumera cˆateva strategii posibile, ment, ionˆand c˘a acestea pot fi puternic influent, ate de diverse optimiz˘ari.
• Cea mai simpl˘a strategie este s˘a trimitem pe rˆand, cˆate un r˘aspuns pentru prima ˆıntrebare. Cˆand o rezolv˘am,
ˆıncepem s˘a ghicim a doua ˆıntrebare. Fiindc˘a r˘aspunsurile sunt distribuite aleator, aceast˘a metod˘a trimite ˆın
medie aprox. 70 de seturi.
• O optimizare simpl˘a: dac˘a am r˘amas cu o singur˘a variant˘a neˆıncercat˘a pentru o ˆıntrebare, s, tim c˘a e cea
corect˘a.
• Observ˘am c˘a ne permitem s˘a ˆıncerc˘am ˆın paralel r˘aspunsuri pentru ˆıntreb˘ari din 2 categorii diferite, fiindc˘a
acestea avˆand punctaje diferite, putem deduce din punctajul total care dintre cele dou˘a r˘aspunsuri au fost
corecte. Aceast˘a strategie ne poate duce ˆın zona a aprox. 40 de seturi.
• Analizˆand posibilitatea de a ˆıncerca ˆın paralel 3 ˆıntreb˘ari, observ˘am c˘a putem obt, ine o ambiguitate ˆın cazul
scorului total 5: nu s, tim dac˘a e corect r˘aspunsul de la ˆıntrebarea grea sau celelalte dou˘a. Totus, i, putem
rezolva ambiguitatea printr-un set suplimentar (care poate include s, i ˆıntreb˘ari neimplicate ˆın primul). Mai
mult, observ˘am c˘a probabilitatea de a obt, ine aceast˘a ambiguitate este cel mult 1/4, iar ˆın majoritatea cazurilor
este mult mai mic˘a. Din acest motiv, num˘arul mediu de variante excluse per set de aceast˘a strategie este
foarte apropiat de 3.
• O solut, ie care urmeaz˘a aceast˘a strategie paralel˘a cu 3 r˘aspunsuri, rezolv˘a eficient ambiguitatea s, i are grij˘a
s˘a-s, i adapteze strategia atunci cˆand nu mai sunt disponibile 3 ˆıntreb˘ari din categorii diferite (coborˆand init, ial
la strategia cu 2 ˆıntreb˘ari diferite cˆat timp e posibil˘a) poate obt, ine sub 30 de seturi s, i 100 de puncte.
• Exist˘a strategii care optimizeaz˘a seturile ˆın cadrul unei singure categorii de ˆıntreb˘ari. Spre exemplu, dac˘a la
un moment dat avem M ˆıntreb˘ari cu cˆate 2 variante posibile r˘amase, putem face mai bine decˆat M ˆıntreb˘ari ˆın
medie. Putem trimite r˘aspunsuri la cˆate dou˘a ˆıntreb˘ari simultan. Cu probabilitate 1/2 ambele sunt corecte
sau ambele sunt gres, ite (deci, ambele rezolvate). Cu probabilitate 1/2 trebuie s˘a trimitem un set ˆın plus
pentru a rezolva ambiguitatea. Num˘arul mediu de seturi este astfel 1.5 pentru 2 intrebari, deci 0.75 ∗ M
pentru toate M .
• Optimizarea descris˘a mai sus poate fi generalizat˘a ˆıntr-un algoritm de tip divide-et-impera care ˆıncepe prin
a num˘ara cˆate ˆıntreb˘ari au r˘aspunsul 0, 1, etc. s, i continu˘a prin a face acelas, i lucru recursiv pe submult, imi
mai mici, apelul recursiv putˆand fi oprit cˆand toate ˆıntreb˘arile din submult, imea apelat˘a sunt rezolvate de
r˘aspunsul fixat, sau dimpotriv˘a, niciuna dintre ˆıntreb˘ari nu este rezolvat˘a de r˘aspunsul fixat.
• Strategiile s, i optimiz˘arile de mai sus pot fi generalizate s, i combinate. O astfel de solut, ie hibrid˘a poate obt, ine
chiar un num˘ar mediu de 23.9 de seturi. ˆIn curˆand vom publica problemele pe infoarena.ro s, i v˘a vom invita
s˘a coborˆat, i sub acest prag :).
4

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

Concurs de pregătire · 2021Matematică · Etapa a II-aDeschide fișa Examen de admitere · 2022Matematică, Informatică și Fizică · Varianta 1; broșură comunăDeschide fișa Examen de admitere · 2022Matematică, Informatică și Fizică · Varianta 2; broșură comunăDeschide fișa Examen de admitere · 2022Matematică, Informatică și Fizică · Varianta 3; broșură comunăDeschide fișa Examen de admitere · 2022Matematică, Informatică și Fizică · Varianta 4; broșură comunăDeschide fișa Concurs de pregătire · 2022Informatică · Etapa a II-aDeschide fișa

Răspunsuri directe

Ce trebuie să știi despre acest subiect?

Ce document de admitere este acesta?

Pagina prezintă concurs de pregătire din 2021 pentru Informatică, la Facultatea de Matematică și Informatică. Documentul este etichetat după instituție, facultate, program și tipul probei folosind inventarul public verificat. Consultă metodologia actuală a instituției pentru condițiile examenului viitor.

Există și barem sau răspunsuri pentru acest subiect?

Da. Pagina include baremul sau răspunsurile publice asociate acestui subiect, afișate separat ori în același document atunci când sursa le publică împreună. Verifică fiecare rezolvare după ce ai terminat varianta și urmărește exact criteriile de punctare indicate de instituție.

Cum folosesc acest subiect în pregătirea pentru admitere?

Rezolvă documentul fără ajutor și respectă timpul prevăzut de metodologia examenului. Corectează cu baremul disponibil, marchează capitolele unde ai pierdut puncte și repetă exerciții similare. Compară apoi cu alte probe din aceeași facultate și confirmă programa curentă pe site-ul oficial al instituției.

Pregătire cu un profesor

Subiect și barem

Concurs de pregătire · Informatică · 2021

Despre acest subiect

Subiectul și baremul în format text

Subiect · pagina 1