Lista de probleme 1988

Filtrare

#1137 Cuart

Gina şi Mihai joacă împreună jocul Cuart. Ei au la dispoziție un șir de 2*N cartonașe ce conțin numere naturale. Primele N cartonașe, de la stânga la dreapta, sunt ale Ginei, iar următoarele N ale lui Mihai. Gina traversează șirul, de la stânga la dreapta și scrie pe o foaie de hârtie, pe primul rând, un șir de numere obținut din numerele de pe cartonașele sale, din care a șters toate cifrele pare. La fel procedează Mihai care scrie pe foaia sa de hârtie, pe primul rând, șirul de numere obținut din numerele de pe cartonașele sale, din care a șters toate cifrele impare. Dacă dintr-un număr s-au șters toate cifrele, sau au rămas doar cifre egale cu 0, atunci numărul este ignorat, deci pe hârtie nu se scrie nimic.
Fiecare copil, notează pe hârtia sa, pe al doilea rând, un alt șir de numere obținut astfel: pentru fiecare număr X scris pe primul rând, copilul va scrie cel mai mare număr natural K cu proprietatea că 1+5+9+13+...+ K ≤ X. În jocul copiilor, numărul X se numește cuarț dacă 1+5+9+13+...+K = X.

În exemplul de mai sus, Gina nu a scris niciun număr cuarț pe primul rând, iar Mihai a scris unul singur (6=1+5).

Regulile de câștig ale jocului sunt următoarele:

  • Câștigă acel copil care are scrise pe primul rând cele mai multe numere cuarț. În acest caz, valoarea de câștig a jocului este egală cu numărul de numere cuarț scrise de copilul câștigător.
  • Dacă cei doi copii au scris același număr de numere cuarț, atunci va câștiga cel care are primul număr scris pe primul rând, mai mare decât al celuilalt. Acest prim număr scris de câștigător va reprezenta valoarea de câștig.
  • Dacă nici Gina și nici Mihai nu au scris niciun număr pe hârtie, se consideră egalitate și nu câștigă niciunul.

Scrieţi un program care să citească numărul N reprezentând numărul de cartonașe ale unui copil şi cele 2*N numere de pe cartonașe, în ordine de la stânga la dreapta și care să determine:

1) Cel mai mare număr de pe cele 2*N catonașe, pentru care nu s-a scris niciun număr pe primul rând (a fost omis), nici pe hârtia Ginei, nici pe hârtia lui Mihai; dacă nu a fost omis niciun număr, se va scrie 0;
2) Câștigătorul jocului și afișează numărul 1 dacă a câștigat Gina, 2 pentru Mihai sau 0 în caz de egalitate.
3) Valoarea de câștig a jocului, sau 0, în caz de egalitate.

Maria a aflat că numerele naturale care încep cu cifra 1 și au toate cifrele ordonate strict crescător şi consecutive sau încep cu cifra 9 și au toate cifrele ordonate strict descrescător şi consecutive se numesc numere speciale. Interesată să descopere legătura dintre numerele speciale cu același număr de cifre, a observat că poate construi tabelul alăturat.

Scrieţi un program care citind patru numere naturale K, N, A şi B determină:

1) cel mai mare număr special situat în tabel pe linia K;
2) numărul special obţinut din numărul N prin ştergerea unei cifre;
3) numărul de numere speciale din mulțimea {A , A +1, A+2, A+3…,B-1,B}.

#1139 Covor

Bunica Marei țese un covor. Mara urmărește cu mare atenție modelul și încearcă să-l reconstituie pe caietul de matematică. Modelul este format din romburi. Primul romb, de indice 1, are latura formată din două pătrățele, al doilea romb, de indice 2, are latura formată din trei pătrățele etc. Un romb de indice i are latura formată din i+1 pătrățele.
Romburile sunt unite, consecutiv, ca în exemplul din imaginea alăturată. Săgețile indică sensul în care bunica țese covorul.

Ca să nu uite modelul, Mara scrie pe caiet, începând cu 1, numere consecutive care să indice modul în care țese bunica covorul.

În exemplul următor este reprezentat modul în care se țese un model format din patru romburi.

Cunoscându-se numerele n și k să se determine:

1. numărul maxim de romburi complete care pot forma modelul unui covor, descris cu ajutorul unui șir format din maximum n numere naturale consecutive (primul număr din șir fiind 1);
2. cel mai mic indice al unui romb ce conține numărul k.

#1140 Ordine

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

