Lista de probleme

#1896 ksir

Fie S un șir de caractere cu litere mici și litere mari. Se sortează în ordine lexicografică toate subsecvențele distincte ale lui S. Se dă un număr K și un vector k cu K numere întregi, se cere pentru fiecare număr cel de k i -lea subșir lexicografic.

Concursul de Informatica "Spiru Haret" Targu Jiu, ed. I

#1021 Cartite

Cârtițele sunt animale de dimensiuni mici care își duc traiul pe suprafețe de teren deschis, având ca dușman principal vulpea. Lângă o pădure se află o zonă agricolă în forma dreptunghiulară, împărțită în pătrățele de aceeași dimensiune. Zona agricolă este reprezentată printr-un tablou bidimensional cu M linii și N coloane, având liniile și coloanele numerotate începând cu 1. În aceasta zona agricolă trăiește o cârtiță și K vulpi.

Pentru cârtiță cunoaștem coordonatele ei (linia și coloana) pe care se găsește, la fel și pentru vulpi, care stau la pânda pentru a ataca cârtita în momentele ei de neatenție.
Pe suprafața terenului cârtita se poate deplasa din patrațelul în care se afla doar într-unul dintre cele 4 pătrățele vecine pe direcțiile nord, sud, est sau vest.
Vulpile pot ataca instantaneu pe o raza de acțiune de lungime 0, 1 sau 2 pe orizontala și verticala, inclusiv în poziția unde se găsesc, după care tot instantaneu se întorc în pozițiile inițiale. În figura de mai jos sunt desenate pătrățele unde poate ataca o vulpe poziționață în pătrățelul cu cifra reprezentând raza de acțiune.

Pentru a micșora riscul de deplasare în zona agricolă cârtița sapă în pământ un sistem de G galerii, care leagă între ele pătrățele din zona agricola. Aceste galerii nu se intersectează sub pamânt, ci doar la suprafață, trecerea dintr-o galerie în alta, care se intersectează în același pătrățel făcându-se printr-un sistem ce nu îi pune viata în pericol. Galeriile sunt indicate prin coordonatele pătrățelelor pe care le unesc. Acestea sunt săpate astfel încât, dacă pornim dintr-un capăt al unei galerii le putem parcurge pe toate. Nu exista doua galerii care sa pornească din același pătrățel și să ajungă tot în același pătrățel (galeriile sunt distincte).

Cârtița dorește sa se plimbe prin toate galeriile de sub teren trecând o singura data prin fiecare, dar pentru acest lucru trebuie sa ajungă nevătămată mergând la suprafața terenului la un pătrățel de unde să intre în sistemul de galerii.

Determinați:

1. cel mai apropiat pătrățel de poziția inițială a cârtitei prin care ea poate să intre în galerie pentru a se plimba, precum și lungimea traseului parcurs la suprafață astfel încât fiecare pătrățel de pe traseu sa nu fie atacat de nicio vulpe;
2. traseul de plimbare numai prin galerii, specificat prin coordonatele pătrățelelor care constituie capetelor acestora.

OJI 2014, Clasele XI-XII

Numărul 1 poate fi scris în diverse moduri ca sumă de fracţii cu numărătorul 1 şi numitorul o putere a lui 2. De exemplu:

1 = 1/2 + 1/2 = 1/2 + 1/4 + 1/8 + 1/8 = 1/8 + 1/4 + 1/2 + 1/8

Două scrieri nu sunt considerate distincte dacă folosesc aceleaşi fracţii scrise în altă ordine. În exemplul de mai sus ultimele două scrieri nu sunt distincte.

Pentru N – număr natural nenul să se determine:
a) O modalitate de scriere a numărului 1 ca sumă de exact N fracţii cu numărătorul 1 şi numitorul o putere a lui 2.
b) Numărul de scrieri distincte a numărului 1 ca sumă de exact N fracţii cu numărătorul 1 şi numitorul o putere a lui 2. Deoarece acest număr poate fi foarte mare acest număr trebuie calculat modulo 100003.

OJI 2014, Clasele XI-XII

Un vârcolac bântuie ulițele satului Bosston, semănând panică printre săteni. Satul Bosston este compus din 2*N săteni, fiecare dintre aceștia fiind rudă cu exact un vârcolac. Vârcolacii sunt codificați cu numere naturale. Pentru a afla care este vârcolacul care le cauzează probleme, aceștia s-au dus la vraciul local. Acesta a spus că, dacă există un vârcolac V astfel încât oricum s-ar împărți cei 2*N săteni în două grupuri de N săteni, există cel puțin un sătean în primul grup și cel puțin un sătean în al doilea care să fie rude cu V, atunci vârcolacul V sigur este cel care bântuie satul. Dacă nu există un astfel de vârcolac, atunci sătenii nu își pot da seama cine le bântuie satul.

Cunoscând N și indicii vârcolacilor cu care se înrudesc fiecare dintre cei 2*N săteni, să se determine vârcolacul care bântuie satul, în cazul în care acesta există.

ONI 2014, Clasele XI-XII

#1116 karb

