Lista de probleme 687

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

Se dă un șir de N numere distincte a[1],a[2],..a[N]. Orice secvență
a[i],a[i+1],...,a[j-1],a[j], 1 ≤ i + 1 < j ≤ n, pentru care toate valorile a[k],
i < k < j, sunt mai mici decât extremitățile a[i] și a[j], o vom numi în continuare “groapă”.

Scrieţi un program care va determina numărul “gropilor” din șirul dat.

#696 Mario

Jocurile cu Mario sunt jocuri on-line pentru copii de toate vârstele. Acum, Mario-personajul din joc, are nevoie de ajutorul vostru pentru a ajunge din turnul castelului unde se află, la sol, unde îl așteaptă cu nerăbdare prințesa Peach.

Coborârea din turn se face cu ajutorul unor platforme orizontale, de diferite lungimi, fiecare dintre ele aflându-se la o anumită înălțime față de sol. Deplasarea din turn spre sol se va face astfel:

  • Mario își dă drumul în cădere liberă din turn și cade sub efectul greutății sale;
  • dacă în cădere, el ajunge pe o platformă, se va deplasa pe suprafața acesteia spre unul din capetele din stânga sau din dreapta ale acesteia, urmând ca de acolo să procedeze la fel, lăsându-se din nou în cădere liberă spre sol.

Dacă Mario cade pe o distanță mai mare decât H, atunci își pierde toată energia și nu mai poate continua jocul.

Cunoscând poziția în care se află Mario și modul de așezare al platformelor (date în coordonate carteziene), determinați numărul drumurilor distincte pe care le poate parcurge Mario pentru a ajunge la prințesă.

Lot Juniori, Deva, 2013

Undeva, în deșertul Sahara, ilustrul biolog Sahraa Gaea a conceput și construit un sistem de irigații ingenios, sistem cu care își propune să irige o zonă deșertică dreptunghiulară bogată în nutrienți minerali. Zona deșertică este împărțită în N*M pătrate de latură unitate. În fiecare pătrat se află un dispozitiv de picurare ce asigură o anumită cantitate de apă în funcție de comanda primită de la centrul de control al sistemului.

Sistemul de irigare este astfel conceput încât să irige (ude), pe baza unor comenzi automatizate, parcele dreptunghiulare ale regiunii deșertice.

Orice parcelă are laturile paralele cu laturile zonei deșertice și este identificată prin coordonatele colțurilor stânga-sus (x1,y1), respectiv dreapta-jos (x2,y2). La fiecare comandă se specifică parcela care va fi udată și cantitatea de apă (exprimată în litri) cu care va fi irigat fiecare pătrat al acesteia.

Un pătrat al zonei deșertice devine fertil dacă acumulează cel puțin Q litri de apă.

Să se determine aria maximă a unei suprafețe conexe fertile. Prin aria unei suprafețe înțelegem numărul de pătrate ce compun suprafața. Orice două pătrate fertile care au o latură comună fac parte din aceeaşi suprafaţă conexă fertilă.

#688 pixy

Pixy locuieşte într-o ţară colorată. Harta ţării poate fi reprezentată sub forma unui dreptunghi împărţit în celule, organizate în M linii şi N coloane. Liniile sunt numerotate de la 1 la M, începând de la linia de sus, iar coloanele sunt numerotate de la 1 la N începând de la coloana din stânga. Fiecare celulă are o anumită culoare. Culorile sunt codificate cu literele A, B, C, D, E, F (există doar 6 culori).

Casa lui Pixy se găseşte în celula de coordinate (1,1), iar prietena lui, Pixela, locuieşte în celula de coordonate (M,N). Pixy doreşte să ajungă la aleasa inimii sale, însă nu poate păşi decât pe celule de aceeaşi culoare. Ştim că Pixy se poate deplasa doar orizontal, sau vertical cu câte o căsuţă la fiecare pas.

