Lista de probleme 1992

Un grup de N cercetași, numerotați de la 1 la N, se află în tabără la munte. Pentru ei, organizatorii au pregătit N scaune, de asemenea numerotate de la 1 la N, așezate în cerc, astfel încât fiecare cercetaș să aibă locul său (locul cercetașului i este pe scaunul i, 1≤i≤N).

Pentru desfășurarea următoarei activități, organizatorii au decis ca M dintre cercetași să prezinte diferite exerciții. Numărul M este egal cu cea mai mare putere a lui 2 cu proprietatea că numărul N de cercetași aflați în tabără se poate scrie ca sumă de M numere consecutive în mulțimea numerelor impare. Cei M cercetași care vor prezenta sunt cei numerotați cu numerele impare consecutive a căror sumă este N. De exemplu, dacă N=8, atunci M este 2, iar exercițiile vor fi prezentate de cercetașii numerotați cu 3, respectiv cu 5.

Din joacă, micii cercetași s-au așezat pe scaune la întâmplare. Organizatorii au nevoie pentru a desfășura activitatea ca cel puțin cei M cercetași care vor prezenta exercițiile să se afle pe locurile lor. Pentru aceasta, o parte dintre cercetași trebuie să-și schimbe locul și organizatorii invită micii cercetași să participe la jocul numit ”Mutare”. Acest joc se desfășoară astfel: unul dintre cercetașii care nu se află pe locul lor se ridică și merge în interiorul cercului. Cercetașul numerotat cu numărul scaunului rămas liber își va ocupa locul, iar locul ocupat de el anterior rămâne astfel liber. Jocul continuă până când scaunul cercetașului aflat în interiorul cercului se eliberează și el se așază pe locul său.

Fiind dat numărul N, precum și ordinea în care s-au așezat cercetașii pe scaunele numerotate de la 1 la N, scrieți un program care să determine:

• numărul M de cercetaşi care vor prezenta exerciţii în cadrul activităţii;
• numerele de identificare ale celor M cercetaşi care vor prezenta exerciţiile, în ordine strict crescătoare;
• numărul minim de cercetași care își vor schimba locul, astfel încât toţi cei M cercetași care vor prezenta exercițiile să se afle pe locurile lor.

Pietrele preţioase au fascinat omenirea încă din timpuri străvechi iar cele mai renumite dintre ele, cristalele, au devenit atât simbolul durităţii cât şi al eternităţii. În urma unui studiu ştiinţific, pe un eşantion de formă dreptunghiulară se pot observa diferite tipuri de molecule, dispuse într-o geometrie perfectă, pe M rânduri a câte N molecule fiecare, aliniate una lângă alta. O formaţiune cristalizabilă este alcătuită din 3 molecule de acelaşi tip, învecinate două câte două, având una dintre cele patru forme din imaginea alăturată (fig.1).

Fiecare formaţiune este înconjurată de jur-împrejur, ca în fig.2, de un înveliş special format şi el din molecule identice, de alt tip decât cele din formaţiunea cristalizabilă pe care o înconjoară şi o izolează de restul formaţiunilor moleculare. În acest fel, fiecare moleculă din formaţiunea cristalizabilă se învecinează la Nord, Sud, Est şi Vest cu o moleculă din aceeaşi formaţiune cristalizabilă sau cu o moleculă din învelişul special.

Fiecare formaţiune cristalizabilă se bombardează cu raze X şi în acest fel are loc cristalizarea, proces prin care învelişul special se extinde peste formaţiunea cristalizabilă pe care o înconjoară, formând o singură structură din care se va dezvolta cristalul.

Cerințe

1. Determinaţi numărul formaţiunilor cristalizabile ce pot fi identificate pe eşantionul analizat.
2. Afişaţi eşantionul rezultat după cristalizare.

Arhi şi-a propus să extindă clădirea de birouri pe care a proiectat-o iniţial pe un singur nivel numerotat cu 1, împărţit în n*n zone pătratice de latură 1, fiecare corespunzând unui birou, prin construirea mai multor niveluri. În colţurile tuturor birourilor se construiesc grinzi de rezistenţă. Pentru a asigura rezistenţa întregii clădiri, Arhi va proiecta niveluri noi, numerotate cu 2, 3,… atât timp cât conțin cel puțin un birou și sunt respectate următoarele patru reguli:

