Lista de probleme

#686 grad

Se consideră o propoziţie formată din litere mici ale alfabetului englez şi eventual spaţii. Cuvintele sunt formate numai din litere şi sunt separate între ele prin unul sau mai multe spaţii.

Definim numărul asociat unui cuvânt c1c2...ck ca fiind un număr natural nc, obţinut ca produsul puterilor de forma pi, unde p este poziţia în alfabet a literei ci. Astfel cuvântului badab i se asociază numărul nc=21∙12∙43∙14∙25, adică nc=4096.

Definim gradul unui cuvânt c1c2...ck ca fiind numărul nr modulo k, unde nr este numărul de divizori al lui nc. Gradul cuvântului badab este 3, pentru că nr=13 (cei 13 divizori ai lui 4096 sunt: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 şi 4096), k=5 (cuvântul conţine 5 litere) şi 13 modulo 5=3.

Definim gradul unei propoziţii ca fiind suma gradelor cuvintelor existente în ea.

Să se scrie un program care pentru o propoziţie dată determină gradul ei.

Lot Juniori, Sibiu 2011

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.

OJI 2010, Clasa a VII-a

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

OJI 2009, Clasa a X-a

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

ONI 2014, Clasa a X-a

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.

ONI GIM 2014, Clasa a VII-a

Scrieți un program C/C++ care citește de la tastatură un text și îl transformă în memorie prin înlocuirea fiecărui cuvânt format din număr par de litere cu simbolul #.

Model bacalaureat

Dându-se o ecuaţie de gradul 2, să se scrie un program care determină soluţiile acestei ecuaţii.

Scrieţi un program care, citind de la tastatură cuvântul C, construieşte în memorie matricea reprezentării binare a cuvântului şi afişează pe ecran dimensiunea celei mai mari submatrici pătratice conţinând elemente având toate aceeaşi valoare (fie 0, fie 1).

Admitere Informatica Iasi, 2015

#1494 s_p_c

Scrieţi un program care citeşte din fişierul de intrare şiruri de caractere de forma cuvânt#tip, unde cuvânt este un şir oarecare de litere iar tip poate fi una din literele S, P sau C, semnificaţia fiind subiect, predicat sau complement. Programul va afişa, în ordine lexicografică, toate propoziţiile având structura subiect predicat complement ce pot fi formate cu ajutorul cuvintelor citite. Datele de intrare se consideră a fi corecte.

Admitere Informatica Iasi, 2012