Lista de probleme 8

În orașul Beclean există N clădiri, numerotate de la 1 la N, înălțimile acestora fiind date de șirul H: H[1] este înălțimea primei clădiri, H[2] este înălțimea celei de a doua clădiri, ș.a.m.d.
Pentru oricare două clădiri i, j cu i < j definim gradul de diferențiere ca fiind diferența în valoare absolută dintre înălțimile celor două clădiri, deci grad(i,j) = |H[i] - H[j]|.
Arhitectul Gigel vrea să construiască o nouă clădire, care să se integreze optim în peisajul urban, însă nu este sigur care ar trebui să fie înălțimea ei. Pentru a se decide, Gigel vă roagă să aflați care este al K-lea cel mai mic grad de diferențiere dintre oricare două clădiri din cele date.

Pentru un șir de N clădiri cu înălțimi cunoscute, aflați care este al K-lea cel mai mic grad de diferențiere.

Paul a scris pe o foaie un șir numere naturale. Ionel a copiat șirul de numere pe altă foaie, dar a uitat să lase spații între numere, astfel că a obținut un număr foarte lung. Mihai a împărțit numărul scris de Ionel în numere cu K cifre, eventual cu excepția ultimului, care poate avea mai puțin de K cifre.

Determinați:

1. Cel mai mare număr scris de Paul.
2. Câte cifre are numărul scris de Ionel.
3. Care este suma numerelor scrise de Mihai.

În curtea școlii, N copii stau așezați în cerc; pe tricouri sunt scrise, în ordine, numerele de la 1 la N și fiecare copil ține în mână un cartonaș cu un număr natural nenul.

Ei decid să joace un joc de echipă care necesită multă răbdare. Regula jocului este următoarea:

• la fiecare pas:
  • se alege copilul care are cel mai mic număr scris pe cartonaș; dacă sunt mai mulți copii cu același număr minim, va fi ales copilul care are pe tricou un număr mai mic.
  • copilul ales trebuie să adune la valoarea curentă de pe cartonașul său valoarea pe care a avut-o la începutul jocului.
• jocul se termină atunci când toți copiii au pe cartonașe aceeași valoare.

Cunoscând numărul de copii N și numerele inițiale de pe cartonașe, scrieți un program care să determine:

• Care este valoarea finală la care vor ajunge toți copiii la finalul jocului?
• Care este numărul total de pași efectuați până la finalul jocului?
• Pentru un număr K dat, care este copilul ales la pasul K?

Cifrul este un număr natural și este corect dacă și numai dacă oricare două cifre consecutive ale sale se află în terminal pe poziții vecine pe linii sau pe coloană.

Gigel, informaticianul băncii, trebuie să răspundă la două întrebări:

1) Dându-se configuratia a T terminale, să se determine câte sunt valide.
2) Dându-se un terminal valid și N numere naturale, să se stabilească pentru fiecare dacă reprezintă un cifru corect în raport cu terminalul dat.

Scrieți un program care să îl ajute pe Gigel să răspundă la întrebări.

După ce în timpul vacanței, Alex a vizionat filmul The Good, The Bad and The Ugly, el a descoperit o proprietate interesantă a numerelor naturale, aceea de a fi număr bun sau număr rău.

Pentru a determina dacă un număr X este bun sau rău, Alex procedează astfel:

• Determină lista divizorilor naturali ai numărului X;
• Apoi, el calculează suma pătratelor acestor divizori;
• În final, însumează cifrele sumei rezultate și notează acest rezultat cu S;
• Dacă S este par, atunci Alex va ști că numărul dat este bun;
• Dacă S este impar, atunci X va fi rău.

Alex primește cadou un șir A cu N numere naturale. Spunem că o secvență a șirului A este rea, dacă și numai dacă ea este alcătuită doar din numere rele.

Acum, prietenii lui care nu au vizionat filmul îi pun mai multe întrebări.

1. Mihai vrea să afle care este cel mai mare număr prim din șirul dat.
2. Răzvan se întreabă câte numere bune sunt în vectorul A.
3. Adelin cere găsirea celei mai lungi secvențe rele din șir.

Mihai decide că e vremea să își construiască propria casă și are nevoie de un arhitect priceput. Auzind el despre arhitectul Gigel, intenționează să îl contacteze. Construirea unei case fiind o chestiune serioasă, Mihai vrea să testeze competențele lui Gigel și îi pregătește mai multe întrebări de următoarele două tipuri:

• Tipul 1: O cameră cu suprafața N trebuie împărțită în zone cu aceeași suprafață, număr natural. În câte moduri se poate face această împărțire?
• Tipul 2: Două camere cu suprafețele a și b pot fi vecine doar dacă a și b au un divizor comun mai mare decât 1. Câte perechi numere naturale din intervalul [1, N] pot fi suprafețele unor camere vecine?

Scrieți un program care citește Q astfel de întrebări și care afișează răspunsurile la fiecare dintre ele.

Ira iubește să se joace pe telefon. Atât de mult, încât părinții au luat decizia să îi blocheze telefonul pentru a se concentra la școală. Fiind fată isteață, ea a descoperit cum poate debloca telefonul de una singură.

Pe ecranul telefonului îi apar mai multe informații:

• un număr natural N
• un șir A cu N numere naturale, numerotate de la 1 la N
• un număr natural K
• un număr natural Q, apoi Q numere x, reprezentând un indice din șirul dat.

Pentru a-și putea continua jocul ea trebuie sa răspundă corect la toate cele Q întrebări de tipul: Care este diferența între cel mai mare și cel mai mic element din secvență care începe la poziția x și are lungime k?

Scrieți un program care citește datele și răspunde corect la toate cele Q întrebări. Ira abia așteaptă să se joace din nou pe telefon!

Se dă o rețea de N * M calculatoare, dispuse sub forma unei matrici cu N linii și M coloane, numerotate începând cu 1, între care se pot transfera informații.

Fiecare calculator funcțional are asociat un cod, număr natural. Calculatoarele defecte sunt marcate cu -1 și nu pot participa la transferul de informație.

Transferul de informație între două calculatoare funcționale se face direct, dacă acestea sunt vecine, sau indirect, prin intermediul altor calculatoare funcționale. Două calculatoare sunt vecine dacă se află pe aceeași linie și coloane adiacente sau pe aceeași coloană și linii adiacente, adică calculatorul de la poziția (i, j) este vecin cu cel de la pozițiile: (i + 1, j), (i - 1, j), (i, j + 1) sau (i, j - 1).

Costul transferului de informație între două calculatoare vecine funcționale este 0, dacă cele două coduri diferă prin cel mult un bit în reprezentarea binară, respectiv 1, în caz contrar. Costul transferului de informație între două calculatoare care nu sunt vecine este suma costurilor transferurilor directe intermediare.

Scrieți un program care să determine costul minim necesar pentru transferul informației de la calculatorul de pe poziția (1, 1) la cel de pe poziția (N, M).