Lista de probleme 14

Se consideră un triunghi alcătuit din numere naturale scrise pe n linii ca în figura alăturată. Liniile triunghiului sunt numerotate de la 1 la n, începând cu linia de la baza triunghiului (linia de jos), iar poziţiile pe linie sunt numerotate începând cu 1 de la stânga la dreapta.
Fiecare număr din triunghi, exceptând pe cele de pe linia 1, este egal cu suma numerelor aflate imediat sub el, în stânga şi respectiv în dreapta lui.

Cunoscând câte un număr de pe fiecare linie a triunghiului, determinaţi toate numerele de pe linia 1.

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

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.

Un teren de fotbal este folosit pentru aterizarea elicopterelor. Gazonul de pe stadion este parcelat în pătrăţele de aceeaşi dimensiune, cu laturile paralele cu marginile terenului. Liniile cu pătrăţele de gazon sunt numerotate de sus în jos cu numerele 1, 2, …, m, iar coloanele cu pătrăţele de gazon sunt numerotate de la stânga la dreapta cu numerele 1, 2, …, n. Din cauza tipului diferit de iarbă se ştie care dintre pătrăţele de gazon sunt afectate sau nu de umbră. Acest lucru este precizat printr-un tablou bidimensional a cu m linii şi n coloane, cu elemente 0 şi 1 (aij = 0 înseamnă că pătrăţelul aflat pe linia i şi coloana j este afectat de umbră, iar aij = 1 înseamnă că pătrăţelul aflat pe linia i şi coloana j nu este afectat de umbră). Fiecare elicopter are 3 roţi pe care se sprijină. Roţile fiecărui elicopter determină un triunghi dreptunghic isoscel. Elicopterele aterizează, astfel încât triunghiurile formate să fie cu catetele paralele cu marginile terenului. În exemplul următor avem patru elicoptere.

Pentru a preciza poziţia unui elicopter pe teren este suficient să cunoaştem linia şi coloana vărfurilor ipotenuzei şi poziţia vârfului deasupra (codificată prin 1) sau dedesubtul ipotenuzei (codificată prin -1). Pentru exemplu, elicopterul din stânga sus este dat prin (1,1), (3,3) şi -1, cel din dreapta sus prin (1,9), (5,5) şi 1, cel din stânga jos prin (5,1), (6,2) şi 1, iar cel din dreapta jos prin (5,9), (6,8) şi 1.

Un elicopter se consideră că a aterizat greşit, dacă triunghiul format sub el (definit mai sus) are mai mult de jumătate din pătrăţele afectate de umbră.

Administratorul terenului de fotbal doreşte să determine numărul N1 de elicoptere, care nu afectează nici un pătrăţel din teren şi numerele de ordine al elicopterelor, care au aterizat greşit în ordine crescătoare: e1, e2, …, eN2, ştiind că există k elicoptere codificate prin numerele 1, 2, …, k.

Scrieţi un program care să determine, pentru fişierul cu datele din enunţ: numărul de elicoptere N1, care nu afectează nici un pătrăţel din teren şi numerele de ordine al elicopterelor, care au aterizat greşit în ordine crescătoare, precedate de numărul lor N2.

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.

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.

Una dintre atracţiile celebrului parc de distracţii Prater din Viena este Marea Roată Vieneză. Din ea se poate admira priveliştea întregii Viene.

Roata are n cabine, numerotate de la 1 la n în sens orar şi dispuse simetric pe circumferinţa roţii. Îmbarcarea clienţilor se face în cabina în care roata este tangentă cu solul, iar rotirea începe cu cabina 1 aflată în poziţia de îmbarcare şi se face în sens antiorar. Un client plăteşte pentru o rotire 1 EUR şi poate cumpăra un număr oarecare de rotiri.

Cei p clienţi care doresc utilizarea roţii trebuie să respecte următoarea procedură: clientul cu numărul de ordine i îşi cumpără un bilet pe care sunt înscrise numărul său de ordine şi numărul de rotiri ci, 1≤ i ≤ p, apoi se aşează la rând. Când în poziţia de îmbarcare este o cabină liberă sau se eliberează o cabină, roata se opreşte şi urcă următorul clientul. Un client coboară după ce se efectuează numărul de rotiri înscris pe bilet.

Să se scrie un program care, cunoscând numărul n de cabine al roţii, numărul p de clienţi, precum şi numărul de rotiri cumpărate de fiecare client, ci, 1≤ i ≤ p, să calculeze:

• suma totală încasată de administratorul roţii de la clienţi;
• ordinea în care coboară clienţii din roată;
• numărul cabinei din care coboară ultimul client.

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.

O invazie de N farfurii zburătoare (denumite uzual OZN) dă bătăi de cap autorităţilor. În fiecare astfel de OZN se află extratereştri care au ca misiune distrugerea planetei noastre. Radarul care a detectat invazia are un ecran similar cu planul XOY. Fiecare OZN este reprezentat pe ecran printr-un segment de dreaptă.

Pentru anihilarea OZN-urilor, autorităţile dispun de K arme laser. Armele sunt poziţionate pe sol (ilustrat pe ecranul radarului prin axa OX). Fiecare armă emite o rază laser, ilustrată pe ecran printr-o paralelă cu axa OY. Dacă o rază laser intersectează segmentul de pe ecranul radarului corespunzător unui OZN, raza va omorî toţi extratereştrii aflaţi în OZN-ul respectiv.

Din păcate, în preajmă se află doar un militar specializat în arme laser, aşa că autorităţile doresc să ştie exact ce armă trebuie să folosească acesta pentru a distruge cât mai mulţi extratereştri.

Ajutaţi autorităţile să determine numărul de extratereştri care pot fi anihilaţi cu fiecare armă din dotare.

Pasiunea Mirunei este să coloreze. Vacanţa trecută şi-a petrecut-o la bunica ei la ţară şi pentru că se cam plictisea s-a gândit să vopsească gardul de la casa bunicii.

Gardul este compus din N scânduri dispuse una lângă alta. Miruna a găsit în garajul bunicii 5 cutii de vopsea de culori diferite: albă, albastră, roşie, verde şi galbenă. Când a vopsit gardul, Miruna a respectat următoarele reguli:

1. Dacă o scândură era vopsită cu alb, următoarea scândură o vopsea obligatoriu cu albastru
2. Dacă o scândură era vopsită cu albastru, atunci următoarea scândură o vopsea cu alb sau roşu
3. Dacă o scândură era vopsită cu roşu, atunci următoarea scândură o vopsea cu albastru sau verde
4. Dacă o scândură era vopsită cu verde, atunci următoarea scândură o vopsea cu roșu sau galben
5. Dacă o scândură era vopsită cu galben, atunci următoarea scândură o vopsea obligatoriu cu verde

După ce a și-a terminat treaba Miruna își admira “opera de artă” și se întreba în câte moduri diferite ar fi putut să vopsească gardul bunicii.