În perioada Campionatului Mondial din Brazilia se preconizează o creştere a traficului de cafea. Se ştie că sunt N orase, conectate prin N-1 străzi bidirecţionale, astfel încât se poate ajunge din orice oraş în altul. În prezent există K carteluri de cafea aflate în oraşe distincte, care își exercita influența în propriul oraș. Se ştie că fiecare din aceste carteluri doreşte să-şi extindă influenţa în oraşele vecine. Astfel, la un moment de timp, un cartel poate să-şi extindă influenţa într-un oraş vecin doar dacă acesta nu se află sub influenţa altui cartel. O dată ce un cartel îşi extinde influenta asupra unui nou oraş, cartelul îşi poate extinde influenţa şi în oraşele vecine acestuia. Se ştie că până la începerea campionatului mondial, fiecare oraş va fi sub influenţa unui cartel.

ABIN (Agência Brasileira de Inteligência) doreşte să afle în câte moduri poate fi dominată ţara de influenţele celor K carteluri la data începerii campionatului mondial, modulo 666013.

Cunoscând numărul de orașe N, modul în care acestea sunt conectate, numărul de carteluri inițiale K și cele K orașe în care se află cartelurile, să se determine numărul de moduri în care ţara poate fi împărţită între cartelurile de cafea, modulo 666013.

ONI 2014, Clasele XI-XII

#1117 Volum

K.L. 2.0 și-a dorit o piscină pe un grid A cu N linii și M coloane. Cum K.L. 2.0 nu a fost foarte inspirat, el a uitat să își niveleze terenul înainte de a construi piscina, astfel încât fiecare celulă de coordonate (i, j) a gridului are o înalțime Ai,j (1 ≤ i ≤ N și 1 ≤ j ≤ M). La un moment dat începe o ploaie puternică, care umple piscina cu apă. După terminarea ploii, K.L. 2.0 se întreabă câtă apă are în piscină.

Dintr-o celulă apa se varsă în celulele vecine cu care are o latură comună şi care au înălţimea strict mai mică decât celula curentă. Apa de pe marginea piscinei se scurge în exterior.

Pentru N, M și gridul A date, să se determine volumul de apă care a rămas în piscină.

ONI 2014, Clasele XI-XII

Un graf conex cu N noduri și M muchii poate fi privit ca o clepsidră cu centrul în nodul X, 1 ≤ X ≤ N, dacă putem împărți toate nodurile, mai puțin nodul X, în două submulțimi nevide astfel încât orice drum de la un nod dintr-o mulțime la un nod din cealaltă mulțime trece prin nodul X. Voi trebuie să determinați numărul de moduri distincte în care putem privi graful ca o clepsidră pentru fiecare din cele N noduri alese drept centru, modulo 666013. Două moduri se consideră distincte dacă cele două submulțimi aferente sunt diferite. Ordinea submulțimilor într-un mod este relevantă, dar ordinea nodurilor în cadrul unei mulțimi nu este. Spre exemplu, soluțiile ({1,2,3}, {4,5}) şi ({4,5}, {1,2,3}) sunt distincte, dar soluţiile ({4,5}, {1,2,3}) şi ({4,5}, {1,3,2}) nu sunt distincte.

ONI 2014, Clasele XI-XII

Se dă o matrice cu m linii şi n coloane, fiecare linie reprezentând o permutare. Se ştie că liniile de la 2 la m sunt permutări circulare ale primei linii. Unei linii x (1 ≤ x ≤ m) i se pot aplica următoarele operaţii:

  • o permutare circulară la stânga: elementul de pe poziţia i (1 < i ≤ n) se mută pe poziţia i-1, mai puţin primul primul element, care devine ultimul;
  • o permutare circulară la dreapta: elementul de pe pozitia i (1 ≤ i < n) se mută pe poziţia i+1, mai puţin ultimul element care devine primul.

Scopul este să permutăm circular liniile, la stânga sau la dreapta, astfel încât în final toate liniile să fie egale, folosind un număr minim de operaţii.

Dându-se o matrice cu proprietatea din enunţ se cere să se determine numărul minim de operaţii necesare pentru a ajunge la o matrice în care toate liniile sunt egale.

ONI 2014, Clasele XI-XII

#1120 xcmmdc

Se dă o matrice cu m linii şi n coloane, cu elementele numere naturale nenule şi un număr natural nenul fixat k.

Pentru matricea dată şi numărul k dat să se răspundă la q întrebări de forma: “Câte submatrice pătratice de latură L cu cel mai mare divizor comun al elementelor egal cu k există în matricea dată?”

ONI 2014, Clasele XI-XII

#1135 p2sah

Se dă o tablă de șah cu n+1 linii (numerotate de sus în jos începând cu 1) și 2n+1 coloane (numerotate de la stânga la dreapta începând cu 1). Pe prima linie pătratul din mijloc conține 1 gram de fân, iar celelalte pătrate de pe prima linie nu conțin nimic. Începând cu linia a doua fiecare pătrat conține o cantitate de fân obținută prin adunarea cantităților de fân din cele 3 pătrate ale liniei anterioare cu care se învecinează (pe verticală și diagonală). De exemplu dacă n=3 tabla are 4 linii, 7 coloane și următoarea configurație.

Un cal pleacă de pe prima linie, de pe o coloana k<=n, sare din orice poziție (i,j) în poziția (i+1,j+2) atât timp cât este posibil și mănâncă tot fânul din pătratele prin care trece. De exemplu, pentru n=3 și k=2, pătratele prin care trece calul sunt marcate cu asterisc ( * )

Cerinţe:

1. Cunoscând n și k, să se calculeze cantitatea de fân de pe linia k a tablei.
2. Cunoscând n și k, să se calculeze câte grame de fân mănâncă un cal care pleacă de pe prima linie, de pe coloana k.

OJI 2015, Clasele XI-XII