• R1: fiecare nivel nou va fi proiectat sub forma unui dreptunghi sau pătrat de arie maximă pentru nivelele cu număr impar, respectiv, sub forma unui pătrat de arie maximă pentru nivelele cu număr par;
• R2: fiecare dintre colţurile zidurilor unui nivel nou trebuie plasat pe câte o grindă de rezistenţă dintre două sau mai multe birouri de pe nivelul precedent;
• R3: oricare două dintre colţurile zidurilor unui nivel nou vor fi plasate pe ziduri diferite (un zid nu se poate suprapune în totalitate pe alt zid) şi cel puţin două vârfuri opuse ale unui nivel nou se vor afla pe ziduri opuse ale nivelului precedent;
• R4: orice porţiune de zid de pe nivelul k (k>1), construită deasupra unui birou de pe nivelul k-1, se va suprapune exact peste una dintre laturile biroului, sau îl va străbate în diagonală.

Birourile de pe nivelul k (k>1), vor fi construite exact deasupra celor de pe nivelul precedent, astfel, nivelurile 2, 4 etc. vor avea lângă ziduri spaţii triunghiulare care nu vor aparţine niciunui birou.

Numerele inscripţionate pe birouri în imaginea de mai sus, indică nivelul corespunzător birourilor vizibile de deasupra clădirii.

Cunoscându-se lungimea n a laturii primului nivel al clădirii, să se determine:

1. numărul maxim de niveluri pe care le poate avea clădirea;
2. numărul total de birouri ale clădirii cu număr maxim de niveluri.

Fie un şir a[1], a[2], …, a[n] de numere naturale, unde n este impar. Avem la dispoziţie o singură operaţie admisă şi anume: putem aduna la două poziţii diferite din şir o aceeaşi valoare naturală nenulă.

Cerințe:

1. Să se verifice dacă șirul poate să aibă toate elementele egale după aplicarea unei singure operații.
2. Folosind de mai multe ori operaţia admisă, să se obţină șirul cu toate elementele egale, dar valoarea egală obţinută să nu depăşească dublul valorii maxime din şirul iniţial.

Tudor a primit un joc educaţional numit “Roboţel” cu ajutorul căruia va învăţa punctele cardinale Nord, Est, Sud, Vest. Jocul constă dintr-un roboţel care se deplasează pe o tablă de forma unei matrici pătratice, împărţită în R linii şi R coloane. Fiecare căsuţă, aflată la intersecţia dintre o linie şi o coloană, este fie căsuță „liberă”, fie căsuță „semnalizator”, caz în care este etichetată cu una din literele N, E, S, V, reprezentând 4 sensuri posibile de deplasare. Când roboțelul ajunge într-o „căsuţă semnalizator”, el îşi schimbă sensul de deplasare astfel:

• Dacă căsuţa este etichetată cu N atunci roboţelul se va deplasa în continuare de jos în sus;
• Dacă căsuţa este etichetată cu E atunci roboţelul se va deplasa în continuare de la stânga la dreapta;
• Dacă căsuţa este etichetată cu S atunci roboţelul se va deplasa în continuare de sus în jos;
• Dacă căsuţa este etichetată cu V atunci roboţelul se va deplasa în continuare de la dreapta la stânga.

Două căsuțe semnalizator formează o pereche „blocantă” dacă:

• Se află pe aceeași linie și conțin literele E și V, căsuța cu E are coloana mai mică decât a celei etichetate cu V și între ele, pe aceeași linie nu există alte căsuțe semnalizatoare.
• Se află pe aceeași coloană și conțin literele S și N, căsuța cu S are linia mai mică decât a celei etichetate cu N și între ele, pe aceeași coloană nu există alte căsuțe semnalizatoare.

În figura 1, de exemplu, sunt 2 perechi blocante: Perechea (1,2) (5.2) și perechea (2,3) (2,5).

Roboţelul porneşte din căsuţa (1,1), aflată pe prima linie și prima coloană şi dacă aceasta este liberă, se deplasează, în cadrul primei linii, de la stânga la dreapta. În cazul în care căsuța de pornire (1,1) este semnalizator, atunci roboțelul se va deplasa pe direcția indicată de litera cu care este etichetată. Considerând că roboțelul se deplasează pe tablă, el se oprește doar în următoarele situații:

• Roboţelul intră într-o căsuţă liberă aflată pe prima sau ultima linie, respectiv prima sau ultima coloană, caz în care dacă s-ar menține sensul deplasării actuale roboțelul ar părăsi tabla;
• Roboțelul intră într-o „căsuţă semnalizator” a unei perechi blocantă și se va opri în cealaltă căsuță a perechii.

De exemplu, în Figura 2, roboțelul ajunge în căsuța liberă (3,5) unde se oprește. În Figura 3, roboțelul se va opri în căsuța (4,1) deoarece dacă ar schimba sensul spre Est, ar reveni în ultima căsuță semnalizator vizitată, (4,3).
Roboțelul înaintează o căsuță într-un pas, în sensul de deplasare.

Scrieţi un program care, cunoscând numărul R de linii şi coloane și cele K căsuţe semnalizator, determină:

1. Toate perechile blocante de pe tablă;
2. Numărul de pași efectuați pe fiecare sens în parte: Nord, Est, Sud și Vest

Ionel și Georgel sunt colegi de clasă și doresc să facă schimb de fișiere prin email. Fiecare dintre ei își arhivează fișierele cu câte o parolă. Fiecare copil își construiește parola pe baza unui șir format din N numere naturale.

Numerele din șir care se folosesc efectiv pentru construirea parolelor sunt doar cele divizibile cu numerele din mulțimea {2,3,4,5,6,7,8,9,10,11,12,13,14,15}. Copiii numără câte din valorile din șir sunt divizibile cu fiecare din aceste numere.

Parola folosită de Ionel se obține prin însumarea numărului de valori din șir care sunt divizibile cu numerele din mulțimea {2,3,4,5,6,7,8,9}. Parola folosită de Georgel se obține prin însumarea numărului de valori din șir care sunt divizibile cu numerele din mulțimea {10,11,12,13,14,15}.

Scrieţi un program care citește șirul celor N numere și determină:

1. câte numere din șir nu se vor folosi în construirea parolelor celor doi copii;
2. parola construită de Ionel;
3. parola construită de Georgel.

Un număr natural nenul m se numește norocos dacă pătratul lui se poate scrie ca sumă de m numere naturale consecutive. Un număr natural m se numește k-norocos, dacă este egal cu produsul a exact k numere prime distincte. Observați că între cele două proprietăți definite nu există nicio legătură.

Dându-se k și N numere naturale, scrieți un program care să determine:

a) Cel mai mic și cel mai mare număr norocos dintre cele N numere citite
b) Câte numere k-norocoase sunt în șirul de N numere citite

Pentru un număr natural N se consideră șirul a=(1,2,3...,N), deci a[i]=i pentru orice i, 1≤i≤N.

Asupra acestui șir se pot aplica operații de două tipuri:

a) la operația de tipul 1 se specifică două valori i și j, cu 1≤i≤j≤N. Efectul acestei operații asupra șirului este de oglindire a secvenței din șir care începe cu elementul de pe poziția i și se termină cu cel de pe poziția j. De exemplu, dacă în șirul a=(1,2,3,4,5,6,7) se aplică operația 3 6, atunci șirul devine a=(1,2,6,5,4,3,7). Iar în șirul a=(1,4,3,2,5,6,7), dacă se aplică operația 4 6, atunci a=(1,4,3,6,5,2,7).
b) Operația de tipul 2 conține un indice i, 1≤i≤N, și cere să afișăm valoarea elementului care se află în acel moment pe poziția i în șir.

Se consideră M astfel de operații într-o ordine dată.

Scrieți un program care să determine și să afișeze rezultatul pentru fiecare operație de tipul 2.

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

Se consideră o matrice cu L linii și C coloane care memorează doar valori din mulțimea {0,1,2}. O submatrice nevidă (formată din cel puțin o linie și cel puțin o coloană) a acestei matrice o numim omogenă dacă numărul valorilor de 0 este egal cu numărul de valori de 1 și egal cu numărul valorilor de 2.

Să se determine câte submatrice nevide omogene există.