Lista de probleme 1991

Gigel îşi imaginează lumea în varianta 2d, adică reprezentată în sistem de coordonate cartezian XOY. Fiecare persoană din grupul celor N prieteni ai săi este reprezentată în plan printr-un punct identificat prin abscisa şi ordonata sa. În lumea sa 2d, plouă ca în Anglia, iar picăturile de ploaie pică paralel cu axa OY, de la o înălţime infinită. Ca să îi ferească pe prietenii săi de ploaie, îşi propune să le construiască apărători pe care le va reprezenta pe hartă prin segmente de dreaptă.

Ştiind că nu poate să deseneze pe hartă decât segmente de lungimi egale, determinaţi care este lungimea minimă a unui segment astfel încât trasând cel mult K segmente, toți cei N prieteni ai săi să fie protejați de ploaie.

Vasilică are la grădiniţă N turnuri cu înălţimile h1, h2, …, hN. Când aşază în linie nişte turnuri, cel puţin două, astfel încât înălţimile lor să fie în ordine crescătoare, Vasilică spune că a construit un deal. Înălţimea dealului este egală cu înălţimea celui mai înalt turn folosit. Iată, de exemplu, că aşezând în ordine turnurile cu înălţimile 2 4 4 7 9 a format un deal cu înălţimea 9.

Vasilică şi-ar dori să aşeze în linie cele N turnuri, formând o succesiune de dealuri astfel încât suma înălţimilor dealurilor formate să fie maximă.

Scrieţi un program care, cunoscând înălţimile celor N turnuri, va determina suma înălţimilor dealurilor ce se pot forma aşezând în linie cele N turnuri, maximă posibil.

Specialiştii chimişti au reuşit crearea în laborator a unei game diversificate de substanţe lichide nemiscibile (care nu se amestecă între ele), de aceeaşi densitate şi de culori diferite.

Acest rezultat a fost utilizat de către specialiştii fizicieni pentru studiul principiului vaselor comunicante. Conform acestui principiu „într-un sistem de vase comunicante nivelul lichidului este acelaşi, indiferent de forma vaselor.“

Experimentele fizicienilor se desfăşoară astfel:

Într-un sistem cu două vase comunicante, gradat identic pe fiecare ramură cu 0, 1, 2, 3,…, fizicienii introduc un număr de n lichide, pe ramura din stânga sau pe ramura din dreapta. Volumele introduse din fiecare lichid, notate cu Vi (1≤i≤n), sunt numere naturale nenule pare astfel încât, la echilibru, orice lichid se va aşeza între două gradaţii de aceeaşi parte a unei ramuri sau pe cele două ramuri ale sistemului de vase comunicante. Lichidele sunt identificate prin intermediul culorii acestora, culori numerotate cu 1, 2, 3, … , n. Introducerea lichidelor în sistemul cu două vase comunicante se face în ordinea crescătoare a numerelor culorilor, începând cu lichidul de culoare 1.

Scopul experimentului este de a determina gradaţia maximă la care se ridică lichidele în sistemul cu două vase comunicante, precum şi între ce gradaţii se găseşte un lichid de culoare x, dintre cele introduse.

De exemplu, dacă în sistemul cu două vase comunicante se introduc n=3 lichide în ordinea: V1=4 lichid de culoare 1 introdus prin ramura din dreapta (operaţie codificată 4 D), V2=4 lichid de culoare 2 introdus prin ramura din stânga (operaţie codificată 4 S) şi V3=2 lichid de culoare 3 introdus prin ramura din stânga (operaţie codificată 2 S) atunci gradaţia maximă la care se ridică nivelul lichidelor în sistemul cu două vase comunicante este 5, iar lichidul de culoare x=2 se găseşte între gradaţiile: 3 pe ramura din stânga (3 S) şi 1 pe ramura din dreapta (1 D), conform figurii alăturate.

