Lista de probleme 974

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

Parcul oraşului a fost neglijat mult timp, astfel că acum toate aleile sunt distruse. Prin urmare, anul acesta Primăria şi-a propus să facă reamenajări. Parcul are forma unui pătrat cu latura de n metri și este înconjurat de un gard care are exact două porți. Proiectanții de la Primărie au realizat o hartă a parcului și au trasat pe hartă un caroiaj care împarte parcul în nxn zone pătrate cu latura de 1 metru. Astfel harta parcului are aspectul unei matrice pătratice cu n linii și n coloane. Liniile și respectiv coloanele sunt numerotate de la 1 la n. Elementele matricei corespund zonelor pătrate de latură 1 metru. O astfel de zonă poate să conțină un copac sau este liberă. Edilii orașului doresc să paveze cu un număr minim de dale pătrate cu latura de 1 metru zonele libere (fără copaci) ale parcului, astfel încât să se obțină o alee continuă de la o poartă la alta. Scrieți un program care să determine numărul minim de dale necesare pentru construirea unei alei continue de la o poartă la cealaltă.

Maria pleacă în excursie la munte. Traseul de la baza muntelui și până la vârf trece printr-o serie de parcele organizate într-o matrice pătratică de dimensiune nxn. Baza muntelui se consideră primul element al matricei, iar vârful, ultimul element. Se cunoaște faptul că traseele de la bază până la vârf au numai suișuri. Maria dispune de un altimetru prin intermediul căruia poate determina altitudinea la care se găsește parcela pe care se află. Ea nu-și propune să urce până la vârf, ci doar până la o anumită altitudine. Cunoscând valoarea n, harta de dimensiune nxn cu altitudinile precizate și x o valoare ce reprezintă altitudinea la care trebuie să ajungă Maria, se cere să se determine coordonatele parcelei cu altitudinea x.

Fie n un număr natural nenul.

Se construiește mulțimea M a tuturor numerelor formate din exact n cifre, numere formate doar cu cifrele 1 și 2.

Scrieți un program care citește numărul natural n și apoi determină cel mai mic număr natural x din mulțimea M cu proprietatea că x este divizibil cu 2n.

Ana şi Bogdan au inventat încă un joc. Jocul are jetoane, albe şi negre, care iniţial se aşază într-un teanc, într-o ordine oarecare. Numim configuraţie succesiunea culorilor tuturor jetoanelor din teanc (în ordine, începând din vârful teancului). Un jeton alb va fi codificat prin litera A, iar un jeton negru prin litera N.

La o mutare un jucător poate lua din vârful teancului oricâte jetoane consecutive (dar cel puţin un jeton), cu condiţia ca toate jetoanele luate să aibă aceeaşi culoare. Jucătorii mută alternativ, prima la mutare fiind Ana. Jocul va fi câştigat de jucătorul care ia ultimul jeton.

Spunem că un jucător are strategie sigură de câştig dacă el, urmând această strategie, câştigă jocul, indiferent care sunt mutările celuilalt jucător.

Scrieţi un program care citeşte T configuraţii şi determină pentru fiecare dintre cele T configuraţii dacă Ana are strategie sigură de câştig.

SLang este o versiune a aplicației Scratch care pune la dispoziție șapte instrucțiuni de tip I1, I2, I3, I4, I5, I6, I7 prezentate în enunț.

Un program corect este o succesiune de instrucţiuni care respectă următoarele reguli:

1. Începe cu o instrucțiune de tip I1 şi se termină cu o instrucțiune de tip I7.
2. Între instrucţiunea de tip I1 şi instrucţiunea de tip I7 vor exista una, două sau mai multe instrucţiuni de tipurile I2, I3, I4, I5 sau I6, fără a utiliza două instrucţiuni de acelaşi tip; fiecare dintre aceste instrucţiuni poate să conţină alte instrucţiuni, conform cu regulile specificate.
3. Corpul unei instrucțiuni de tip I4 poate conține una sau două instrucțiuni de mișcare (adică de tip I2 sau I3) și nu poate conține instrucțiuni de alt tip.
4. Fiecare dintre cele două ramuri ale unei instrucțiuni de tip I5 (ramura daca şi ramura daca nu) poate conține una sau două instrucțiuni de tip I2 sau I3 și nu poate conține instrucțiuni de alt tip.
5. Corpul unei instrucțiuni de tip I6 poate conține una, două sau mai multe instrucţiuni de tipurile I2, I3, I4, I5 sau I6, fără a utiliza două instrucţiuni de acelaşi tip; similar, fiecare dintre aceste instrucţiuni poate să conţină alte instrucţiuni, conform cu regulile specificate.

Nivelul de imbricare al unui program corect va fi egal cu numărul de instrucţiuni de tip I6 existente în program.

Dat fiind numărul natural K, reprezentând nivelul de imbricare, scrieţi un program care să rezolve următoarele cerinţe:

1. determină numărul de programe corecte distincte cu nivelul de imbricare K;
2. determină numărul minim de instrucțiuni și respectiv numărul maxim de instrucțiuni ce pot exista într-un program corect cu nivel de imbricare K.

Se consideră un șir de caractere format din litere mici ale alfabetului englez. Să se determine lungimea minimă a unei secvențe care conține toate literele întâlnite în șirul inițial.

Să considerăm N variabile, denumite cu litere mici ale alfabetului englez, începând cu litera a. Să considerăm de asemenea M relaţii de ordine între aceste N variabile, sub forma: var1>var2 sau var1<var2, unde var1 şi var2 sunt două nume de variabile (deci litere mici distincte dintre primele N litere ale alfabetului englez).

Scrieţi un program care să ordoneze crescător cele N variabile pe baza celor M relaţii cunoscute.

Se consideră un șir de caractere format din N caractere literă mare ale alfabetului englez. Șirul poate fi rotit circular spre stânga cu k poziții.

Să se determine poziția minimă k cu care poate fi rotit circular spre stânga șirul inițial astfel încât șirul obținut să fie minim lexicografic.

Pentru a exprima starea de spirit în comunicarea online sunt utilizate emoticonurile (cunoscute şi sub denumirea de smileys). În mod text, un smiley este reprezentat ca o secvenţă de caractere.

Dat fiind un text, să se determine numărul de smileys care apar în text.