Lista de probleme 974

Se consideră trei numere naturale nenule n, k și w.

Să se scrie un program care determină numărul m al mulțimilor de forma {x[1], x[2],… , x[k]} având ca elemente numere naturale nenule, ce satisfac simultan condițiile:

• 1 ≤ x[1] < x[2] < ... < x[k] ≤ n
• x[i+1] - x[i] ≥ w, 1 ≤ i ≤ k - 1

Definim o modificare procentuală de preț ca fiind o pereche (c p) formată dintr-un caracter din {‘+‘,‘-‘} și un număr natural p. Dacă c = ‘+‘ atunci are loc o scumpire iar dacă c = ‘-‘ atunci are loc o ieftinire a unui preț, iar numărul p reprezintă procentul de modificare a prețului.

Exemple de modificări procentuale de preț: (+ 35) – reprezintă scumpirea unui preț cu 35%; (– 50) – reprezintă ieftinirea unui preț cu 50%.

Unui preț inițial i se poate aplica o succesiune de n modificări procentuale de preț obținându-se un preț final. Numim ciclu de preț de lungime n o succesiune de n modificări procentuale de preț, cu proprietatea că prețul final este egal cu prețul inițial.

Să se scrie un program care citește un număr natural n și determină numărul de cicluri de preț de lungime n distincte ce conțin cel puțin o dată o modificare procentuală cunoscută (C P).

Ne aflăm în secția de vopsitorie a uzinei Toyota Motor unde inginerii japonezi prezintă ultimul tip de robot industrial de vopsire. În dorința de a evidenția calitatea și viteza de execuție a roboților, inginerii folosesc pentru demonstrație o tablă de dimensiunea n×n, împărțită în pătrate cu latura egală cu 1, reprezentată sub forma unui tablou bidimensional cu n linii şi n coloane.

Un robot utilizat pentru vopsire are două brațe telescopice care se deplasează de-a lungul unei axe. Fiecare braț poate vopsi într-o unitate de timp un singur pătrat. La momentul de timp t=0 robotul primește comanda de a se poziționa într-un pătrat specificat prin coordonatele (x,y).

În funcție de traiectoria de deplasare roboții folosiți sunt de două tipuri. La momentul de timp t robotul de tip 1 vopsește pătratele aflate la coordonatele: (x-t,y+t) și (x+t,y-t), iar robotul de tip 2 vopsește pătratele aflate la coordonatele: (x+t,y+t) și (x-t,y-t). Pentru vopsirea unui pătrat se consumă 1 litru de vopsea.

Pe tablă sunt așezați m roboți.

Cunoscând pentru cei m roboți coordonatele inițiale (x[i],y[i]), i=1,…,m, se cere să se determine:

a) Cantitatea totală de vopsea care a fost folosită de roboți după t unități de timp
b) Numărul minim de unități de timp necesare formării primului dreptunghi cu arie nenulă. Un dreptunghi corect format este rezultatul intersecției a două traiectorii paralele a doi roboți de tip 1 cu două traiectorii paralele a doi roboți de tip 2, iar colțurile dreptunghiului sunt 4 pătrate care au fost vopsite de doi roboți de tipuri diferite.

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

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.

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.

Fie n un număr natural nenul.

Să considerăm o expresie de forma: x[1]-x[2]-x[3]-...-x[n]

Se ştie că scăderea nu este o operaţie asociativă, adică x[1]-(x[2]-x[3])≠(x[1]-x[2])-x[3].

Ca urmare, prin plasarea unor perechi de paranteze în expresie, putem obţine diferite valori.
Pentru problema noastră, vom denumi scădere o expresie de forma de mai sus în care pot apărea şi paranteze rotunde care se închid corect. Valoarea unei scăderi se obţine efectuând operaţiile de scădere în ordine de la stânga la dreapta; dacă apar paranteze, se efectuează mai întâi operaţiile din paranteze.

Date fiind valorile x[1], x[2], …, x[n] care intervin în scădere, scrieţi un program care să rezolve următoarele două cerinţe:

1. să se determine valoarea maximă a unei scăderi (obţinută prin inserarea convenabilă a unor paranteze rotunde în expresia x[1]-x[2]-x[3]-...-x[n]), precum şi o scădere având valoare maximă.
2. să se determine valoarea unei scăderi specificate.

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

