Lista de probleme 12

Terminalul unui aeroport este o sală foarte mare având forma unui dreptunghi împărțit în pătrate cu latură unitară. Aici se află mai multe persoane, care trebuie să poarte la vedere un ecuson cu un cod de bare care poate fi citit în orice moment de camerele de supraveghere și decodificat de calculatoarele serviciului de protecție și pază. Într-un pătrat cu latură unitară poate să se afle doar o singură persoană la un moment dat. Sala este reprezentată printr-o matrice cu R linii și C coloane, elementele sale fiind numere naturale de cel mult 6 cifre cu valorile: 0 – pentru spațiu neocupat, respectiv numere naturale nenule, care reprezintă identificatorul (ID-ul) persoanelor. Printre aceste persoane există persoane infiltrate (intruși) care au ID-uri cu valori identice cu ale altor persoane. Dacă există două sau mai multe persoane cu același ID, acestea sunt considerate toate suspecte.

Intrușii vor să ajungă în apropierea unor VIP-uri (persoane importante), pentru a le înregistra discuțiile cu un microfon care poate înregistra sunete în interiorul unui pătrat cu latura D, în centrul căruia se află chiar el. Acest pătrat nu este cuprins neapărat integral în matricea sălii (vedeți figura alăturată)!

Prin convenție, ID-urile VIP-urilor sunt numere prime distincte. În plus, și un ID al unui VIP poate fi copiat, crescând astfel numărul suspecților. Un VIP se caracterizează printr-un nivel de importanță: cu cât ID-ul este un număr mai mare, cu atât nivelul de importanță este mai mare (este „mai importantă”).

Persoanele suspecte au asociat un „grad de periculozitate”. Acesta este cu atât mai mare cu cât numărul de VIP-uri aflate în interiorul pătratului de latură D, în centrul căruia se află suspectul, este mai mare. Dacă există doi suspecți cu același grad de periculozitate, se consideră „mai periculoasă” persoana care are în pătratul său VIP-ul cu ID-ul cel mai mare. În caz de egalitate, se consideră „mai periculoasă” persoana care este așezată pe o linie cu un indice mai mic, iar la egalitate de indici de linii, pe o coloană cu indice mai mic. Există și persoane suspecte cu gradul de periculozitate 0, dacă în interiorul pătratului în centrul căruia se plasează nu există niciun număr prim.

Cerințe

1) Să se determine numărul persoanelor suspecte aflate în sala de așteptare.
2) Să se determine ID-ul și coordonatele persoanelor suspecte, (RSi -linia suspectului i, CSi -coloana suspectului i) în ordinea descrescătoare a „gradului de periculozitate”.

Fiind dat un şir de numere, denumim secvenţă a acestuia o parte dintre termenii şirului luaţi de pe poziţii consecutive. Denumim platou al acestui şir o secvenţă formată din valori identice. Lungimea unui platou este egală cu numărul de elemente care îl formează.

De exemplu, în şirul de numere 1 1 1 7 7 3 4 4 4 7 7 avem:

• platourile 1 1 1 şi 4 4 4 ambele având lungimea 3;
• platourile 7 7 (cel care începe în poziţia a patra) şi 7 7 (cel care începe pe poziţia a zecea), ambele având lungimea 2;
• platoul 3 care are lungimea 1.

În schimb nu avem platoul 7 7 7 7 deoarece cele patru elemente egale cu 7 nu sunt pe poziţii consecutive!

Se dă un şir de n numere. Fiecare dintre aceste numere aparţine intervalului [0,1000000]. Asupra acestui şir se pot efectua o singură dată următoarele două operaţiuni în această ordine:

1. se extrage un platou la alegere;
2. se inserează platoul extras la pasul anterior într-o poziţie la alegere din şirul rezultat după extragere.

De exemplu, dacă avem următorul şir inițial: 2 2 5 0 5 8 8 8 4 9 9 9 0 0 2 2 8 extragem platoul 2 2 format din elementele aflate în penultima şi antepenultima poziţie şi obţinem şirul: 2 2 5 0 5 8 8 8 4 9 9 9 0 0 8

În şirul rezultat inserăm platoul 2 2 (pe care l-am extras în pasul anterior) în poziţia a doua şi obţinem şirul: 2 2 2 2 5 0 5 8 8 8 4 9 9 9 0 0 8

Să se scrie un program care pentru un şir dat determină:

1. Lungimea maximă a unui platou din şirul dat iniţial precum şi valoarea cea mai mare a elementelor care formează un platou de lungime maximă.
2. Lungimea maximă a unui platou care poate să apară în şir în urma efectuării celor două operaţiuni precum şi valoarea cea mai mare a elementelor care ar putea forma un astfel de platou.

