Lista de probleme 2164

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.

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

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.

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.

Î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?

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.

Parcarea unui mall are locuri de parcare dispuse pe nr rânduri, câte np pe fiecare rând, unul lângă altul. Trei prieteni vin cu câte o mașină la mall și caută un triplet de locuri libere alăturate, plasate toate trei doar pe primul sau toate trei doar pe ultimul rând al parcării.

Scrieţi un program care citeşte de la tastatură două numere naturale din intervalul [3,50], nr și np, reprezentând numărul de rânduri din parcare, respectiv numărul de locuri de pe fiecare rând, apoi nr∙np valori din mulțimea {0,1}, elemente ale unui tablou bidimensional cu nr linii și np coloane, reprezentând, în ordinea dispunerii lor pe rânduri, starea locurilor de parcare (0, pentru loc liber, sau 1, pentru loc ocupat).

Programul afișează pe ecran numărul de triplete de locuri libere pe care le pot găsi prietenii.

În Grădina Botanică Regală „Etherea”, cercetătorii studiază o specie rară de cireș japonez, numită Sakura Tennyo. Grădina este reprezentată printr-o matrice cu N linii și M coloane, în care fiecare celulă corespunde unei parcele de pământ. Inițial, toate parcelele au fertilitatea 0.

În grădină au loc, pe rând, Q înfloriri. O înflorire din celula (r, c), având puterea K, eliberează polen care, purtat de curenții de aer, se poate răspândi în cel mult 4 zone triunghiulare, după reguli precizate.

Determinați matricea finală a fertilității după aplicarea tuturor celor Q înfloriri.

Înainte de prima cursă din sezon, Marele Premiu al orașului Necleab, Carol și Luis pot să facă mașina mai rapidă folosindu-se de un șir de n numere întregi, indexat de la 0 la n − 1, și patru numere: k, p, q și r. Carol selectează o mulțime care conține indicii unei subsecvențe de lungime q · k din șirul de n numere. Indicele de start al acestei subsecvențe, notat cu i, trebuie să îndeplinească condiția 𝑖 % 𝑘 = 𝑟. Luis selectează inițial o mulțime care conține indicii unei subsecvențe de lungime 𝑝 din șirul de n numere. Ulterior, el adaugă indici astfel încât, la final, un indice i aparține mulțimii dacă și numai dacă indicele 𝑖 + 𝑘 aparține aceleiași mulțimi, ori de câte ori ambii indici sunt cuprinși între 0 și n − 1. Pentru ca în sfârșit anul ăsta să fie anul lor, piloții vor să facă mașina cât mai rapidă. Urmând regulile descrise mai sus, care este viteza maximă cu care piloții pot îmbunătăți mașina?

Fermierul Amooot merge la magazinul de furaje pentru a achiziționa amestecuri de iarbă pentru pășunatul vacilor sale. Vânzătorul Popică, viclean de fel, îi prezintă un șir V de N oferte; însă, pentru ca Amooot să poată achiziționa hrana, acesta va trebui neapărat să selecteze o subsecvență canonică de oferte!

Spunem că o subsecvență A[i], A[i+1], … , A[j] , 1 ≤ i ≤ j ≤ N este canonică dacă A[k] % A[i] = 0, pentru orice k, i ≤ k ≤ j. De exemplu, în șirul (3, 4, 2, 10, 4, 12, 3), subsecvențe canonice sunt (2, 10) sau (2, 10, 4, 12), dar nu și subsecvența (10, 4, 12).

Văzând condițiile impuse de Popică, Amooot își pune două întrebări:

1. Care este cea mai lungă subsecvență canonică din V?
2. Câte subsecvențe canonice există în V?