Lista de probleme 17

Etichete

#2960 abx

Un număr natural n se numește putere dacă există două numere naturale a,b, a ≥ 1, b ≥ 2 astfel încât \(n = a^b\). De exemplu, numerele 32 , 169 , 1 sunt puteri (\(32 = 2^5\) , \(169 = 13^2\) , \(1 = 1^2\) ), iar 72 , 2000 și 31 nu sunt puteri.
Se citesc numerele naturale N , M și un șir de N numere naturale \(x_1, x_2, …, x_N\) din intervalul [1,M].

Pentru fiecare din cele N numere \(x_i\) determinați câte un număr natural \(r_i\) din intervalul [1,M], cu proprietatea că \(r_i\) este o putere și pentru orice altă putere p din intervalul [1,M] este îndeplinită condiția \(|x_i – r_i| ≤ |x_i – p|\), unde |x| reprezintă valoarea absolută a lui x (modulul).
Dacă există două puteri egal depărtate de \(x_i\) se va alege puterea cea mai mică. De exemplu pentru numărul 26, dintre puterile 25 și 27 va fi ales numărul 25.

Într-o școală există un sistem de acces cu ajutorul cartelelor, conectat la un calculator și o imprimantă. Fiecare elev al școlii are câte o cartelă. Într-o zi, la utilizarea fiecărei cartele, sistemul imprimă următoarele informații pe hârtie, pe câte o linie, după regula următoare:
- Caracterul b dacă elevul este băiat sau caracterul f dacă este fată. Caracterul va fi urmat de un spațiu;
- Caracterul i dacă elevul a intrat în școală sau caracterul e dacă a ieșit din școală. De asemenea, acest caracter va fi urmat de un spațiu;
- Momentul utilizării cartelei, exprimat prin oră, minute și secunde. Acestea vor fi reprezentate în cadrul liniei, exact în această ordine, prin trei numere naturale, separate între ele prin câte un spațiu.

Cunoscându-se toate cele N linii imprimate într-o zi determinați:
1. Câți băieți și câte fete sunt la școală după cele N acțiuni imprimate de sistem.
2. Care este numărul total de secunde în care, în școală, s-au aflat un număr egal, nenul, de fete și băieți, până în momentul utilizării ultimei cartele. Dacă nu există această situație se afișează 0.
3. Care este numărul maxim de secunde în care, în școală, până în momentul utilizării ultimei cartele, s-au aflat neîntrerupt un număr impar de băieți. Dacă nu există o astfel de situație se afișează 0.

#2978 aur

După ce au mers împreună prin lume, Păcală și Tândală au strâns o căruță plină de bănuți de aur, iar acum îi răstoarnă pe toți în curtea casei și îi împart în N grămezi. Păcală numără bănuții din fiecare grămadă și îi dictează lui Tândală N numere naturale pe care acesta trebuie să le scrie în ordine pe o tăbliță. După ore bune de muncă, Păcală constată că Tândală a scris pe un singur rând, în ordine, de la stânga la dreapta, toate numerele dictate de el, dar lipite unul de altul. Acum pe tăbliță e doar un șir lung de cifre. Ce să facă Păcală acum?

Cunoscând cele N numere naturale dictate de Păcală, scrieți un program care să determine:
1. numărul cifrelor scrise pe tăbliță de Tândală;
2. ce-a de-a K-a cifră de pe tăbliță, în ordine de la stânga la dreapta;
3. cel mai mare număr ce se poate forma cu exact P cifre alăturate de pe tăbliță, considerate în ordine de la stânga la dreapta.

#2977 poarta1

Sindbad a descoperit un recipient care conține o poțiune magică și o inscripție care descrie cum se poate deschide poarta unui templu. Urmând instrucțiunile din inscripție, Sindbad a ajuns la un tunel acoperit cu dale pătrate, aliniate astfel încât formează linii și coloane. Tunelul are mai multe linii, iar pe fiecare linie sunt câte N dale. Dalele din tunel sunt numerotate începând cu 1, astfel încât, parcurgându-le linie cu linie și fiecare linie de la stânga la dreapta, se obține un șir strict crescător de numere naturale consecutive.
Sindbad se află la intrare, înaintea primei linii. Pentru a deschide poarta templului, el trebuie să ajungă pe dala numerotată cu P, călcând pe un număr minim de dale. Dacă există mai multe astfel de soluții, o va alege pe cea pentru care consumul total de picături de poțiune magică este minim.

Scrieți un program care citește valorile N și P și rezolvă următoarele cerințe:
1. afișează numărul minim de dale pe care trebuie să calce pentru a deschide poarta;
2. afișează numărul natural T, reprezentând numărul minim de picături de poțiune magică necesare pentru deschiderea porții.

#2976 maxim7