Să se scrie un program care cunoscând numărul n de lichide introduse în sistemul cu două vase comunicante, volumul Vi şi ramura prin care se face introducerea lichidului de culoare i (1≤i≤n), precum şi culoarea x, să calculeze gradaţia maximă la care se ridică lichidele în acest sistem la echilibru şi între ce gradaţii se găseşte lichidul de culoare x.

Furnicuţa şi-a construit un depozit pentru grăunţe pe o suprafaţă de teren dreptunghiulară şi l-a compartimentat în N*M camere identice, de formă pătratică, dispuse câte M pe direcţia Ox şi câte N pe direcţia Oy. Din fiecare cameră se poate intra în orice cameră învecinată cu ea (cameră care are un perete comun cu aceasta).

În fiecare cameră, identificată prin coordonatele sale, ca în desenul alăturat în care N=5 şi M=4, furnica a depozitat o cantitate de grăunţe. De exemplu, în camera de coordonate (I,J) este depozitată cantitatea CIJ de grăunţe.

Atât intrarea cât şi ieşirea din depozit se poate face doar prin cele patru camere din colţurile depozitului, adică cele de coordonate (1,1), (1,M), (N,1) şi (N,M) care comunică cu exteriorul.

Pentru a asigura circulaţia aerului în depozit, furnica a montat un sistem de ventilaţie în camera de coordonate (X,Y).

Văzând ce multe grăunţe are furnica pentru iarnă, vecinul ei, leneşul greieraş Cri, s-a hotărât să fure din ele.

Cri s-a gândit să intre în depozit prin sistemul de ventilaţie din camera de coordonate (X,Y) şi să iasă prin una din cele 4 camere din colţurile depozitului care comunică cu exteriorul.

A studiat planul depozitului şi a împărţit camerele în patru zone:

• prima zonă, numerotată cu 1, conţine toate camerele de coordonate (I,J) cu 1 ≤ I ≤ X şi 1 ≤ J ≤ Y, cu ieşirea prin camera de coordonate (1,1)
• a doua zonă, numerotată cu 2, conţine toate camerele de coordonate (I,J) cu 1 ≤ I ≤ X şi Y ≤ J ≤ M, cu ieşirea prin camera de coordonate (1,M)
• a treia zonă, numerotată cu 3, conţine toate camerele de coordonate (I,J) cu X ≤ I ≤ N şi 1 ≤ J ≤ Y, cu ieşirea prin camera de coordonate (N,1)
• a patra zonă, numerotată cu 4, conţine toate camerele de coordonate (I,J) cu X ≤ I ≤ N şi Y ≤ J ≤ M, cu ieşirea prin camera de coordonate (N,M)

Cri va intra doar într-una din cele patru zone şi va fura grăunţele doar din camerele conţinute de zona aleasă. Pentru a nu declanşa alarma furnicuţei, el va trebui să treacă cel mult o dată prin fiecare cameră din zonă, să fure întreaga cantitate de grăunţe din aceasta şi să iasă din depozit prin camera ce comunică cu exteriorul, corespunzătoare zonei alese.

Cri va trebui să aleagă zona în care va intra astfel încât cantitatea totală T de grăunţe furate să fie maximă, iar numărul K de camere prin care va trece să fie minim.

Scrieţi un program care să determine numerele naturale Z, T şi K, unde Z reprezintă numărul zonei pe care va trebui s-o aleagă Cri astfel încât cantitatea totală T de grăunţe furate să fie maximă, iar numărul K de camere prin va trece să fie minim.

Lizuca are n flori ornamentale de înălţimi h1, h2, …, hn, exprimate în centimetri. Pentru a uda plantele, Lizuca stabileşte următorul program: în prima zi va alege o plantă pe care o va uda, în a doua zi va alege două plante pe care le va uda, în ziua a treia va alege trei plante pe care le va uda şi aşa mai departe. Dacă o plantă este udată într-o anumită zi, atunci creşte 1 centimetru până la sfârşitul acelei zile, iar dacă nu este udată, rămâne la înălţimea pe care o avea la sfârşitul zilei precedente.