De Ziua Îndrăgostiţilor Vali a hotărât să organizeze o petrecere mare pe stadionul oraşului. La petrecere pot participa numai şi numai îndrăgostiţi care şi-au procurat biletele din timp. Biletele oricărui cuplu sunt aproape identice. Ele au proprietatea că numărul de serie are prima cifră 1 pentru băieţi şi *prima cifră 2 pentru fete, continuarea celor două numere este identică. De exemplu, dacă prietenul are biletul cu numărul 134, atunci prietena lui are biletul 234, iar dacă prietena are biletul 2234567890, atunci prietenul ei are biletul 1234567890.
Bineînțeles, că și Vali are bilet și speră să câștige un cadou. Biletul lui Vali are aceeași proprietate ca celelalte bilete, cu o singură excepție: Vali nu va participa cu pereche la acest eveniment.

Pe parcursul desfășurării petrecerii, biletele de intrare vor avea şi rolul de bilet de tombolă. Acestea vor fi introduse într-o urnă şi câteva dintre ele vor fi extrase, iar norocoşii proprietari ai biletelor vor primi cadouri valoroase. Se mai știe că există probabilitatea ca unii participanți să vină la petrecere cu bilete falsificate, având numere identice cu cele de pe un bilet original. Acest fapt se va depista cu ușurință în momentul extragerii.

De Ziua Îndrăgostiţilor Vali a hotărât să organizeze o petrecere mare pe stadionul oraşului. La petrecere pot participa numai şi numai îndrăgostiţi care şi-au procurat biletele din timp. Biletele oricărui cuplu sunt aproape identice. Ele au proprietatea că numărul de serie are prima cifră 1 pentru băieţi şi *prima cifră 2 pentru fete, continuarea celor două numere este identică. De exemplu, dacă prietenul are biletul cu numărul 134, atunci prietena lui are biletul 234, iar dacă prietena are biletul 2234567890, atunci prietenul ei are biletul 1234567890.
Bineînțeles, că și Vali are bilet și speră să câștige un cadou. Biletul lui Vali are aceeași proprietate ca celelalte bilete, cu o singură excepție: Vali nu va participa cu pereche la acest eveniment.

Pe parcursul desfășurării petrecerii, biletele de intrare vor avea şi rolul de bilet de tombolă. Acestea vor fi introduse într-o urnă şi câteva dintre ele vor fi extrase, iar norocoşii proprietari ai biletelor vor primi cadouri valoroase. Se mai știe că există probabilitatea ca unii participanți să vină la petrecere cu bilete falsificate, având numere identice cu cele de pe un bilet original. Acest fapt se va depista cu ușurință în momentul extragerii.

Cunoscând numerele de serie ale tuturor biletelor de intrare la acest eveniment, aflaţi:
a) dacă pe Vali o cheamă Valentina sau îl cheamă Valentin;
b) numărul biletului lui Vali.

Să se scrie un program care pentru un şir cunoscut determină pentru câte subsecvenţe ale şirului suma elementelor care le alcătuiesc are un anumit rest dat la împărţirea cu 3.

Se dă un șir P de lungime N cu elemente distincte din mulțimea {1,2..,N}. Pentru fiecare poziție i din șirul P se cere să aflați cea mai mică poziție j, astfel încât P[j] < P[i] și j < i. În caz că o astfel de poziție nu există se consideră -1 ca soluție.

După o amorţeală care durase mai bine de 3 luni, Mama Natură îşi dădu seama că primăvara stătea să vină şi florile cu care trebuia curând să umple câmpiile nu erau încă pregătite. Înainte de începerea iernii, a lucrat să combine nuanţe din care să creeze flori pline de culoare, iar acum are camera plină de discuri de diferite culori, care aşteaptă să fie asamblate în flori viu colorate, fie pe post de mijloc, fie ca şi petale.

Pentru a forma o floare, Mama Natură alege un mijloc de orice culoare şi cel puţin K petale. Totodată, ea nu îşi doreşte să strice ordinea firească a lucrurilor şi de aceea nu va folosi niciodată două culori diferite de petale pentru aceeaşi floare. Ea admite, în schimb, flori cu petalele și mijlocul de aceeași culoare.

Deoarece timpul e scurt şi Mama Natură are lucruri mai importante de făcut decât să stea să asambleze flori, ea îşi cheamă în ajutor toate prietenele şi doreşte să îi dea fiecăreia ceva de lucru. Pentru aceasta, ea are la dispoziţie un şir D de N numere, unde numărul de pe poziţia i din șir reprezintă câte discuri de culoarea i a pregătit. Apoi, Mama Natură îşi pune M întrebări de forma x y, prin care doreşte să afle care este numărul maxim de flori care se pot forma folosind doar discuri de culori din intervalul [x, y] din şirul D.