Dintr-un șir format din N cifre, numerotate de la 1 la N, Ionel ia exact M cifre aflate pe poziții consecutive. El lipește cifrele luate sau le amestecă și apoi le lipește pentru a obține cu ele un număr cât mai mare. Cunoscând N, M și cele N cifre din șir, să se determine:
1) cel mai mare număr care se poate obține din primele M dintre cele N cifre date;
2) de unde va lua Ionel M cifre aflate pe poziții consecutive pentru a obține un număr maxim; dacă sunt mai multe poziții corespunzătoare unui număr maxim, alegerea se va face astfel încât numărul format din cifrele rămase, în ordinea în care erau, să fie cât mai mare posibil; dacă și în acest caz există mai multe soluții, se alege poziția maximă.

Gigel, pasionat de numere, știe că orice număr natural se scrie într-o bază de numerație b ca o succesiune de simboluri care au asociate valori de la 0 la b-1. De exemplu numărul 7, scris în baza 10, se scrie în baza 2 ca 111(2), iar numărul 26732, scris în baza 10, se scrie în baza 37 ca o succesiune de 3 simboluri, primele două având asociată valoarea 19, iar ultimul având asociată valoarea 18. El a descoperit că există numere care au proprietatea că se scriu, în exact două baze diferite, prin exact trei simboluri identice. De exemplu, numărul 931(10) se scrie în baza 11 ca 777(11), iar în baza 30 se scrie 111(30). Fiind dat un număr natural N, să se determine cel mai mare număr natural mai mic sau egal cu N, care are proprietatea că se scrie în exact două baze diferite prin exact 3 simboluri identice.
1. Să se scrie numărul determinat
2. Să se scrie cele două baze determinate și valorile simbolurilor respective.

Avem o matrice de dimensiuni N x M, cu elemente 0 și 1. Numim segment o secvență de cel puțin două valori 1 aflate una lângă alta, toate pe aceeași linie, sau toate pe aceeași coloană a matricei. Se cere determinarea numărului de perechi de segmente:
1. aflate pe linii distincte ale matricei;
2. aflate pe coloane distincte ale matricei;

#2980 valutar

Valutar este un joc care poate fi jucat de oricâți jucători. La începutul jocului, fiecare jucător primește L lei și E euro, precum și un jeton numerotat cu numărul jucătorului. Scrieți un program care să rezolve următoarele cerințe:
1. determină numărul de jucători existenți în joc după X mutări;
2. determină jucătorul care a rămas în joc și care are cea mai mare sumă de Euro după X mutări.

Pe un teren de formă dreptunghiulară format din L linii și C coloane sunt plantate M mine. Liniile sunt numerotate de sus în jos cu valori de la 1 la L iar coloanele sunt numerotate de la stânga la dreapta cu valori de la 1 la C. Deoarece războiul s-a terminat, specialiștii vor să demineze terenul și să-l redea utilizării publice. Mutarea unei mine reprezintă operația de transfer a unei mine de la linia x1 și coloana y1 la o poziție liberă, dată de linia x2 și coloana y2, unde 1 ≤ x1, x2 ≤ L și 1 ≤ y1, y2 ≤ C. Deoarece mutarea unei mine este periculoasă, trebuie determinat numărul minim de mine care trebuie mutate din poziția inițială astfel încât toate minele de pe teren să fie așezate unele lângă altele într-o zonă compactă dreptunghiulară, oriunde în cadrul terenului dat, pentru ca apoi să fie detonate împreună.

Cunoscând numărul de linii L și de coloane C ale terenului minat, numărul de mine M, precum și poziția fiecărei mine, să se scrie un program care determină:
1. linia sau liniile pe care se găsesc cele mai multe mine;
2. numărul minim de mine mutate, pentru ca toate minele de pe teren să fie așezate într-o zonă compactă cu formă dreptunghiulară.

#2962 traseu3

O suprafață de teren de formă dreptunghiulară este divizată în N fâșii orizontale și M fâșii verticale, de lățimi egale. Se formează astfel N x M zone de formă pătrată, cu latura egală cu o unitate. Astfel, suprafața este reprezentată sub forma unui tablou bidimensional cu N linii și M coloane, în care pentru fiecare zonă este memorat un număr ce reprezintă altitudinea zonei respective. Interesant este că în tablou apar toate valorile 1, 2, …, N•M. Suprafața este destinată turismului. Deoarece spre laturile de Est și Sud ale suprafeței există peisaje de o frumusețe uimitoare, se dorește găsirea unor trasee turistice în care deplasarea să se realizeze cu pași de lungime unitară mergând doar spre Est și spre Sud. O comisie, care trebuie să rezolve această problemă, a stabilit că un traseu este atractiv dacă și numai dacă ultima poziție a traseului are altitudinea mai mare decât prima poziție a traseului. Un traseu poate începe, respectiv se poate încheia, în oricare dintre zonele terenului, cu respectarea condițiilor anterioare. Se cere să se determine numărul maxim Z de zone pe care le poate avea un traseu atractiv.