Lista de probleme 160

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.

Regele Rufus dorește să stabilească moștenitorul averii sale, adică să ofere parola de la seif celui mai deștept dintre fiii săi. Inițial, regele a avut parola X formată din N cifre nenule și un cod cheie Q (număr natural cu exact nouă cifre, distincte, toate nenule). În fiecare an din cei K ani de domnie, folosind codul cheie Q, Rufus a modificat câte o secvență de cifre din parolă ajungând la parola finală P.Pentru fiecare secvență se cunoaște poziția S a primei cifre din secvență și poziția D a ultimei cifre din secvență. Astfel, secvența este formată din cifrele situate pe pozițiile S, S+1, S+2,…, D în parola X.

Modificarea unei secvențe din X constă în înlocuirea fiecărei apariții a cifrei 1 cu prima cifră a lui Q, apoi a fiecărei apariții a cifrei 2 cu a doua cifră a lui Q,…, a fiecărei apariții a cifrei 9 cu ultima cifră a lui Q.

Pentru a decide moștenitorul, regele le dă fiilor parola finală P, codul cheie Q, numărul K de ani de domnie și cele K secvențe de cifre care au fost modificate și le cere să găsească: parola inițială X, poziția minimă Z din parola X care a apărut în cele mai multe secvențe dintre cele modificate de rege de-a lungul celor K ani de domnie și cifrele distincte care au ocupat poziția Z în cei K ani.

Scrieți un program care citește numerele Q, N, K, cele N cifre ale parolei finale P și cele K perechi de poziții S și D, și care rezolvă următoarele două cerințe:

1. determină parola inițială X;
2. determină poziția minimă Z și cifrele distincte care au ocupat această poziție în cei K ani de domnie.