Marele inginer NN, expert în construirea de baraje, a primit de data aceasta o sarcină mai îmbârligată. Acesta are de construit M baraje peste mai multe râuri dintr-o deltă și îşi planifică pe hârtie milimetrică construcţia fiecărui baraj în parte.

Toate râurile peste care are de construit baraje sunt braţe ale aceluiaşi fluviu şi toate pornesc din exact acelaşi punct pe lungimea fluviului. Pentru a-şi explica schiţa, NN marchează locul de despărţire a tuturor braţelor fluviului printr-un punct O, numit origine. Apoi, din origine pornesc N semidrepte, fiecare reprezentând o porţiune de uscat, astfel încât spaţiul gol dintre 2 semidrepte consecutive va fi considerat un braţ al fluviului.

După ce a desenat schiţa proiectului, NN se întreabă care e numărul de râuri pe care le acoperă complet fiecare baraj. Un baraj acoperă complet un râu dacă intersectează fiecare dintre malurile acestuia. Sarcina voastră este să îl ajutaţi oferindu-i informaţii precise pentru a-şi putea realiza planul cât mai eficient, păstrându-şi renumele.

Fericit că s-a calificat la ONI, XORin vrea să sărbătorească făcând cât mai mult zgomot. Deoarece e programator, acesta s-a gândit să automatizeze felul în care face zgomot.

Pentru a face zgomot el folosește o placă cu circuite de diverse intensități. Placa poate fi reprezentată sub forma unei matrice cu N linii și M coloane. Fiecare celulă din matrice are o intensitate între 0 și 9 (o celulă cu intensitatea 0 corespunde unei zone goale, fără nici un circuit).

Un circuit începe într-o celulă a matricei și se termină în altă celulă, fiind o succesiune de celule adiacente de aceeași intensitate de la un capăt la celălalt al circuitului, asemenea unui drum pe matrice între cele două celule. Două celule se consideră adiacente dacă au o latură comună, deci o celulă e adiacentă cu maxim patru alte celule.

Placa a fost concepută în așa fel încât să nu apară scurtcircuite, așadar curentul dintr-un circuit poate merge numai într-o singură direcție (cu alte cuvinte, fiecare celulă dintr-un circuit se învecinează cu maxim alte două celule din același circuit). Nu există circuite de aceeași intensitate care să se învecineze.

Zgomotul produs de un circuit este egal cu lungimea lui, adică cu numărul de celule din matrice corespunzătoare circuitului.

Cerințe:

1) Să se afle numărul de circuite.
2) Să se afle valoarea zgomotului maxim care poate fi obținut unind două circuite. Două circuite pot fi unite dacă se poate trage o legătură de la un capăt al unui circuit până la un capăt al celuilalt circuit, numai prin celulele libere ale matricei (de intensitate 0). Legătura trebuie să aibă forma unui circuit. Lungimea circuitului nou creat nu se adaugă la zgomotul produs de cele doua circuite.
3) Să se afișeze placa ce conține legătura care unește două circuite din care se obține zgomotul maxim de la cerința 2. Dacă există mai multe variante, se poate afișa orice placă care conține legătura validă.

Cercetări recente au scos la iveală un vechi document scris într-un dialect ciudat denumit masaretu. Textul conţinut de acest document este format din cuvinte iar între două cuvinte există cel puţin un spaţiu.

Despre acest dialect se cunosc câteva caracteristici:

• scrierile din acest dialect folosesc literele mici ale alfabetului englez;
• toate cuvintele dialectului au exact opt litere;
• cuvintele dialectului sunt formate din silabe. Fiecare silabă are două litere dintre care una este o vocală (adică una dintre literele a e i o u) iar cealaltă o consoană. Rezultă că fiecare cuvânt are patru silabe.

Din păcate documentul descoperit este deteriorat: din unele cuvinte au dispărut una sau mai multe litere. Astfel în document apar grupuri formate din mai puţin de opt litere care nu mai reprezintă cuvinte ale vocabularului dialectului masaretu.

Să se scrie un program care determină:

1) câte cuvinte corecte sunt în documentul recent descoperit.
2) silabele care apar cel mai des în cuvintele corecte din document.

Tudoraș are o pasiune pentru muzică. El deține câte K albume din discografia fiecăreia dintre cele C formații pe care le ascultă. În fiecare zi, Tudoraș extrage la întamplare exact Q albume din colecția sa, pe care le ascultă în cursul zilei.

La finalul zilei, Tudoraș analizează albumele ascultate. Concret, el numără de la câte formații diferite provin cele Q albume alese și își notează această valoare.

Care va fi media aritmetică a valorilor notate, dacă procesul se repetă pentru un număr infinit de zile? Cu alte cuvinte, care este valoarea medie (expected value) a numărului de formații ascultate într-o zi?