Pentru obținerea Pietrei Filosofale, un alchimist a preparat un elixir folosind un creuzet de capacitate C, în care a turnat picături de metal topit, într-o ordine bine stabilită, în N etape. Numărul de picături turnate într-o etapă este cuprins între 0 și C-1, iar procesul începe când în creuzet s-a turnat prima picătură (în prima etapă numărul de picături turnate este nenul). Picăturile se adună în creuzet una câte una şi, de fiecare dată când acesta se umple complet, alchimistul rosteşte o formulă magică, provocând transformarea întregului conţinut într-o singură picătură, apoi continuă procesul. O rețetă de obținere a elixirului se exprimă printr-un șir de N numere, reprezentând numărul de picături turnate în cele N etape.

De exemplu, aplicând rețeta 5 6 1 0, cu un creuzet de capacitate C=7, în cele N=4 etape procesul este:

• etapa 1: se toarnă 5 picături;
• etapa a 2-a: se toarnă 6 picături, astfel: după primele 2 picături se umple creuzetul (5+2=7) și deci se rosteşte formula magică, în creuzet rămânând o picătură; se continuă cu celelalte 4 picături; la finalul etapei în creuzet sunt 5 picături (1+4=5);
• etapa a 3-a: se toarnă o picătură; la finalul etapei în creuzet sunt 6 picături (5+1=6);
• etapa a 4-a: se toarnă 0 picături; după ultima etapă creuzetul conține 6 picături (6+0=6).

O rețetă care corespunde Pietrei Filosofale trebuie să conducă, la finalul aplicării ei, la obținerea unei singure picături, chintesența metalelor amestecate. Bineînțeles, sunt mai multe astfel de rețete.

Fiind un tip responsabil, alchimistul a lăsat posterității un set de tratate, care cuprind toate aceste rețete. El a scris pe fiecare pagină câte o rețetă, astfel încât niciuna să nu se repete în cadrul întregii lucrări. Pe vremea aceea erau meșteri pricepuți, care fabricau tratate de dimensiuni corespunzătoare, încât fiecare pagină să poată cuprinde o rețetă ca a noastră, oricât de lungă ar fi ea. Fiecare tratat are P pagini și doar după ce completează toate cele P pagini ale unui tratat, alchimistul începe un nou tratat.

Se cere numărul de rețete publicate în ultimul tratat.

Gigel si Ionel se joacă de-a spionii! De aceea ei imaginează o modalitate de a codifica un mesaj astfel încât nimeni să nu îl poată descifra. Toate mesajele lor au lungimea o putere a lui 2. Ei numerotează literele mesajului începând cu 1. Apoi separă literele în două categorii: cele cu număr de ordine impar în stânga, cele cu număr de ordine par în dreapta, păstrând ordinea lor. Procedeul continuă pentru fiecare grupă nou rezultată începând cu cea din stânga, până când fiecare grupă obţinută conţine un singur caracter. După terminarea operaţiilor alipesc grupele de câte o literă rezultate, începând de la stânga spre dreapta şi obţin mesajul codificat.

De exemplu pentru mesajul MESAJNECODIFICAT procedează astfel:
1. numerotează

MESAJNECODIFICAT
123456789...

2. separă

MSJEOIIA                   EANCDFCT            apoi repetă paşii 1 şi 2 pentru 
12345678                   12345678            fiecare grupă rezultată

MJOI        SEIA           ENDC       ACFT
1234        1234           1234       1234

MO   JI     SI   EA        ED  NC     AF  CT
12   12     12   12        12  12     12  12

M O  J I    S I  E A       E D  N C   A F  C T
1 2  1 2    1 2  1 2       1 2  1 2   1 2  1 2    

până se obţine un singur caracter în fiecare grupă şi alipind literele de la stânga spre dreapta rezultă mesajul codificat: MOJISIEAEDNCAFCT

Scrieţi un program care să rezolve următoarele două cerinţe:

1. dat fiind un mesaj, să determine codificarea acestuia;
2. dat fiind un mesaj codificat, să determine decodificarea acestuia.