Lista de probleme 31

Etichete

#1111 Zimeria

Olimpia D’Info a găsit o placă gravată ce conţine mai multe cuvinte scrise cu semne grafice necunoscute, fiecare cuvânt fiind format din exact 5 semne grafice. Studiind cu atenție cuvintele, a dedus că în scrierea acestora sunt utilizate 12 semne grafice distincte şi a asociat câte o literă mică din alfabetul englez fiecărui semn. După asociere, a stabilit pentru fiecare semn o complexitate, scriind literele în ordinea crescătoare a complexităților pe care le-a stabilit anterior. Olimpia consideră că această ”complexitate” este cel mai potrivit criteriu de ordonare lexicografică.

Cunoscând ordinea semnelor și cuvintele de pe placă determinaţi:
a) Numărul de cuvinte distincte existente pe placă.
b) Şirul de cuvinte ordonat lexicografic, conform criteriului formulat de Olimpia.

Se presupune că unele dintre primele instrumente de calcul au fost beţişoarele de socotit. În problema noastră vom considera un număr ca fiind o succesiune de unul sau mai multe beţişoare, un beţişor fiind reprezentat de litera I. Într-o expresie, între oricare două numere există semnul + sau semnul *.

Exemple de numere

I
III
IIIIIIIIIII

Exemple de expresii

III
II*III
I+I*III+IIIIIII

Scrieţi un program care evaluează astfel de expresii.

ONI GIM 2014, Clasa a VI-a

#1205 Nod

Pe vremea maurilor, transmiterea unor mesaje codificate între două persoane se făcea folosind un cifru numit nod. Cele două persoane alegeau în secret o poveste. Aceasta era scrisă într-o carte folosind litere mici și mari ale alfabetului englez, pe P pagini, numerotate de la 1 la P, fiecare conținând exact R rânduri, numerotate în cadrul fiecărei pagini de la 1 la R, iar fiecare rând fiind format din exact C cuvinte, numerotate în cadrul fiecărui rând de la 1 la C.

Un cuvânt al mesajului de transmis era codificat prin poziția sa în povestea aleasă de cei doi, folosind trei numere scrise cu cifre romane, ce indicau în ordine: numărul paginii, numărul rândului în cadrul paginii, respectiv al cuvântului în cadrul rândului.
Mesajul astfel codificat era scris pe trei linii. Pe prima linie erau scrise numerele paginilor, pe a doua linie numerele rândurilor, iar pe a treia linie erau scrise numerele de ordine ale cuvintelor.

Presupunem că mesajul este format din primul cuvânt de pe al cincilea rând al celei de a doua pagini și din al patrulea cuvânt de pe rândul al doilea al primei pagini. Mesajul putea fi transmis pe trei linii în modul următor:

  • II I (numerele paginilor)
  • V II (numerele rândurilor)
  • I IV (numerele cuvintelor)

Cifrele romane sunt scrise cu majusculele M, D, C, L, X, V, I, iar valorile corespunzătoare lor sunt în ordine: 1000, 500, 100, 50, 10, 5, 1. Valoarea unui număr scris cu cifre romane se calculează parcurgând de la stânga la dreapta cifrele numărului astfel:

  • cifra curentă se adună la valoarea obținută până în acel moment, dacă cifra următoare este mai mică sau egală cu ea;
  • cifra curentă se scade din valoarea obținută până în acel moment, dacă cifra următoare este mai mare decât ea;
  • ultima cifră se adună întotdeauna la valoarea obținută până în acel moment.

De exemplu pentru numărul MCDXLVI scris cu cifre romane, se obține valoarea 1446 în sistem zecimal, astfel: 1000-100+500-10+50+5+1, iar pentru numărul XXI scris cu cifre romane se obține valoarea 21 în sistemul zecimal astfel: 10+10+1.

Cunoscându-se textul poveștii ales de cei doi și mesajul codificat de ei scrieți un program care rezolvă următoarele două cerințe:

a) Rescrie mesajul codificat folosind scrierea cu cifre din sistemul zecimal.
b) Afișează toate cuvintele mesajului decodificat în ordinea în care acestea apar în poveste.

#694 sam

Aranjăm primele N numere naturale nenule sub forma unui șir A[1], A[2], ..., A[N].

Fie X[1], X[2],...,X[K] (K ≥ 3), un subșir al șirului A. Numim extrem local al subșirului X termenul din mijlocul unei secvențe de lungime trei din subșir, X[i-1], X[i], X[i+1], cu proprietatea: X[i-1]<X[i]>X[i+1], 1<i<K sau X[i-1]>X[i]<X[i+1], 1<i<K.

Vom nota cu nrex(X) numărul de extreme locale ale subșirului X.

Spunem că un subșir X[1], X[2],...,X[K] (K≥2) al șirului A este subșir alternant dacă nrex(X)=K-2, adică exceptând primul și ultimul termen din subșir toți ceilalți termeni sunt extreme locale ale subșirului X.

Dintre toate subșirurile alternante ale șirului A ne interesează cele de lungime maximă pe care le vom numi subșiruri alternante maximale.

Cunoscând N și tabloul A se cere să se determine restul obținut la împărțirea dintre numărul M al subșirurilor alternante maximale ale tabloului A și numărul 1000003.

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ă.

#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ă.

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

#1207 Cifre9

Maia tocmai a învăţat la şcoală să facă adunări cu numere naturale având mai multe cifre. Pentru că îi place foarte mult matematica s-a apucat să scrie pe o foaie multe numere naturale, cu una sau mai multe cifre, şi a început să le adune.

După o vreme s-a cam plictisit şi s-a gândit să afle cea mai mare sumă ce s-ar putea obţine dacă s-ar schimba între ele cifrele numerelor de pe foaie. Are însă o singură dorinţă: după ce schimbă cifrele între ele să rămână acelaşi număr de numere cu o cifră, acelaşi număr de numere cu două cifre şi aşa mai departe.

Cerinţe

Scrieţi un program care să determine

a) suma maximă ce se poate obţine schimbând între ele cifrele numerelor iniţiale;
b) un şir de numere pentru care se obţine suma maximă, respectând restricţiile din enunţ.

#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.

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.