#4617
parking
Mark a construit o parcare dreptunghiulară, pe care a împărțit-o, utilizând marcaje, în locuri de parcare pătrate, organizate pe n
linii (numerotate de la 1
la n
) și m
coloane (numerotate de la 1
la m
). Astfel, un loc de parcare poate fi identificat prin numărul liniei şi numărul coloanei pe care acesta se află. Orice mașină poate fi parcată în interiorul unui loc de parcare, paralel cu liniile orizontale de marcaj, sau paralel cu liniile verticale, fără a depăși conturul pătratului corespunzător.
Scrieți un program care, cunoscând dimensiunile parcării, pozițiile întreruperilor din zid, numărul de mașini, iar pentru fiecare mașină numărul liniei și al coloanei corespunzătoare locului în care este parcată și modul de parcare a acesteia, rezolvă următoarele două cerinţe:
1) determină numărul de mașini care pot ieși din parcare fără a fi condiționate de mutarea sau de părăsirea parcării de către alte mașini (numărul de maşini care pot ieşi în prima serie);
2) determină numărul total maşini care pot ieşi din parcare, precum şi numărul de serii în care se realizează ieşirea tuturor acestor maşini.
OJI 2024, clasa a 7-a
#4610
poseidon
În Tărâmul Magic al Insulelor, se desfășoară o vânătoare anuală de comori, unde echipele explorează insule fermecate, delimitate de apa ce le înconjoară. La ordinul regelui A., sunt ascunse comori pe fiecare insulă. Harta tărâmului este reprezentată sub forma unei matrice de dimensiune 𝑛 × 𝑚
, ale cărei elemente codifică zone pătratice, cu latura de 1 metru. Acestea pot fi:
−1
;0
; sauDouă zone se consideră vecine dacă au o latură comună. Două zone aparţin aceleiaşi insule dacă ele sunt vecine sau dacă se poate ajunge de la o zonă la cealaltă pe un drum care parcurge o succesiune de zone, oricare două zone parcurse consecutiv fiind vecine. În acest an, căpitanul Poseidon dorește să facă o farsă regelui A., permutând comorile, astfel încât fiecare comoară să fie mutată într-o zona în care inițial a fost o altă comoară. Totuși, pentru a nu atrage atenția prea mult, comorile vor rămâne în cadrul insulei pe care se aflau inițial
Pentru început, căpitanul Poseidon își propune să rezolve următoarele cerințe:
1 000 000 007
.OJI 2024, clasa a 10-a
#4608
aprogressive
Se consideră matricea 𝑇
cu 𝑛
linii (numerotate de la 1
la 𝑛
) și 𝑚
coloane (numerotate de la 1
la 𝑚
) ce conține numere întregi.
O submatrice a matricei 𝑇
este definită prin linia și coloana colțului stânga-sus (𝑥1, 𝑦1)
, respectiv linia și coloana colțului dreapta-jos (𝑥2, 𝑦2)
, cu 1 ≤ 𝑥1 ≤ 𝑥2 ≤ 𝑛
și 1 ≤ 𝑦1 ≤ 𝑦2 ≤ 𝑚
și conține toate elementele de pe pozițiile (𝑥, 𝑦)
ale matricei pentru care 𝑥1 ≤ 𝑥 ≤ 𝑥2
și 𝑦1 ≤ 𝑦 ≤ 𝑦2
. În particular, submatricea cu colțul stânga-sus în (1, 1)
și colțul dreapta-jos în (𝑛,𝑚)
este identică cu matricea 𝑇
.
Pentru fiecare linie a unei submatrice date, se calculează suma pe linie prin adunarea elementelor aflate pe aceasta. Sumele obținute pentru fiecare dintre liniile acestei submatrice formează termenii unui șir, numit șirul 𝑆
al sumelor pe linii. Spunem că submatricea este aprogressive dacă 𝑥1 < 𝑥2
și 𝑦1 < 𝑦2
și șirul 𝑆
al sumelor pe linii poate fi rearanjat pentru a forma, cu toți termenii săi, o progresie aritmetică de rație nenulă 𝑟
.
Forma comprimată a unei submatrice 𝑅
cu colțul stânga-sus (𝑥1, 𝑦1)
și colțul dreapta jos (𝑥2, 𝑦2)
se notează cu C(𝑅)
și se definește astfel:
𝑥1 = 𝑥2
(este o submatrice linie) sau dacă 𝑦1 = 𝑦2
(este o submatrice coloană) atunci forma sa comprimată este C(𝑅)= (𝑥1, 𝑦1, 𝑥2, 𝑦2, 0)
. În caz contrar,𝑅
este aprogressive, forma sa comprimată este C(𝑅)= (𝑥1, 𝑦1, 𝑥2, 𝑦2, 𝑟)
. În caz contrar,𝑅
în 4
submatrice 𝐴
, 𝐵
, 𝐶
, 𝐷
cu mulțimi disjuncte de elemente după cum este ilustrat în figura alăturată, unde submatricea 𝐴
are colțul stânga-sus în (𝑥1, 𝑦1)
, iar colțul dreapta-jos în \( \left( \left[ \frac{x1 + x2}{2} \right], \left[ \frac{y1 + y2}{2} \right] \right) \), \( \left[ x \right] \) reprezentând partea întreagă a numărului real 𝑥
. Forma comprimată a submatricei 𝑅
este definită recursiv C(𝑅) =(C(𝐴), C(𝐵), C(𝐶), C(𝐷))
.Cunoscând dimensiunile și elementele matricei 𝑇
să se determine:
𝑇
pentru care suma elementelor aflate pe fiecare dintre acestea este maximă.𝑇
pentru care elementele pot fi rearanjate astfel încât să formeze pe linia respectivă, o progresie aritmetică de rație nenulă.𝑇
.OJI 2024, clasa a 10-a
#4609
opsir
Se consideră o pereche de șiruri de caractere, 𝑆
și 𝑇
, de lungime 𝑛
, respectiv 𝑚
, formate exclusiv din litere mici ale alfabetului englez. Pozițiile literelor sunt numerotate în șir începând de la 1
.
Sunt două tipuri de operații ce se pot efectua asupra șirului 𝑇
:
1 𝑝
: se șterge litera de pe poziția 𝑝
;2 𝑠𝑡 𝑑𝑟
(cu 𝑠𝑡 ≤ 𝑑𝑟
): se sortează crescător (alfabetic) literele din subsecvența ce corespunde intervalului de poziții [𝑠𝑡, 𝑑𝑟]
;unde 𝑝
, 𝑠𝑡
și 𝑑𝑟
sunt poziții ale unor litere din șirul 𝑇
.
Inițial, toate literele șirului 𝑇
sunt necolorate. O operație de tip 2 poate fi realizată doar dacă toate literele din subsecvența corespunzătoare intervalului de poziții [𝑠𝑡,𝑑𝑟]
sunt necolorate. După efectuarea sortării, toate literele din această subsecvență devin colorate.
Pentru fiecare dintre perechile de șiruri de tipul 𝑆
și 𝑇
date:
𝑆
sau 𝑇
) în care apare de mai multe ori. În caz de egalitate, se alege șirul 𝑇
.𝑇
, care să îl transforme𝑆
. Să se afișeze DA
în cazul în care există o astfel de succesiune de operații, sau NU
înOJI 2024, clasa a 10-a
#4607
Astar
Se dă o hartă de NxN
care conține spații libere (notate cu '.'
) și spații ocupate (notate cu '#'
). Să se răspundă la Q
interogări de forma i1 j1 i2 j2
, unde se dorește să se afle distanța minimă de la celula (i1, j1)
la celula (i2, j2)
.
#4586
planar
În teoria grafurilor, un graf planar este un graf care poate fi încorporat într-un plan, adică poate fi desenat în plan în așa fel încât muchiile sale să se intersecteze doar în noduri. Cu alte cuvinte, aceste poate fi desenat în așa fel încât oricare două muchii să nu se intersecteze. Florin urmează în perioada 2023-2029 studii în informatică.
Fiind date NR = 2 * N
noduri fixe (asemănător cu ceasul clasic) în planul xOy și N
muchii, Florin vrea să determine numărul grafurilor distincte planare în care fiecare nod va avea gradul 1
. Scrieţi un program care să determine numărul de grafuri obținute de Florin.
OMI Iasi 2024
#4583
criptare2
Ana și Bogdan sunt pasionați de criptarea mesajelor. Ei au studiat mai multe metode de criptare. Ultimul algoritm pe care l-au studiat presupune să scrie un cuvânt cu litere mari ale alfabetului englez. Apoi, sub acest cuvânt să scrie toate permutările sale circulare cu o poziție spre stânga obținând astfel o matrice de caractere. Ordonează lexicografic liniile matricii, memorează ultima coloană și adaugă la finalul șirului astfel obținut numărul liniei pe care a ajuns cuvântul inițial, șirul rezultat fiind denumit cript-ul șirului inițial. Analizând matricea de caractere obținută ei au observat că în matrice se obțin submatrici cu proprietatea că în cele patru colțuri ale lor se află același caracter. Să se scrie un program care citește un număr natural c
, reprezentând cerința care trebuie să fie rezolvată, apoi citește un cuvânt. Programul rezolvă următoarele cerințe:
1. Dacă c = 1
, șirul citit este un cuvânt necriptat, programul va determina și va afișa cript-ul obținut conform algoritmului descris anterior.
2. Dacă c = 2
, șirul citit este un cript, programul va determina și va afișa cuvântul necriptat.
3. Dacă c = 3
, șirul citit este un cuvânt necriptat, programul va determina matricea de caractere obținută conform algoritmului descris anterior și va afișa numărul maxim de elemente dintr-o submatrice cu proprietatea că în colțurile sale se află același caracter.
OMI Iasi 2024
Se consideră o mulţime A
cu n
elemente (distincte).
Determinaţi numărul de posibilităţi de a scrie pe A
ca reuniune de m
mulţimi. Două moduri de scriere B1 U B2 U ... U Bm
şi C1 U C2 U ... U Cm
diferă dacă există cel puţin un indice i
din mulțimea {1,2 … m}
astfel încât mulţimile Bi
şi Ci
diferă prin cel puţin un element.
.campion
#4505
Mewtwo
Ash este un antrenor Pokemon ambițios, setându-și scopul să devină cel mai bun. Din păcate, rivalul său, Gary, a furat startul și are Pokemoni mai puternici decât cei ai lui Ash.
Totuși, Ash nu se va da bătut chiar așa ușor! Are un plan de bătaie: în aventurile sale a găsit o clădire misterioasă care poate fi reprezentată ca o matrice de N x M
, fiecare celulă reprezentând conținutul unei camere. În această clădire se află:
A
): Ash se află inițial în această camerăM
): cel mai puternic Pokemon cunoscut de om. Ash are deja un Master Ball, așa că îl va poate prinde pe Mewtwo cu ușurință.G
): a fost provocat de Ash la o bătălie de Pokemoni și îl așteaptă într-o anumită cameră_
): Ash poate accesa această cameră#
): Ash nu poate accesa această camerăPlanul său constă în a-l prinde pe Mewtwo, după aceea în a-l confrunta pe Gary. Ash se poate deplasa în cele patru direcții cardinale (N
, E
, S
, V
). Știind că o deplasare se face într-o secundă, determinați numărul minim de secunde în care Ash poate ajunge la Mewtwo, apoi la Gary.
#4487
moser
Se consideră un cerc. Pe cerc se desemnează N
puncte oarecare. Dacă tragem linii între toate perechile de puncte, care este numărul maxim de bucăți în care poate fi descompus cercul? Să se răspundă la Q
astfel de scenarii.