Lista de probleme 160

Zarul folosit la diverse jocuri este un cub care are desenat pe fiecare faţă a sa 1, 2, 3, 4, 5 sau 6 puncte. Pe un zar nu există două feţe cu acelaşi număr de puncte şi suma punctelor de pe oricare două feţe opuse este egală cu 7.

Pe o masă de joc este desenat un traseu în formă de pătrat, cu latura de dimensiune n. Fiecare latură a traseului este împărţită în n pătrăţele identice, care au latura egală cu cea a zarului. Zarul este aşezat iniţial în colţul din stânga sus al traseului şi apoi rostogolit de pe o faţă pe alta, din pătrăţel în pătrăţel, de-a lungul traseului parcurs în sensul acelor de ceasornic.

În orice moment ne-am uita la zar, putem vedea numărul punctelor desenate pe trei din feţele sale (aşa cum se vede în desenul de mai sus).

Notăm cu f1 faţa cubului orientată spre noi, f2 faţa superioară a cubului, respectiv cu f3 faţa laterală din dreapta. Pentru exemplul din figură: n=4, faţa dinspre noi (f1) conţine trei puncte, faţa superioară (f2) conţine două puncte, faţa laterală din dreapta (f3) conţine un punct, iar sensul de deplasare este cel precizat prin săgeţi.

Cunoscând dimensiunea n a traseului şi numărul punctelor de pe cele trei feţe ale zarului în poziţia iniţială, determinaţi după k rostogoliri numărul punctelor ce se pot observa pe fiecare din cele trei feţe ale zarului.

Mariei îi plac numerele prime şi puterile numerelor prime. Pornind de la un număr prim p, ea construieşte noi numere, fiecare număr construit fiind un produs de forma py (y număr natural nenul) sau q∙pm, m număr natural şi q un număr prim, numindu-le numere p-prime. De exemplu, numerele 2, 3, 4, 5, 6, 7, 8, 10, 12, 13, 14, 16, 17 sunt primele 13 numere 2-prime deoarece 2=21, 3=3•20, 4=22, 5=5•20, 6=3•21, 7=7•20, 8=23, 10=5•21, 12=3•22, 13=13•20, 14=7•21, 16=24, 17=17•20.

Într-o zi Maria a găsit o foaie de hârtie, pe care era scris un şir format din n numere naturale nenule.

Cum pe lângă numerele p-prime ea este pasionată şi de secvenţe, şi-a pus următoarea întrebare: câte secvenţe sunt pe foaie cu următoarele proprietăţi:

• conţin exact k numere p-prime;
• încep şi se termină cu un număr p-prim.

În plus, Maria doreşte să ştie care este poziţia de început şi cea de final, pentru fiecare secvenţă descoperită, relative la şirul scris pe foaia de hârtie.

Scrieţi un program care să citească mai multe seturi de date, fiecare set fiind format din numerele n, p, k, cu semnificaţiile din enunţ, şi şirul cu n elemente a1, a2, a3, … an, numerele Mariei. Programul va determina pentru fiecare set de date numărul secvenţelor ce conţin exact k numere p-prime, precum şi poziţiile de început şi de final ale acestor secvenţe în şirul din set.

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.

Gigel a primit de ziua lui un joc cu bile. Jocul conţine n bile numerotate cu numerele naturale distincte de la 1 la n. Jucându-se, Gigel a amestecat bilele astfel încât acum ele nu mai sunt în ordine. Ca să le pună înapoi în cutia jocului, Gigel ia de pe masă bilele una câte una, şi le pune în cutie formând un şir. Însă Gigel se joacă şi acum, astfel încât el nu pune bilele la rând, una după alta, ci are o regulă pe care o respectă cu stricteţe. Astfel, Gigel încearcă să plaseze fiecare bilă pe care a luat-o de pe masă exact la mijlocul şirului de bile deja format. Dacă acest lucru nu este posibil (șirul are lungime impară), atunci el plasează bila la sfârşitul şirului de bile deja format. După ce toate bilele au fost puse în cutie, Gigel îşi dă seama că nu a notat ordinea în care a luat bilele de pe masă şi, în mod firesc, îşi pune problema dacă nu cumva poate deduce acest lucru din şirul de bile pe care tocmai l-a format.

Cunoscându-se numărul de bile şi configuraţia finală a bilelor în şir să se determine:

1. numărul ultimei bile luate de pe masă;
2. ordinea în care bilele au fost luate de pe masă.

Ca în mai toate poveștile, Făt-Frumos a căutat o Cosânzeană și a găsit-o, dar tatăl ei i-a cerut să-i paveze drumul de lungime N care leagă castelele sale. Dalele cu care va pava drumul au aceeași lățime (egală cu lățimea drumului) și lungimi numere naturale. Fiind un împărat cam sâcâit, acesta dorește ca pavarea să se facă folosind un număr minim de dale, diferența de lungime între două dale vecine să nu fie mai mare ca 1, iar prima și ultima dală să fie de lungime 1. Împăratul nu se mulțumește să primească de la Făt-Frumos doar un număr (numărul minim de dale necesare): el vrea și posibilitatea de pavare cea mai mică din punct de vedere lexicografic.

