Lista de probleme 129

Filtrare

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

#1198 Sablon1

Se consideră alfabetul englez compus din literele mici, de la a la z.
Se numeşte cuvânt un şir finit, eventual vid, de litere din acest alfabet.
Se numeşte expresie şablon un şir de caractere din alfabet în care pot apărea și caracterele ? şi *.

Un cuvânt se potrivește cu o expresie șablon dacă se poate obține din aceasta astfel:

  • caracterul ? se înlocuiește cu o singură literă din alfabet;
  • caracterul * se înlocuiește cu un cuvânt oarecare, eventual vid;
  • din expresia șablon se poate elimina sau nu, înainte de a efectua înlocuirea caracterelor ? și *, un singur caracter de tip literă.

Considerându-se o expresie șablon și un șir de cuvinte, să se determine, pentru fiecare cuvânt în parte, dacă se potrivește sau nu cu expresia şablon dată.

#1219 Cript

Ilinca a citit despre criptarea mesajelor, acum dorește să comunice cu prietena ei Miruna numai prin mesaje criptate folosind un sistem propriu de criptare.

Ilinca ştie că fiecare caracter se reprezintă în memoria calculatorului pe 8 biți, în care se memorează scrierea în baza 2 a codului ASCII al caracterului respectiv. Pentru a cripta caracterul, Ilinca foloseşte o matrice pătratică având 8 linii (numerotate de la 0 la 7 de sus în jos) şi 8 coloane (numerotate de la 0 la 7 de la stânga la dreapta). Pe prima linie a matricei Ilinca scrie cei 8 biţi reprezentând scrierea în baza 2 a codului ASCII al caracterului, pe poziţia 0 fiind scrisă cifra cea mai semnificativă (corespunzătoare lui 27). Pe fiecare dintre următoarele 7 linii din matrice scrie permutarea circulară cu o poziție la stânga a liniei anterioare. Ordonează lexicografic liniile matricei formate și defineşte cript-ul caracterului ca fiind succesi­unea de biți reprezentată de ultima coloană din matrice, parcursă de sus în jos, urmată de indicele liniei din matrice pe care a ajuns după ordonarea lexicografică reprezentarea în baza 2 a codului ASCII al caracterului. Dacă există linii egale în matrice, după ordonarea lexicografică acestea îşi vor păstra ordinea relativă iniţială, astfel că linia conţinând reprezentarea în baza 2 a codului ASCII al caracterului va fi prima dintre acestea.

Pentru a cripta un mesaj, Ilinca scrie în ordine cript-urile caracterelor din mesajul respectiv.

Miruna cunoaşte sistemul de criptare al Ilincăi, ca urmare ştie să decripteze mesajele primite.

Scrieți un program care să rezolve următoarele două cerinţe:
1. citește un mesaj şi afişează mesajul criptat conform sistemului Ilincăi;
2. citeşte un mesaj criptat conform sistemului Ilincăi şi determină mesajul decriptat.

#1222 TV

Comisia Naţională a Audiovizualului (CNA) este autoritatea care coordonează activitatea posturilor media din România. Șeful CNA-ului dorește o statistică referitoare la publicitatea transmisă de posturile de televiziune. În acest scop, el primește pentru fiecare zi informații în următorul format: d hh:mm:ss, unde d este durata exprimată în secunde a publicității, iar hh:mm:ss este momentul de start al publicității (hh este ora, mm este minutul, iar ss este secunda). Observaţi că d este separat de hh printr-un singur spaţiu, iar următoarele valori sunt separate prin caracterul ':'.

De exemplu o linie de forma:

150 05:02:45

se interpretează astfel: există un post TV care a transmis publicitate cu durata de 150 secunde, ora de început fiind 5, 2 minute și 45 de secunde.

”Secunda de aur” este o secundă în care se difuzează cât mai multă publicitate, adică pe un număr maxim de posturi în acea secundă se transmite publicitate. Dacă sunt mai multe astfel de secunde, “secunda de aur” este considerată prima secundă cu această proprietate în derularea zilei.

Șeful CNA primește în fiecare dimineață lista cu activitatea din ziua anterioară ca o succesiune de linii, fiecare linie având forma descrisă mai sus.

Scrieţi un program care, cunoscând lista din ziua anterioară, să rezolve următoarele cerinţe:

  1. să determine durata totală în care niciun post de televiziune nu a difuzat publicitate;
  2. să determine care este “secunda de aur”.

ONI GIM 2015, Clasa a VII-a

#1536 Ecuatii

Să considerăm ecuaţii de gradul I, de forma: expresie_1=expresie_2. Expresiile specificate sunt constituite dintr-o succesiune de operanzi, între care există semnul + sau semnul - (cu semnificaţia binecunoscută de adunare, respectiv scădere). Fiecare operand este fie un număr natural, fie un număr natural urmat de litera x (litera x reprezentând necunoscuta), fie doar litera x (ceea ce este echivalent cu 1x).