Pentru a putea ajunge la Pixela, Pixy va proceda astfel: alege o culoare şi va recolora celula în care se găseşte casa sa cu culoarea aleasă. Astfel va obţine o zonă de celule adiacente având toate aceeaşi culoare. Două celule se consideră adiacente dacă se învecinează orizontal sau vertical. De exemplu, pentru harta din figura 1, dacă alege culoarea având codul D va obţine zona marcată din figura 2, toate celulele din această zonă având culoarea D.

În continuare Pixy va proceda asemănător: alege o nouă culoare, şi recolorează toată zona obţinută la pasul anterior cu noua culoare, astfel zona pe care poate păşi se lărgeşte. De exemplu, dacă în situaţia din figura 2, Pixy alege acum culoarea cu codul C va obţine situaţia din figura 3.

Procedeul continuă până când celula corespunzătoare casei Pixelei face şi ea parte din zona obţinută de Pixy în urma recolorărilor.

Alegerea culorilor de la fiecare pas trebuie făcută cu mare grijă, astfel încât numărul de recolorări să fie minim.

Acum lui Pixy îi mai rămâne sarcina de a găsi un drum cât mai scurt pe care îl va parcurge până la Pixela, păşind doar pe celulele din zona obţinută în urma recolorărilor succesive, adică celulele de pe parcursul drumului vor avea toate aceeaşi culoare.

Se cere să determinaţi:

a) numărul minim de recolorări
b) lungimea drumului minim de la Pixy la Pixela, parcurs pe zona obţinută în urma recolorărilor de la cerinţa a).

Lot Juniori, Sibiu 2011

#687 liste

Numim listă un sir de numere naturale. Avem la dispoziţie mai multe liste aşezate, în ordine, una sub alta. Spunem că două liste L1 şi L2 sunt vecine dacă L1 este imediat deasupra lui L2, sau dacă L2 este imediat deasupra lui L1. Oricare două liste vecine L1 şi L2 pot fi unificate dacă ele au cel puţin un element comun. Prin unificare, noua listă va avea ca elemente toate elementele din L1 la care se adaugă toate elementele din L2. Listele L1 şi L2 vor dispărea şi în locul lor va apărea noua listă.

Determinaţi numărul minim de liste care rezultă după aplicarea unui număr suficient de unificări astfel încât să nu mai existe două liste vecine care să poată fi unificate.

Lot Juniori, Sibiu 2011

#686 grad

Se consideră o propoziţie formată din litere mici ale alfabetului englez şi eventual spaţii. Cuvintele sunt formate numai din litere şi sunt separate între ele prin unul sau mai multe spaţii.

Definim numărul asociat unui cuvânt c1c2...ck ca fiind un număr natural nc, obţinut ca produsul puterilor de forma pi, unde p este poziţia în alfabet a literei ci. Astfel cuvântului badab i se asociază numărul nc=21∙12∙43∙14∙25, adică nc=4096.

Definim gradul unui cuvânt c1c2...ck ca fiind numărul nr modulo k, unde nr este numărul de divizori al lui nc. Gradul cuvântului badab este 3, pentru că nr=13 (cei 13 divizori ai lui 4096 sunt: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 şi 4096), k=5 (cuvântul conţine 5 litere) şi 13 modulo 5=3.

Definim gradul unei propoziţii ca fiind suma gradelor cuvintelor existente în ea.

Să se scrie un program care pentru o propoziţie dată determină gradul ei.

Lot Juniori, Sibiu 2011

Dorești să mergi în vacanță și ai hotărât deja destinația. Formal, te afli în punctul (0,0) al unui sistem cartezian de axe și trebuie să ajungi în punctul de coordonate (X,X). Țara în care te afli are drumuri paralele cu axele de coordonate la fiecare abscisă și la fiecare ordonată număr natural. În fiecare moment, dacă eşti în punctul de coordonate (a,b), ai 2 variante de deplasare: în punctul (a,b+1) sau în punctul (a+1,b). La fiecare astfel de pas consumi un litru de carburant. Prin unele puncte de forma (a,a) nu poți trece, iar în celelalte puncte care au abscisa egală cu ordonata poți trece și în plus, acolo se află câte o stație de benzină unde poți să „faci plinul”. Prin toate punctele care nu au abscisa egală cu ordonata poți trece dar acolo nu se află stații de benzină. Rezervorul mașinii tale are o capacitate de K litri.