Cunoscând lungimea drumului, determinați numărul minim de dale necesare pavării și posibilitatea de pavare cu număr minim de dale, care este cea mai mică din punct de vedere lexicografic.

Un copil dorește să găsească un mod original de a-și codifica numele și folosește în acest scop o figură formată doar din triunghiuri, desenată pe o foaie de hârtie. El plasează fiecare literă din numele său, în câte un triunghi. Dacă numele lui este DARIUS, atunci foaia de hârtie va arăta ca în figura 1. Pe primul rând așează prima literă, pe al doilea rând următoarele trei litere, pe al treilea rând următoarele cinci litere, și așa mai departe până când așează toate literele din nume. Dacă numele nu are suficiente litere, copilul folosește caracterul * pentru a completa ultimul rând pe care pe care a așezat litere. Nemulțumit că numele poate fi citit relativ ușor, răstoarnă figura, rotind foaia de hârtie, în sensul acelor de ceasornic, obținând astfel figura 2.

Cunoscând literele numelui, scrieți un program care determină și afișează în fișierul de ieșire:

1. Numărul de caractere * pe care trebuie să le utilizeze pentru a completa ultimul rând;
2. Prima literă de pe fiecare rând din figura inițială;
3. Șirul literelor de pe fiecare rând, după rotirea foii de hârtie.

Se consideră o tablă de şah cu n linii şi n coloane, şi n=4k+1. Liniile acestei table sunt numerotate de sus în jos începând cu linia 1, iar coloanele sunt numerotate de la stânga la dreapta începând cu 1. În fiecare dintre câmpurile acestei table se scrie câte un număr natural din mulţimea {1, 2, …, n2} după următoarele reguli:

a) se porneşte din colţul aflat în poziţia stânga sus al tablei şi se avansează utilizând săritura calului
b) se merge orizontal către dreapta şi în continuare, pe chenarul format din primele două linii, primele două coloane, ultimele două linii şi ultimele două coloane, în sensul acelor de ceasornic;
c) se efectuează mai multe tururi ale tablei, până ce se umple întregul chenar, fără să se sară de două ori în aceeaşi căsuţă, fără să se sară în afara acestui chenar şi fără să rămână vreun câmp liber;
d) din poziţia finală în care s-a ajuns, trebuie să fie posibilă săritura în colţul din stânga sus al pătratului rămas neacoperit;
e) se continuă deplasarea în interiorul pătratului rămas neacoperit, folosind regulile a), b), c), d) până ce se ajunge la pătratul interior de latură 1 care va conţine valoarea n2.

Cunoscând valoarea lui n ce reprezintă dimensiunea tablei şi un număr p, să se determine linia şi coloana căsuţei din tabelă unde este scris numărul p, după regulile de mai sus.

În planul xOy se desenează un dreptunghi cu laturile paralele cu axele de coordonate. Coordonatele vârfurilor din stânga-jos şi dreapta-sus ale dreptunghiului sunt: (0,0) şi (c,d). Fie P mulţimea punctelor situate în interiorul dreptunghiului, ale căror coordonate sunt numere naturale. Prin desenarea unui număr minim m de segmente de dreaptă, se uneşte vârful de coordonate (0,0) cu fiecare punct din mulţimea P. Astfel, fiecare punct din P va aparţine interiorului unui segment din cele m sau va fi o extremitate a unui segment din cele m.

Scrieţi un program care să citească numerele naturale c şi d, şi care să determine numărul minim m de segmente de dreaptă desenate.

Fie un număr natural a având n cifre. Scrieţi un program care să determine un număr natural x cu proprietatea că este cel mai mic număr mai mare decât a, care are exact aceleaşi cifre ca şi numărul a.

Fiind date două tablouri bidimensionale a şi b, cu m linii şi n coloane fiecare, definim următoarele operaţii:

1. suma tablourilor a şi b, ca fiind un tablou c cu m linii şi n coloane, în care fiecare element este egal cu suma elementelor de pe aceeași linie şi aceeași coloană din a şi b. În acest caz folosim operatorul +, adică c=a+b.
2. produsul tablourilor a şi b, ca fiind un tablou d cu m linii şi n coloane, în care fiecare element este egal cu produsul elementelor de pe aceeași linie şi aceeași coloană din a şi b. În acest caz folosim operatorul *, adică d=a*b. Dacă a şi b sunt tablouri identice (a şi b au elemente identice pe aceeaşi poziţie), atunci pentru d se mai foloseşte şi notaţia a2 sau b2.

De exemplu, pentru m=2, n=3 şi tablourile:

se obține:

Fiind dat un tablou bidimensional a, cu m linii, n coloane şi componente numere naturale dorim să determinăm un şir de tablouri bidimensionale: b1, b2, …, bk cu număr minim de termeni (k minim), cu proprietatea că a=b12+b22...+bk2.