Scrieţi un program care determină:

a) un număr natural S, exprimat în centimetri, reprezentând suma înălţimilor finale ale tuturor plantelor, dacă Lizuca le-ar uda după procedeul descris, timp de n zile;
b) un număr natural K, reprezentând numărul maxim de zile în care Lizuca poate uda florile după procedeul descris anterior, astfel ca la sfârşitul celei de a K-a zi, nicio plantă ornamentală să nu atingă înălţimea H.

Într-o zi frumoasă de vară, Alice se juca în parc. Deodată, văzu un iepure cu ceas, numit Iepurele Alb, sărind grăbit în scorbura unui copac. Curioasă, Alice îl urmări şi sări şi ea în scorbură. Spre mirarea ei, ajunse într-o sală mare cu N uşi încuiate. Pe fiecare uşă era scris câte un număr natural. Într-o clipă, lângă ea apăru Iepurele Alb şi-i spuse că doar uşile cu numere magice pot fi deschise dacă are cheile potrivite. Pentru a o ajuta, Iepurele Alb i-a explicat că un număr magic este un număr natural care poate fi redus la o cifră prin complementarea cifrelor acestuia faţă de cifra sa maximă din scrierea zecimală, apoi prin complementarea cifrelor numărului obţinut faţă de cifra sa maximă şi aşa mai departe până când se obţine o cifră. Evident, nu toate numerele naturale sunt numere magice. De exemplu, uşa cu numărul 1234 poate fi deschisă cu cheia inscripţionată cu cifra 1 deoarece 1234 este un număr magic ce poate fi redus la cifra 1 prin complementări repetate (1234→3210→123→210→12→10→1), iar uşa cu numărul 1204 nu poate fi deschisă deoarece 1204 nu este un număr magic (indiferent de câte ori s-ar repeta complementarea nu poate fi redus la o cifră: 1204→3240→1204→3240→1204 ... ).

Înainte să dispară, Iepurele Alb îi dădu o cheie aurie inscripţionată cu cifra K şi o avertiză că poate deschide cu această cheie doar uşile cu numere magice ce pot fi reduse la cifra K.

Scrieţi un program care să citească numerele naturale N, K şi cele N numere naturale scrise pe cele N uşi, şi care să determine:

a) cel mai mare număr par dintre numerele scrise pe cele N uşi;
b) numărul uşilor care pot fi deschise cu cheia aurie inscripţionată cu cifra K.

Costel a descoperit într-o debara servieta cu cifru a tatălui său. Cifrul este compus din 4 discuri metalice pe care sunt inscripţionate cifrele de la 0 la 9. Fiecare disc se poate mişca individual, de sus în jos sau de jos în sus, formându-se combinaţii de cifre. De multe ori, datorită comodităţii, combinaţia ce permite deschiderea servietei este formată numai din cifre identice: 0000, 1111 etc.

Costel îşi imaginează un cifru compus din N discuri metalice, fiecare având inscripţionate cifrele de la 0 la 9, fiecare putând fi deplasat în cele două direcţii specificate anterior. Prin mutare Costel înţelege deplasarea unui disc în sus sau în jos, cu o singură poziţie, adică deplasarea discului până la cifra precedentă, respectiv următoare celei curente.

Realizaţi un program care, cunoscând poziţia iniţială a fiecărui disc dintre cele N discuri ale cifrului, determină şi afişează:

a) cifra cea mai mare care apare pe discurile cifrului în forma iniţială;
b)
b1) numărul minim de mutări necesare pentru ca numărul obţinut pe cifru să fie compus numai din cifre identice, număr necesar deschiderii servietei;
b2) cifra cea mai mică ce se poate obţine în urma efectuării numărului minim de mutări determinat;
b3) numărul de combinaţii formate din cifre identice, care se poate obţine în urma efectuării numărului minim de mutări determinat.