Determinați numărul de trasee distincte prin care poți ajunge la destinație. Două trasee sunt distincte dacă diferă prin cel puţin un punct.

Lot Juniori, Vaslui, 2014

#678 mts

Alex a accesat fonduri europene și a pus bazele unei afaceri profitabile, constând în creșterea viermilor de mătase. Viermii de mătase se hrănesc cu frunze de dud, iar Alex are mulți duzi în grădină. El a observat că dacă așează un vierme de mătase pe o frunză de dud, acesta va mânca toată frunza într-un timp care depinde doar de mărimea suprafeței frunzei.

Alex a decis să le aplice viermilor săi de mătase un test de inteligență. În acest scop, a pus în practică următorul experiment științific: pe o bară îngustă, liniară, a așezat de la stânga la dreapta n frunze de dud având suprafețele s[1], s[2], … s[n], la distanțe x[1], x[2],…, x[n] milimetri față de capătul din stânga. Alex a așezat un vierme de mătase pe frunza cu numărul de ordine k. Pentru oricare frunză i, viermele de mătase va mânca frunza în s[i] secunde, unde s[i] este mărimea suprafeței frunzei. După ce mănâncă în întregime o frunză, viermele pornește imediat cu viteza de 1 milimetru/ secundă spre următoarea frunză, care poate fi la stânga sau la dreapta sa. Altfel spus, el își poate schimba dacă e cazul, sensul de deplasare după ce mănâncă o frunză.

Alex ar dori să știe care este numărul maxim de frunze de dud pe ar putea să le mănânce în întregime cel mai inteligent vierme de mătase pe care îl are, având la dispoziție timpul de maxim t secunde.

Cunoscând n, k, t, distanțele x[1], x[2], .., x[n] și suprafețele s[1], s[2], …, s[n] cu semnificațiile descrise mai sus, să se determine numărul maxim de frunze pe care un vierme de mătase poate să le mănânce în întregime, într-un timp cel mult egal cu t, dacă este plasat inițial pe frunza k.

Lot Juniori, Vaslui, 2014

#629 Zet

Fie \(z \in R, z \neq 0\) astfel încât \(z + \frac{1}{z} = k, k \in N\).

Dându-se k și un număr natural n, se cere:

a) să calculați \(z^2 + \frac{1}{z^2}\) ;
b) să se determine \(z^n + \frac{1}{z^n}\) .

#628 Cub1

Lui Andrei îi plac foarte mult jocurile de tip puzzle. De curând, el a descoperit un joc nou: un cub de dimensiune n format din n•n•n cuburi unitate sub forma unor cămăruţe. Cubul poate fi văzut ca o matrice tridimensionala ale cărei elemente sunt cămăruţele. Două cămăruţe se numesc adiacente dacă au o faţă comună. Astfel, o cămăruţă poate fi adiacentă cu maxim 6 cămăruţe. Scopul jocului este acela de a duce o bilă din cămăruţa de coordonate (1,1,1) în cămăruţa de coordonate (n,n,n). Bila poate trece dintr-o cămăruţă în alta doar dacă acestea sunt adiacente, iar noua cămăruţă este accesibilă din cămăruţa curentă.

Cunoscând n, dimensiunea cubului şi valorile asociate fiecărei cămăruţe, determinaţi:

a) cămăruța cu un număr maxim de cămăruțe ce pot fi accesate din ea;
b) un drum de lungime minimă de la cămăruţa (1,1,1) la cămăruţa (n,n,n).