De exemplu: 2x-5+10x+4=20-x. Observaţi că în ecuaţiile noastre nu apar paranteze şi necunoscuta este întotdeauna desemnată de litera mică x.

Scrieţi un program care să rezolve ecuaţii de gradul I, în formatul specificat în enunţul problemei.

#2168 dir

Costel trebuie să realizeze, împreună cu echipa sa, o aplicaţie software pentru gestiunea fişierelor de pe hard-disc, sarcina sa fiind aceea de a scrie un modul pentru determinarea căilor tuturor fişierelor de date aflate în structura arborescentă a folderelor de pe disc. Membrii echipei au stabilit o codificare proprie pentru memorarea structurii fişierelor de pe disc, utilizând un şir de caractere. Scrieţi un program care, cunoscând şirul de caractere ce codifică o structură de fişiere de pe disc, determină calea pentru fiecare fişier de date din structură. Prin cale a unui fişier se înţelege o succesiune de foldere, fiecare folder fiind urmat de caracterul \(backslash), începând de la folderul aflat pe cel mai înalt nivel al structurii (primul specificat în şirul ce codifică structura de fişiere), până la subfolderul în care se află fişierul de date respectiv şi terminată cu numele fişierului. Căile determinate vor fi afişate în ordine lexicografică.

#1098 Reteta

Mama mea este profesoară de informatică, dar îi place foarte mult să gătească. Recent am descoperit caietul ei de reţete, care arată foarte neobişnuit. Fiecare reţetă este scrisă pe un singur rând pe care sunt precizate produsele folosite, cantităţile, precum şi ordinea în care se execută operaţiile. De exemplu:
(unt 50 zahar 250 ou 4)5
ceea ce înseamnă că se amestecă 50 grame unt cu 250 grame zahăr şi cu 4 ouă timp de 5 minute. Pentru fiecare produs mama foloseşte întotdeauna aceeaşi unitate de măsură, aşa că unităţile de măsură nu mai sunt precizate. Numele produsului este scris întotdeauna cu litere mici, iar produsele şi cantităţile sunt separate prin spaţii (unul sau mai multe). Produsele care se amestecă împreună sunt încadrate între paranteze rotunde; după paranteza rotundă închisă este specificat timpul de preparare.

Evident, mama are şi reţeţe mai complicate:
(((zahar 100 ou 3)5 unt 100 nuca 200)4 (lapte 200 cacao 50 zahar 100) 3)20

Să traducem această reţetă: se amestecă 100 grame zahăr cu 3 ouă timp de cinci minute; apoi se adaugă 100 grame unt şi 200 grame nucă, amestecând totul încă 4 minute. Se amestecă 200 ml lapte cu 50 grame de cacao şi 100 grame zahăr timp de 3 minute, apoi se toarnă peste compoziţia precedentă şi se amestecă totul timp de 20 minute.

Observaţi că înainte sau după parantezele rotunde pot să apară sau nu spaţii.

Dată fiind o reţetă să se determine timpul total de preparare, precum şi cantităţile necesare din fiecare produs.

Se consideră un şir de cuvinte separate două câte două printr-un spaţiu. Fiecare cuvânt este caracterizat prin numărul de ordine care reprezintă poziţia lui în şirul de cuvinte (primul cuvânt are numărul de ordine 1). Unui cuvânt i se pot aplica în mod repetat următoarele transformări: primul caracter al cuvântului (cel mai din stânga) se şterge de acolo şi se adaugă după ultimul caracter din cuvânt. Astfel, dintr-un cuvânt s cu k caractere se pot obţine alte k-1 cuvinte pe care le numim cuvinte obţinute din transformarea cuvântului s. De exemplu, dintr-un cuvânt format din 4 caractere c1c2c3c4, cuvintele obţinute prin transformarea lui sunt: c2c3c4c1, c3c4c1c2, c4c1c2c3.

Se caută în şirul de cuvinte prima pereche de cuvinte vecine (a,b), în care al doilea cuvânt din pereche (cuvântul b) este identic cu un cuvânt obţinut din transformarea lui a. Dacă există o astfel de pereche, se şterge cuvântul b din şir. Prin ştergerea cuvântului b din şir, acesta va avea mai puţin cu un cuvânt! Se repetă operaţia de căutare de mai sus până când în şirul rămas nu mai există o pereche (a,b) de cuvinte vecine, astfel încât b să fie obţinut prin transformarea lui a.

Se ştie că pe parcursul modificărilor, cuvintele nu-şi schimbă numerele de ordine pe care le-au avut iniţial.

Scrieţi un program care să citească şirul de cuvinte şi să afişeze:

a) numărul de ordine al primului cuvânt şters sau valoarea 0 în cazul în care nu se şterge niciun cuvânt
b) numerele de ordine ale cuvintelor rămase după finalizarea operaţiilor de modificare.