Lista de probleme 184

În timpul activităților din “Săptămâna Altfel” elevii clasei a VII-a doresc să ajute la organizarea cărților din biblioteca școlii. Fiecare carte este etichetată cu un cod care este exprimat printr-un un șir de caractere distincte. Acestea pot fi cifrele 0, 1,..,9 și primele zece litere mici ale alfabetului englez a, b,..,j. Codul identifică în mod unic fiecare carte, adică nu vor exista două cărți cu același cod, dar şi genul literar din care acestea face parte. Cărțile din acelaşi gen literar au codul de identificare format din aceleaşi caractere, distincte, dispuse în altă ordine.

Numim coduri pereche două coduri de identificare care au același număr de caractere și care diferă printr-un
caracter. De exemplu, codurile 42a8 și 2c8a sunt coduri pereche. Pe de altă parte, codurile 42a8 și 248a,
respectiv 42ab și 248c, nu sunt coduri pereche.

Fiind dat șirul celor N coduri de identificare, scrieţi un program care să rezolve următoarele cerinţe:

1. determină numărul de cărți din cel mai numeros gen literar și numărul de genuri literare care au acest număr maxim de cărți.
2. determină numărul de coduri, din șirul celor N, care sunt coduri pereche cu ultimul cod din șir

Scrat și Scratte sunt două veverițe devoratoare de ghinde. Ele trăiesc într-un stejar înalt și culeg ghinde din cele N ramuri ale acestuia. Veverițele vor organiza un concurs: cine culege cele mai multe ghinde în K ture. Într-o tură,
fiecare veveriță se va deplasa de la vizuină până la o ramură a stejarului, de unde va culege cât mai multe ghinde, dar
nu mai mult de M ghinde, după care va reveni în vizuină. Veverițele vor efectua alternativ fiecare câte K ture, prima
care începe fiind Scratte.

Supărat că la concurs nu va începe primul, Scrat decide să se antreneze separat și să vadă câte ghinde ar culege în K
ture, dacă ar fi singur

Să se realizeze un program care determină:

1. Câte ghinde culege Scrat în timpul antrenamentului;
2. Câte ghinde a cules fiecare veveriță pe durata concursului.

Magazinul de jocuri a lansat cea mai recentă versiune a jocului Z, pentru a-i ajuta pe elevii din clasa a VIII-a să înțeleagă mai bine modul de identificare a coordonatelor unui punct din plan, într-un sistem de axe ortogonale.

Pe ecran este afișată o foaie de matematică și sistemul de axe ortogonale xOy. Succesiv, apar coordonatele întregi ale
unor puncte din plan. Jucătorul trebuie să marcheze pe foaie fiecare punct și să traseze un segment care să unească
punctul (cu excepția primului punct marcat) cu cel marcat anterior.

La sfârșitul jocului, jucătorul trebuie să numere de câte ori a trecut prin originea sistemului de coordonate O(0,0) și care este numărul maxim al semnelor Z distincte, formate cu puncte marcate.

Cunoscându-se n (numărul de puncte afișate succesiv pe ecran) și coordonatele celor n puncte din plan, să se scrie un program care determină:

1. Numărul de treceri prin originea sistemului de coordonate.
2. Numărul maxim al semnelor Z distincte, formate cu puncte marcate.

În regiunea Ionia a lumii grecești antice, regiune ce corespunde teritoriului actual al Mării Egee, există mai multe insule. Harta mării este reprezentată de o matrice de dimensiuni N•M, având valori de 1 și 0, iar fiecare element din matrice reprezintă o zonă de dimensiune 1•1 din mare. Liniile matricei sunt numerotate de la 1 la N, de sus în jos, iar coloanele de la 1 la M, de la stânga la dreapta. Astfel, colțul din stânga sus al matricei este asociat zonei (1,1), iar colțul din dreapta jos corespunde zonei (N,M).

Un element care conține valoarea 0 reprezintă faptul că în acea zonă se află apă. O insulă este determinată
de un dreptunghi format în totalitate din valori de 1. Se garantează faptul că toate zonele care conțin valoarea 1
formează dreptunghiuri valide și că oricare două insule sunt separate de apă.

Ionienii, fiind oameni practici, doresc construirea unui far-bibliotecă (așezat pe o platformă 1•1), într-o zonă acoperită de apă. Poziția platformei va fi aleasă într-o celulă C astfel încât suma distanțelor dintre toate insulele și C să fie minimă. Distanța dintre o celulă C și o insulă este definită ca fiind minimul dintre distanțele Manhattan dintre C și fiecare celulă care aparține insulei (distanța poate trece atât prin alte insule, cât și prin zone acoperite de apă). Distanța Manhattan dintre două celule aflate pe linia x1 și coloana y1, respectiv pe linia x2 și coloana y2, este definită ca |x1 – x2| + |y1 – y2|, unde |x| reprezintă valoarea absolută a lui x.