OJI 2015, Clasa a VI-a

#1141 ech

Numim număr echilibrat un număr natural pentru care suma cifrelor de pe poziţii pare este egală cu suma cifrelor de pe poziţii impare.

De exemplu numărul 13552 este echilibrat, pentru că 1+5+2=8=3+5.

Dat fiind un număr natural N să se determine cel mai mic număr echilibrat, strict mai mare decât N.

#1142 Lasere

Se consideră un teren reprezentat printr-o matrice cu n linii şi n coloane având elemente numere naturale. În fiecare element al matricei este memorată înălţimea zonei de teren corespunzătoare ca poziţie elementului respectiv. Pe acest teren sunt amplasate m lasere, în poziţii cunoscute. Un laser este îndreptat spre unul dintre cele 4 puncte cardinale, codificate prin numere astfel: Nord prin valoarea 1, Est prin valoarea 2, Sud prin valoarea 3 şi respectiv Vest prin valoarea 4. Fiecare laser va executa o singură tragere şi ca urmare va scădea cu 1 valorile tuturor elementelor din matrice din direcţia sa de tragere, exceptând poziţia laserului respectiv.

După efectuarea tuturor tragerilor, se caută poziţiile tuturor gropilor şi ale tranşeelor.

Numim groapă un element din matrice pentru care toate cele 8 elemente învecinate pe linie, coloană sau diagonale au valori mai mari sau egale decât el.

Numim tranşee o secvenţă maximală formată din două sau mai multe gropi situate pe aceeaşi linie, pe coloane consecutive. Secvenţa se numeşte maximală dacă nu mai poate fi prelungită la niciunul dintre capete.

Cunoscând configuraţia terenului şi amplasarea laserelor, să se rezolve una dintre următoarele două cerinţe:

1. să se determine numărul de gropi din teren, după executarea tragerilor;
2. să se determine numărul de tranşee existente, după executarea tragerilor.

Considerând un șir de valori binare, numim secvență dominantă un set de elemente aflate pe poziții consecutive în șir care are proprietatea că numărul valorilor egale cu 1 este strict mai mare decât numărul valorilor de 0. De exemplu, în șirul 1,0,0,0,1,1,0,1,1,1,0,0 o secvență dominantă este 0,1,1 și o alta, de lungime mai mare, este 0,1,1,0,1,1,1. Secvența dominantă maximală este secvența dominantă de lungime maximă. În șirul din exemplu secvența dominantă maximală este 1,0,0,0,1,1,0,1,1,1,0 (adică întreg șirul, fără ultimul zero).

Dat fiind un șir de valori binare, să se determine lungimea unei secvențe dominante maximale precum și numărul acestor secvențe.

#1144 Pavare1

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.

OJI 2015, Clasa a VIII-a

Gigel, mare amator de probleme de matematică şi informatică, a observat că unele numere prime au o proprietate interesantă: orice cifră ar elimina dintr-un astfel de număr, numărul obţinut este tot număr prim. A numit astfel de numere numere extraprime. De exemplu, numărul 317 este un număr extraprim: el este număr prim şi, în plus, dacă eliminăm cifra 3, obţinem 17, care este prim; dacă eliminăm 1, obţinem 37, care este prim; dacă eliminăm 7, obţinem 31, care este şi el număr prim.

Spunem că x este între a şi b dacă x≥a şi x≤b. Fiind date două valori naturale a şi b, să se determine câte numere extraprime există între a şi b, precum şi cel mai mic şi cel mai mare număr extraprim dintre a şi b.

#1146 Greieri

Pe o linie orizontală se găsesc n greieri. Ei încep să stea „capră” într-o ordine prestabilită începând cu ultimul, pe rând, până la primul. Toţi greierii care îl preced pe cel care stă „capră” sar peste acesta, în ordine.

De exemplu pentru n=4, mai întâi stă „capră” greierul 4 și peste el sar, în ordine, 3, 2 și 1. Apoi stă „capră” greierul 3 și sar peste el, în ordine, 2, 1 și 4. Apoi stă „capră” greierul 2 și peste el sar, în ordine, 1, 3 și 4. Apoi stă „capră” greierul 1 și sar peste el, în ordine, 4 , 3 și 2, și se revine la ordinea inițială.

Scrieți un program care citește numerele naturale n și m și determină:

a) De câte sărituri este nevoie pentru a se ajunge la ordinea inițială?
b) Cum vor fi așezați greierii după m sărituri?

ONI 2013, Clasa a V-a