Locuitorii planetei Agria, numiţi agri, au hotărât ca în celebrul an 2012 să le explice pământenilor cum trebuie cules „eficient” un rând cu n porumbi, numerotaţi, în ordine, cu 1, 2, 3,..., n.

Cei n porumbi sunt culeşi de mai mulţi agri. Primul agri merge de-a lungul rândului, plecând de la primul porumb şi culege primul porumb întâlnit, al treilea, al cincilea şi aşa mai departe până la capătul rândului.

Atunci când ajunge la capătul rândului, porneşte al doilea agri şi culege porumbi respectând aceeaşi regulă ca şi primul agri.

Metoda se repetă până când toţi porumbii sunt culeşi.

Pământeanul Ionel încearcă să descopere ce ascunde această metodă şi se gândeşte câţi porumbi culege primul agri, câţi agri culeg un rând cu n porumbi, la a câta trecere este cules porumbul cu numărul x şi care este numărul ultimului porumb cules.

Exemplu: Dacă pe un rând sunt n=14 porumbi atunci sunt 4 agri care culeg porumbii:

primul agri culege porumbii 1,3,5,7,9,11,13; al doilea agri culege porumbii 2,6,10,14; al treilea agri culege porumbii 4 şi 12; ultimul agri culege porumbul 8.

Pentru a-l ajuta pe Ionel să descopere secretul acestei metode, scrieţi un program care citeşte cele două numere naturale n şi x şi care determină:

a) numărul de porumbi culeşi de primul agri;
b) numărul de agri care culeg şirul de n porumbi;
c) numărul trecerii la care este cules porumbul cu numărul x;
d) numărul ultimului porumb cules.

Se dau n numere naturale, unde n este număr par. Să se calculeze suma produselor dintre fiecare număr din prima jumătate și fiecare număr din a doua jumătate a șirului de numere date.

Andrei se descurcă foarte bine la geometrie şi de aceea născoceşte tot felul de jocuri pe care le testează cu Alexandru, colegul său de bancă. Pentru a pregăti noul joc cu trei niveluri, Andrei desenează pe o foaie de matematică reperul cartezian xOy şi mai multe puncte distincte. Fiecare punct desenat are atât abscisa x, cât şi ordonata y, numere întregi.

La primul nivel, Alexandru determină numărul maxim de puncte (dintre cele desenate) aflate pe una dintre axele sistemului cartezian sau pe o dreaptă paralelă cu una dintre cele două axe.
La al doilea nivel, Alexandru consideră toate punctele desenate a căror abscisă x şi ordonată y verifică cel puţin una dintre relaţiile x=y sau x+y=0 şi apoi calculează câte drepte distincte trec prin cel puţin două dintre aceste puncte.

La al treilea nivel, Alexandru numără şi şterge punctele din 3 în 3 (primul, al 4-lea, al 7-lea etc.), începând cu cel mai din stânga punct desenat şi continuând către dreapta. Dacă două sau mai multe puncte au aceeaşi abscisă, el le numără pe acestea de jos în sus (începând de la punctul cu ordonata cea mai mică). Când a ajuns cu număratul la cel mai din dreapta punct continuă cu cel mai din stânga punct rămas.

Alexandru se opreşte cu numărarea şi ştergerea când rămâne un singur punct desenat pe foaie.

Scrieţi un program care citeşte numărul natural nenul N, apoi cele 2*N numere întregi ce reprezintă coordonatele celor N puncte şi determină:

a) NRP, numărul maxim de puncte (dintre cele desenate) aflate pe una dintre axele sistemului cartezian sau pe o dreaptă paralelă cu una dintre cele două axe;
b) NRD, numărul de drepte distincte care trec prin cel puţin două dintre punctele desenate a căror abscisa x şi ordonată y verifică cel puţin una dintre relaţiile x=y sau x+y=0;
c) XP reprezentând abscisa punctului rămas pe foaie la sfârşitul celui de-al treilea nivel al jocului.