Numim „oglinda” numărului natural nenul a, numărul b, obţinut prin modificarea fiecărei cifre din reprezentarea sa binară, de exemplu pentru a=22(10)=10110(2) se obţine 01001(2)= 9(10)=b.

Cunoscându-se numerele naturale N, K și cele N numere natural nenule, scrieți un program care:

1. Transformă în baza doi termenii şirului dat obţinându-se un nou şir format din alipirea cifrelor binare. Din acest şir se vor determina și afișa, separate prin câte un spațiu, toate reprezentările în baza 10 corespunzătoare secvenţelor alăturate de exact K cifre binare, parcurse de la stânga la drepta. Dacă ultima secvenţă nu are exact K cifre binare, atunci aceasta nu se va mai lua în considerare.
2. Să aplice K transformări asupra şirului iniţial, înlocuind la fiecare pas orice termen cu „oglinda” sa. Asupra termenilor care devin zero nu se vor mai efectua alte operații. După efectuarea celor K transformări, să se determine cea mai lungă secvență de numere care au cifra 1 pe aceeași poziție în reprezentarea lor în baza doi. Dacă sunt mai multe astfel de secvențe având lungimea maximă, se va afișa cea mai din stânga.

Despre numărul natural N spunem că are proprietatea okcpp dacă oricum alegem K cifre ale sale vom găsi printre ele cel puţin P cifre distincte (oricare k cel puțin p).

Cerințe

(1) Fiind date numerele naturale K, P, A și B să se calculeze și să se afișeze numărul de numere okcpp din intervalul [A,B].
(2) Fiind date numerele naturale K, P și N să se calculeze și să se afișeze cel mai mic număr okcpp care este mai mare sau egal cu N.

În tărâmul Jupânului există N + 1 orașe. Acestea au fost construite în linie dreaptă, începând cu cel în care este casa Jupânului. Între oricare 2 orașe consecutive s-a construit câte un drum. Pentru fiecare drum, se cunoaște lungimea lui, exprimată în metri și viteza cu care se poate parcurge, exprimată în metri pe secundă.

Jupânul trebuie să ajungă din orașul 0 în orașul N. Acesta știe că poate îmbunătăți un drum, mărindu-i viteza de la V metri pe secundă la V + 1 metri pe secundă, cu costul de 1 dolar. Acesta poate îmbunătăți un drum de mai multe ori.

Jupânul are un buget de X dolari și ar vrea să-i folosească pentru a micșora timpul în care ajunge din orașul 0 în orașul N.

Se consideră aranjamentul piramidal de numere cunoscut și sub denumirea de triunghiul lui Pascal. În vârful și pe marginile laterale ale piramidei se află numărul 1. Restul numerelor din acest triunghi se formează ca suma celor două numere de deasupra. Definim un tripas(r,c,L) ca fiind un triunghi echilateral de numere din interiorul triunghiului lui Pascal, pentru care se precizează poziția (r, c) a vârfului și L, lungimea laturii (r=rând, c=coloană, L=lungime latură). Exemplu: tripas(3,1,4) – reprezintă triunghiul de numere cu vârful poziționat pe rândul al treilea, primul element și care are lungimea laturii de 4 elemente, adică numerele (1), (1,3), (1,4,6), (1,5,10,10) – scrise de sus în jos și de la stânga la dreapta. Pe figura de mai sus, tripas(3,1,4) are elementele încadrate în dreptunghiuri. Notăm cu S suma elementelor unui tripas(r,c,L).

Se consideră o succesiune de numere naturale a[1] a[2] ... a[N]. Cu aceste numere se construieşte un şir de caractere astfel: pentru fiecare număr a[i] din şir (i=1, 2, ..., N) se scrie mai întâi numărul de cifre ale lui a[i], apoi cifrele lui a[i].

Scrieţi un program care pe baza şirului de caractere să determine câte numere sunt în succesiune, precum şi descompunerea în factori primi a produsului numerelor din succesiune.

Stațiunea Xoni de pe insula Ixos are N magazine de înghețată, așezate unul lângă altul, pe aceeași parte a străzii pietonale. Acestea sunt numerotate cu valori naturale de la 1 la N , în ordinea așezării pe stradă.

Magazinele sunt deținute de K acționari (numerotați de la 1 la K ), fiecare dintre aceștia fiind proprietarul unor magazine numerotate consecutiv. Un magazin poate avea mai mulți acționari.

Odată cu venirea verii, începe și perioada concediilor, toți acționarii luându-și concediul împreună, timp de M zile. Înainte de a pleca în concediu, ei au discutat cu Transportel pentru a se ocupa de aprovizionarea cu înghețată a magazinelor lor. Acesta a decis, singur, să facă în fiecare dintre cele M zile aprovizionarea unor magazine, numerotate și acestea cu numere consecutive.

Determinați, pentru fiecare acționar numărul de magazine deținute de către acesta care nu au fost aprovizionate cu înghețată în nicio zi din concediu.